NOIp2020 T3 移球游戏 题解 附带70分解法

题意:给定 n+1n+1 个栈,栈的高度限制为 mm。初始时前 nn 个上每个有 mm 个球,最后一个为空。球分为 nn 种颜色,每种恰好 mm 个。一次操作可以把一个栈顶的元素弹出放到一个另一个栈顶,但是不可以使栈溢出或下溢。现要把同种颜色的球移动到同一个栈上,你需要构造一个在 820000820000 次操作内的方案。

先来看通过这个操作都能干什么。例如,我们可以把一个满栈 XX 中所有颜色为 yy 的球挪到栈顶,这项操作需要借助另一个满栈 HH 和一个空栈 NN

  1. 数一下 XX 中共有多少个颜色为 yy 的球,这个数字记为 aa
  2. HH 栈顶 aa 个元素依次放入 NN。操作后 HHaa 个空位,NNmam-a 个空位。
  3. 一直弹出 XX 的栈顶元素,如果颜色为 yy 则放入 HH,否则放入 NN,直到 XX 为空。这时 HHNN 都恰好满了。
  4. NN 栈顶 mam-a 个元素依次放入 XX,把 HH 栈顶 aa 个元素依次放入 XX。这时 XX 中的元素还是原来的那些,不过顺序发生了变化,所有颜色为 yy 的都在栈顶。
  5. NN 全部 aa 个元素依次放入 HH。操作后 HHNN 恢复了操作前的原样。

这项操作的移动步数是 2m+2a2m+2a。为了方便,我们把这个操作叫做“上提”。

有了这项操作,我们可以构造出一个算法:

  1. 任选一个颜色 yy,把所有 nn 个栈中颜色为 yy 的球都上提。
  2. 把这些颜色是 yy 的球都移到那个空栈里。
  3. 任选一个栈,把它的元素都移动到其他没满的栈里。
  4. 去掉颜色是 yy 的球组成的栈,则问题规模 nn 减小了 11。回到第一步重新执行,直到 n=1n=1 结束。

这个算法的移动步数上界也容易分析。每次执行第一步的操作次数是 (2n+2)m(2n+2)m,第二和第三步每一步是 mm,合起来是 (2n+4)m(2n+4)m。那么总体步数上界为 i=2n(2i+4)m=(n+6)(n1)m\sum_{i=2}^n(2i+4)m=(n+6)(n-1)m

带入 7070 分部分分数据范围,算了一下这个数字是 823200823200,还差一点。于是……

潜在的常数优化方法:

  • 上提操作的第三步,不需要把 XX 弹到空,只需要弹到里面没有颜色 yy 的球即可。
  • 在上一条优化的基础上,算法的第一步,可以计算出上提每种颜色的球的代价,然后找一种最小的上提。
  • 上提的第二步和第五步,如果 ma<am-a<a,则只需要移动 mam-a 个元素,然后交换一下 NNHH 的作用即可。

加上这些优化,7070 分到手。考虑正解。

考虑一个对两个栈的操作:给定栈 X,YX,Y,重排两个栈的元素使得 max{X}min{Y}\operatorname{max}\{X\}\leq \operatorname{min}\{Y\}。其中,max\operatorname{max}min\operatorname{min} 都是针对颜色编号而言的。这个操作也需要借助另一个满栈 HH 和一个空栈 NN。注意到同一种颜色可能有很多球,不便于操作,我们可以把所有元素分成“大的一半”和“小的一半”,分别应该装进 YYXX 里。以下我们用“元素为大”、“元素为小”称呼。

  1. 数一下 XX 中共有多少个元素为大,这个数字记为 aa
  2. HH 栈顶 aa 个元素依次放入 NN。操作后 HHaa 个空位,NNmam-a 个空位。
  3. 一直弹出 XX 的栈顶元素,如果为大则放入 HH,否则放入 NN,直到 XX 为空。这时 HHNN 都恰好满了。
  4. NN 栈顶 mam-a 个元素依次放入 XX
  5. 一直弹出 YY 的栈顶元素,如果为大则放入 NN,否则放入 XX,直到 YY 为空。这时 NNXX 都恰好满了。
  6. NN 栈顶 mam-a 个元素依次放入 YY,把 HH 栈顶 aa 个元素依次放入 YY
  7. NN 全部 aa 个元素依次放入 HH。操作后 HHNN 恢复了操作前的原样。

为了方便下文管这个操作叫“切分”,意思当然是把小的一半切出来。操作结束时,XX 所有元素为小,YY 所有元素为大。这就达成了我们的目的。这个操作的步数是 4m+a5m4m+a\leq 5m。可以使用类似上面第三条常数优化,如果 ma<am-a<a,则第一步和第七步只需要移动 mam-a 个元素,然后交换 HHNN 的作用即可。优化后移动次数不超过 92m\frac{9}{2}m

注意到这个操作不适用于 n=2n=2(因为压根就找不到可以用的 HH),于是把 n=2n=2 特判出来,跑上面的算法。

有了这个操作,我们可以使用类似冒泡排序的方式把整个 nn 个栈按照颜色排序,排序之后很显然每个栈里球颜色一样。排序的正确性参照冒泡排序很容易证明(最大的元素一定会冒到最右边),可以算出移动步数 94n(n1)m\frac{9}{4}n(n-1)m,渐进复杂度相同的情况下常数比上面那个算法大了一倍多,只能过 4040 分,看起来根本没用……

尝试换一种排序:归并排序。要解决的问题就是如何归并。类似普通归并的过程,维护两个指针 xxyy,初始值在要归并的两个区间最左侧。把两个指针指向的栈分别称为 X,YX,Y。如果 max{X}<max{Y}\operatorname{max}\{X\}<\operatorname{max}\{Y\},对 X,YX,Y 执行切分,小的一半放到 XX,然后把指针 xx 递增,继续执行。否则把小的一半放在 YY,指针 yy 递增。这样做是正确的,因为未归并区间最小的 mm 个元素一定包含在了 XXYY 里。最后我们可以得到一系列从小到大的栈,不过它们并没有摆在它们应该在的位置上。于是归并的过程中记录一下每个栈应该在的位置,利用那个空栈进行整体移动,可以使用不超过 2L2L 次整体移动把它们摆好(LL 是归并的区间长度)。于是,要归并一个长度为 LL 的区间,要执行不超过 LL 次切分和不超过 2L2L 次整体移动,总操作次数不超过 132Lm\frac{13}{2}Lm

由归并排序的复杂度证明得,所有归并的区间长度和是不会超过 nlog2nn\lceil\log_2n\rceil 的,于是这个算法的操作次数上界是 132nlog2nm\frac{13}{2}n\lceil\log_2n\rceil m(很松,根本卡不满),算一下数字 780000780000,轻松过题。

还有一个优化,就是归并之后的“整体移动”其实是没必要的,可以用一个数组记录一下假装移动了,那么排序长度为 LL 的区间操作次数只有 92Lm\frac{9}{2}Lm,极限数据下总操作次数不会超过 540000540000