口胡

Difficulty：5.1 / Medium

Tag：-

这个游戏大家应该都玩过吧，感觉好玩程度不亚于看 B 站。

独立胡出来了，说明我可以 AK NOIP（

中考完完善代码。

40 pts

和正解没啥关系。但一般都是这么玩的吧。

考虑枚举颜色，然后让所有颜色的球都到同一个柱子上。

具体地，如果你想将一个球一到对应的地方，你先把它上面的球清空（移到别处），然后再把这个球移出来，再把之前移的放回去。由于空位永远是 $m$，所以一定办得到。

移动一个球是 $2m$ 的，总共就是 $2nm^2$ 的。

正解

这里讨论 $m$ 为偶数的情况。

注意到如果只移动一种颜色太浪费了，考虑一次移动多种颜色。

我们有种移动方法：选取 $\lfloor \frac{n}{2}\rfloor$ 种颜色，将这些颜色记为“白”，剩下颜色记为“黑”。想办法将所有白球和黑球分开，然后分别递归黑白两色。

这样，我们就以 $\lceil\log_2 n\rceil-1$ 的代价将问题弱化到如何分开两种颜色。

首先我的想法是和前面一样，把所有黑球 / 白球一次性移到一个柱子上。然后卡了 1h+ 完全不会。

听了会历史知识回顾，突然明白了：有时候，完成比完美更重要。后退不代表放弃，而是通往成功的垫脚石。

定义一个柱子顶上 $\frac{m}{2}$ 的球为“上半”，下面 $\frac{m}{2}$ 为“下半”。

• 我们将一个柱子的上半移到空柱子上，这样就有两个上半为空的柱子。一个上半专装黑球，一个上半专装白球。称此操作为“迪外得”。
• 随便挑选顶上的球装到两个柱子，直到一个柱子装满。称此操作为“巴克特”。
• 将没装满的柱子清空，再将装满的柱子进行“迪外得”操作。
• 再进行一次“巴克特”操作。这次预先计算装的黑球、白球，有意地将先装满的球放到下半已经装好的柱子。
• 将没装满的柱子清空。

这样我们就在 $5m$ 次操作下获得了一个上半同一个颜色，下半也同一个颜色的柱子。

然后将所有柱子都变成这种，再花 $0.5m(n+1)$ 次操作即可分开黑白颜色。

这样总次数为 $5.5nm(\lceil\log_2 n\rceil-1)+\text{eps}$。

对于 $m$ 为奇数的情况，可以将上半改为 $\lfloor\frac{m}{2}\rfloor$，在“巴克特”操作时精细实现，控制黑 / 白球分别有 $\frac{n}{2}$ 次处于上半，$\frac{n}{2}$ 次处于下半。

可以用一些乱搞做法比如随机打乱颜色让它更卡不满。

结尾不会写。

综上所述，很有教育意义。