Educational Codeforces Round 109 (Rated for Div. 2) 题解

[toc]

AC代码

A. Potion-making

给定正整数 $k$，已知 $\frac{x}{x+y}=\frac{k}{100}$ ，求 $\min{(x+y)}$ 。

$k\leq 100$ 。

变形一下得到 $x+y=\frac{100x}{k}$ ，范围很小直接暴力枚举 $x$ 。

B. Permutation Sort

给定一个大小为 $N$ 的排列 $P$ ，你每次可以选择一个任意的连续子序列，然后按照任意顺序重排该序列（但不能直接选择整个数组），询问最少需要操作几次才能将这个排列重排成上升序列。

$N\leq 50$ 。

分四类情况：

初始序列已经是升序，不需要额外操作。
初始序列乱序，但是 $P_1=1$ 或者 $P_n=n$ ，那我们只需要选择 $[2,n]$ 或者 $[1,n-1]$ 就能只花费一次操作完成排序。
初始序列乱序，但是 $P_1=n$ 并且 $P_n=1$ ，如果要将 $P_1$ 变为 $1$ 或者 $P_n$ 变为 $n$ 至少需要两次操作，再加上剩下的一次排序，最小花费为 $3$ ；
初始序列乱序，且不为上述情况之一，那只需要考虑花费一次操作将 $1$ 搬运至 $P_1$ ，或者将 $n$ 搬运至 $P_n$ ，最小花费为 $2$ 。

C. Robot Collisions

在数轴 $[0,M]$ 区间上有 $N$ 个坐标不同的机器人（均位于整点），每个机器人初始都有一个运动方向（L 表示向左，R 表示向右）。每个机器人每秒都会在他运动方向上往前跳跃一个单位距离，如果到达了 $x=0,M$ 就会改变运动方向然后在下一秒往回跳。

如果有两个机器人跳到了相同的坐标，那这两个机器人就会碰撞并爆炸，爆炸后该机器人就会消失，询问所有 $N$ 个机器人的爆炸时间，如果某个机器人不会爆炸就输出 $-1$ 。

$\sum N\leq 3\times 10^5,M\leq 10^8$ 。

假设某个机器人的初始位置是奇数，那么它在奇数秒就一定会跳到偶数坐标，在偶数秒则会跳到奇数坐标，而初始坐标在偶数的机器人则正好相反。这说明初始坐标奇偶性不同的机器人永远不会相撞，因此我们先将这两类情况分开考虑。

然后我们不难发现两个机器人之间有三类不同的相撞情况：

初始方向为 $R-L$ 。
初始方向为 $L-L$ 或 $R-R$ 。
初始方向为 $L-R$ 。

其中，$R-L$ 类型的相撞优先级最高，而且满足就近原则，相邻的两个 $R-L$ 机器人一定会相撞，然后这两个机器人消失，外围的 $R-L$ 机器人再相撞……我们可以直接用栈去除这类情况，于是剩下的机器人一定是这个样子了：L L L ... L R R ... R R 。观察这个序列，显然两端的机器人会优先相撞，这意味着最左侧的 $L-L$ 对，和最右侧的 $R-R$ 对会相撞。因此，这个就是一个双向队列，知道所有的 $L-L,R-R$ 相撞情况均被排除后，才会剩下 $L-R$ 这种情况，最后特判即可。

D. Armchairs

有 $N$ 个座位排成一列，不超过一半的座位上有人坐着，你可以花费 $|i-j|$ 的代价将当前位于第 $i$ 个座位上的人移动到第 $j$ 个。询问将所有初始有人的座位空出的最小代价。

$N\leq 5000$ 。

有一个重要的性质：所有人在更换了座位后相对位置不变，因此可以通过dp解决本题。

假设 $dp[i][j]$ 表示第 $i$ 个人移动到第 $j$ 个空座位中最小的花费，那么显然有：

$$
\begin{aligned}
dp[i][j]=\min(dp[i][j],dp[i-1][j-k]+dis(i,j))
\end{aligned}
$$

上式中，$k=1,2,\ldots,j$ 。虽然这个转移是 $O(n^3)$ 的，但是显然可以通过前缀最小值优化至 $O(n^2)$ 。

E. Assimilation IV

有 $N$ 座城市和 $M$ 个点，城市 $i$ 到点 $j$ 的距离是 $d_{i,j}$ 。对于所有的 $[1..N]$ 的排列 $P$ ，第 $i$ 轮会在城市 $P_i$ 建立一座纪念碑，每座纪念碑初始可以覆盖到距离城市 $i$ 小于等于 $1$ 的点，每过一轮辐射距离 $+1$ （也就是说建立纪念碑后的第二轮可以覆盖距离小于等于 $2$ 的点……）。询问对于所有不同的排列而言，最终覆盖点数的期望？

$N\leq 20,M\leq 50000$ 。

由于期望的线性性质，不妨对于每个点考虑在所有 $n!$ 的情况中它对答案的贡献，将这些贡献累加即为期望值。

对于点 $j$ 到所有城市的 $n$ 个距离 $d_{i,j}$ ，我们先从小到大排序，然后反向思考：一个点不被覆盖到的情况仅存在于选中城市 $i$ 的轮次 $turn_i>n-d_{i,j}+1$ （且该条件对于任意的 $i$ 均成立），转换一下可以得到：$turn_i+d_{i,j}>n+1$ 。也就是说，这题已经转换成了一个子问题：找到不同的排列 $turn(1,2,\ldots,n)$ 的数量，该排列对于任意 $i$ 成立有 $turn_i+d_{i,j}>n+1$ 。

这个子问题的形式不利于我们进行更进一步的运算，因此令 $turn’_i=n+1-turn_i$ ，注意到 $turn’$ 也是一个 $(1,2,\ldots,n)$ 的排列，因此本问题的限制条件可以再次转化为：

\begin{aligned} &\ turn_i+d_{i,j}>n+1\\ \Leftrightarrow&\ n+1-turn’_i+d_{i,j}>n+1\\ \Leftrightarrow&\ turn’_i<d_{i,j}\\ \Leftrightarrow&\ turn_i<d_{i,j} \end{aligned}

由于前文中，我们已经对 $d_{i,j}$ 从小到大排序，因此 $turn_i$ 的可选区间是单调不减的，因此 $turn_1$ 可以在 $(1,2,\ldots,d_{1,j}-1)$ 中取到，可行数量为 $\max(0,d_{1,j}-1)$ ，而 $turn_2$ 的可行取值集合完全包含了 $turn_1$ 的集合，因此可行取值数为 $\max(0,d_{2,j}-1-1)$ ……

这说明一个点被覆盖到的概率为 $1-\frac{\prod_{i=1}^n\max{(0,d_{i,j}-i)}}{n!}$ ，由于每个点的权值为 $1$ ，该式累加即为期望。

~~我降智了，这个子问题推了好久才想通。~~