2020牛客暑期多校训练营(第五场)
A. Portal
题目描述
You are now in a big factory. The factory could be recognized as a graph with n vertices and m edges. Every edge has its length. You have missions to do. The -th mission is going to vertex , picking a block and then sending it to vertex . You should complete the missions in the order from -st to -th. Initially you are standing at vertex .
You have a gun in your hand. When you are at some vertex , you could shoot the gun at the ground, and then a portal will be built at vertex . When there are two portals in the factory, assuming they are at and , you could transfer between and with no cost (just like an edge connecting and with length ).
You also have a remote controller in your hand. It allows you to close a portal whenever you want and wherever you are (closing one portal at a time, not all portals at the same time). What’s more, there could be at most two existing portals. So if you want to create another portal when there exists two, you must use your controller to close one before you create.
You need to find the minimum distance you have to walk in order to complete all missions.
输入描述
First line contains three positive integers separated by spaces.
Next lines, each contains three integers , indicating a bidirectional edge connecting vertex and with length .
Next lines, each contains two intergers , indicating the begin and the end of the -th mission.
, , .
, .
.
The graph is guaranteed to be connected.
输出描述
Output one integer indicating the minimum distance.
示例1
输入
1 | 5 4 2 |
输出
1 | 5 |
说明
Solution for sample : walk from to , create portals at and when passing by, and then walk from to , then you could use portals to complete the second mission.
示例2
输入
1 | 6 10 3 |
输出
1 | 28 |
示例3
输入
1 | 6 10 3 |
输出
1 | 16 |
分析
用动态规划求解。
表示已经完成了第 个任务,当前人在节点 ,传送门在节点 和 时,行走的最短距离。状态过多,显然会 和 。
贪心地思考,一直创建两个传送门是没有必要的:若要从 传送到 ,当前节点为 ,那么必须要从 走到 再传送到 ;不妨只在 创建一个传送门,走到 后再设置传送门;也就是说,我们可以随时在当前节点创建传送门。因此,只需要在状态中记录一个传送门的位置即可。 表示已经完成了第 个任务,当前人在节点 ,传送门在节点 时,行走的最短距离。需要继续精简状态。
不妨将 个任务看作一条路径:。一共有 个节点, 表示第 个节点,其中 。 表示当前人位于节点 ,传送门位于节点 时,行走的最短距离。
可以证明,只需要三种转移,即可覆盖所有状态:① 直接从 走到 ,不更改传送门位置;② 枚举 ,将传送门的位置更改到 ,从 传送到 ,再从 走到 ,将传送门放在 ,再从 走到 ;③ 枚举 ,将传送门的位置更改到 ,从 走到 ,将传送门放在 ,再从 传送到 ,从 走到 。
代码
1 | /****************************************************************** |
B. Graph
题目描述
Mr. W got a new graph with vertices and edges. It’s a connected graph without cycles. Each edge should have an ugly value. To make the graph more beautiful, Mr. W hope you can help him modify it. You can delete or add one edge with an ugly value at a time and you can do it as many times as you want. But the following conditions should be satisfied at any time. The graph is connected. For each cycles in the graph, the XOR sum of all ugly values in the cycle is .
Mr. W wants to know the minimum sum of ugly values of all edges in the graph.
输入描述
The first line contains one integer .
Next lines each contains three integers , denoting an edge between vertex and with ugly value .
输出描述
One integer, the minimum sum of ugly values of all edges in the graph.
示例1
输入
1 | 6 |
输出
1 | 7 |
分析
可以发现任意两个点之间连边的权值都是固定的。由于图始终连通,所以两点间始终存在至少一条路径,如果存在多条,根据环的异或和为 ,两点间的路径的异或和应该相等,且始终是固定的。在初始状态,设根节点(设为 )到节点 路径的异或和为 ,那么若要在 之间添加一条边,为满足环的异或和为 ,其边权必须为 。
可以视为: 个节点的完全图中,节点 的点权为 ,两点间的边权为两点权的异或值接下来。如此一来,预处理点权 后,就转化为求解异或最小生成树的问题,可以参考异或最小生成树模板题:CF888G。
代码
1 | /****************************************************************** |
D. Drop Voicing
题目描述
Inaka composes music. Today’s arrangement includes a chord of notes that are pairwise distinct, represented by a permutation of integers from to (inclusive) denoting the notes from the lowest to the highest.
Her friend, Miyako, sneaks in and plays a trick by altering the chord with the following two operations. : Take out the second highest note and move it to the lowest position, i.e. change the permutation to . Invert: Take out the lowest note and move it to the highest position, i.e. change the permutation to .
Any number of consecutive operations is considered a multi-drop. Miyako would like to change the permutation to an ordered permutation, , in the fewest number of possible. Please help her find the number of needed.
输入描述
The first line contains an integer — the number of notes.
The second line contains n space-separated integers — the original permutation of notes.
The input guarantees each integer from to (inclusive) appears in the permutation exactly once.
输出描述
Output one integer — the number of required to change the permutation to an ordered one.
示例1
输入
1 | 6 |
输出
1 | 2 |
说明
An optimal solution with two multi-drops is:
, times, changing the permutation to ;
, times, changing the permutation to ;
, times, changing the permutation to ;
, time, changing the permutation to .
示例2
输入
1 | 8 |
输出
1 | 5 |
分析
对于操作 ,可以将 看作一个环,环的长度为 ,即进行 次操作 ,排列还原;对于操作 ,可以将 看作一个环,环的长度为 ,即进行 次操作 ,排列还原。形成的两个环如图所示, 代表当前排列 的第一个数, 代表位于大环(长度为 的环)上,而在小环(长度为 的环)外的数。
小环和大环可以独立顺时针转动,两个指针 和 的位置是固定不动的;当转动小环,视为进行了一次 ,当转动大环,视为进行多次 。可以发现,当转动小环,可以将位于小环外的数字,插入任意两个数字之间。在图中,当前 位于 和 之间,转动一次小环, 就在 和 之间了;显然,进行一次 ,可以将 放入任何你想要的位置。更一般的,若要该边数字 在大环中的相对其他数字位置,应该首先用多次 将 放入 标记的位置,然后进行一次 。我们要对大环上的数字进行排序,那么只需要通过若干次操作,利用小环调整一些数字的相对位置,令大环上形成 这样的环,再进行几次 即可将原序列 完成排序。
那么问题就变得简单:每次调整一个数的位置就要进行一次 ,因此要调整尽可能少的数字。不妨找出大环上的一个 (最长上升子序列),其长度为 ;对于在 上的 个数字不作调整,只需要调整 个数字的相对位置;显然,这样的方案使得需要调整的数字个数最小。对于不在 上的 个数字,用 次 和若干次 ,即可将这 个数字一一放入正确的位置,完成排序。
计算环上的 长度时,可以枚举环的起点,对 个起点各求一次 ,取长度最大的即可。时间复杂度为 。
代码
1 | /****************************************************************** |
E. Bogo Sort
题目描述
Today Tonnnny the monkey learned a new algorithm called Bogo Sort. The teacher gave Tonnnny the code of Bogo sort.
1 | bool is_sorted(int a[], int n) { |
The teacher said the shuffle function is to uniformly randomly permute the array with length , and the algorithm’s expectation complexity is .
However, Tonnnny is a determined boy — he doesn’t like randomness at all! So Tonnnny improved Bogo Sort. He had chosen one favorite permutation with length , and he replaced the random shuffle with shuffle of , so the improved algorithm, Tonnnny Sort, can solve sorting problems for length array — at least Tonnnny thinks so.
1 | int p[N]={....};// Tonnnny's favorite permutation of n |
Tonnnny was satsified with the new algorithm, and decided to let you give him a different array of length every day to sort it with Tonnnny Sort.
You are the best friend of Tonnnny. Even though you had found the algorithm is somehow wrong, you want to make Tonnnny happy as long as possible. You’re given , and you need to calculate the maximum number of days that Tonnnny will be happy, since after that you can’t give Tonnnny an array that can be sorted with Tonnnny Sort and didn’t appeared before.
The answer may be very large. Tonnnny only like numbers with at most digits, so please output answer mod instead.
输入描述
The first line contains one integer .
The second line contains integer indicating , which forms a permutation of .
输出描述
The maximum number of days that Tonnnny will be happy, module .
示例1
输入
1 | 5 |
输出
1 | 1 |
示例2
输入
1 | 6 |
输出
1 | 6 |
分析
在 的 中,有操作 ,实际上是用置换 将原序列 映射到当前的序列 。如 ,那么就有:,,,形成了 的闭环,即 三者的值进行了交换;同理,有 这样的闭环。
问题转化为:给定置换 ,求多少种排列可以通过置换 完成排序。不妨考虑将排序后的序列 用置换 打乱会产生多少种不同序列。设排序后的序列为 , 有 个环,且各个环的长度为 ,显然,利用置换 进行 次 , 回到最初排完序的状态,而每次操作后得到的序列都是不同的。因此,只要找出置换 所有的环,所有环长的最小公倍数即为答案。
值得注意的是,数据范围较大,可以使用 的 类。并且,所有环的长度总和为 ,所以所有环的长度的最小公倍数不可能超过 ,因此最后不必煞费苦心地将答案对 取模。
代码
1 | /****************************************************************** |
F. DPS
题目描述
When you are playing multiplayer games, you may want to show that you are the MVP of your team or blame the one always wandering and watching away from the storm center. Well, there’re statistics that show you preformance, but sometimes numbers speak softer than charts. Now, you’re hired to write a program that output ASCII art histograms showing damage dealt to enemies.
There are players in the game. Given that the -th player dealt damage to enemies where is granted, you need to calculate the number of spaces in the bar by the following foluma: . Instead of formal definition of bar description, we will give an example. For some player i whose and , the bar is shown as:
1 | +-------+ |
Moreover, you have to mark the player with maximal damage dealt to enemies by replacing the last space into *
. If there’re multiple maximum, mark all of them.
See samples for more ideas.
输入描述
The first line contains one integer .
The next line each contains one integer, the -th line contains .
It’s granted that .
输出描述
lines, each lines denote a bar in the correct format.
示例1
输入
1 | 4 |
输出
1 | +--------------------------------------------------+ |
示例2
输入
1 | 5 |
输出
1 | +--------------------+ |
分析
按照题意模拟即可。
需要注意细节:计算 时会爆 ;最大值在直方图中要作出标记; 要紧靠直方图输出,并在第二行输出。
代码
1 | /****************************************************************** |
I. Hard Math Problem
题目描述
You are a player of the game Mine Craft. As a lawful goo?d player, instead of dropping TNT everywhere you want to build your village on a vast plain.
The game map could be recognized as a rectangle grid. In one grid, you can set up a gold miner, or an elixir collector, or a headquarter. You also can leave some grids green and vibrant.
However, one restriction for some good reasons is that a headquarter must be next to at least one gold miner and at least one elixir collector. Next to means that their grids share one side, every grid is next to up, down, left, and right grids.
“Efficiency!” A good old man said to you. You, the vast plain holder, want to be the most efficient player in the server. You want to maximize the number of headquarters in your village. Formally, If the village is a grid of size , we define the max number of headquarters can be built as . For example, since there should be at least grids for setting up a headquarter; and one possible solution is .
To prove that you really understand the problem very well, print the efficiency on the infinite plain. Formally, you need to calculate .
输入描述
No input.
输出描述
A real number denoting the answer to the question. Round the answer to decimal places. For example, if your answer is , print .
分析
用 代表总部, 代表黄金矿工, 代表圣水收集器,如图的结构能够使总部的数量尽量多。
对于一个无穷网络,一个单元已经用虚线框出。一个总部分到 个黄金矿工和 个圣水收集器。一个单元所占格子数量为 ,一个总部占整个单元的 。
代码
PHP是世界上最好的语言!
1 | 0.666667 |