题解：P7115 [NOIP2020] 移球游戏

Mirasycle · 2024-12-25 20:12:02 · 题解

暑假 vp 的时候连 n=2 的常规解法都没想到，于是一波爆搜强行构造 n=2 方案喜提 10 分。

当时还不会按照值域 0/1 分治的 trick，不过后来见到了无数次这种 trick。

我印象中这个题也是分治构造的。 P9731 [CEOI2023] Balance

下文中将柱子称为栈 s，毕竟两者的用法是一样的。

先思考 n=2 时候的解法，记录两个栈为 s_1 和 s_2，分别目标为 1 球和 2 球。我们现在想要其中一个栈变成全 1。我们发现 s_1 和 s_2 都往空栈里面放一点东西进去似乎只有暴搜放进去的顺序然后 2 和 3 栈互相搞一下的很暴力的做法，没有可扩展性。

有没有什么好办法去分离 1 和 2 两种小球呢，只有两个空栈能办到。我们现在只有一个空栈，转念一想，其实我们可以再创造两个半空栈，设 s_1 中有 a 个 1，那么我们只需要从 s_1 中挪 \min(a,m-a) 个球给 s_3。不妨设 a<m-a，然后将 s_1 中球依次弹出，如果是 1 则放入 s_2 中，如果是 0 则放入 s_3 中，这次操作把部分 0 和 1 聚集在了一起。

接着，把 s_2 和 s_3 栈顶的 0/1 段全部再放回 s_1 中，这一步我们实现了对于 s_1 的排序。

将 s_2 中的所有数移动到 s_3 中，再把 s_1 中顶端的 1 段放入 s_2 中。这一步我们实现了将 0 和 1 段分别独立地放在 s_1 和 s_2 中。

然后就是处理 s_3 了，我们只需要根据是 0 还是 1 分别放入 s_1 或者 s_2 即可。

这样子我们就完美解决了 n=2 的情况。

那么对于 n>2 的时候呢？把问题转化到 n=2！

我们设 \operatorname{solve}(l,r) 表示正在处理颜色为 [l,r] 范围内的球。我们将 x\le mid 的球全部看成一种颜色，将 x>mid 的球看成另一种颜色，然后执行 n=2 的算法就可以将 x\le mid 的球放在一起，x>mid 的球放在一起，然后再分别进行操作 \operatorname{solve}(l,mid) 和 \operatorname{solve}(mid+1,r) 就可以继续分治下去解决问题了。