题解 P7115 【移球游戏】

· · 题解

具体的解决方案大佬们都已经给出了，我主要想给大家来捋一捋如何去思考这个问题，建立一个思考问题的流程，毕竟我不会“不难注意到”，“易得”，“显然”之类的高端操作。

Step1

首先看一看数据范围，十分是n<=2，其实也就是n=2

那么对于 n=2 的特殊情况改如何思考呢，我们先从简单的来想，如果 m=1 的话就不需要做了，直接就是满足情况，那么当 m=2 的时候，会有四种情况，不过两两对称，其中两种也是直接满足要求的，所以我们干脆就只讨论唯一需要做的一种。如下图 对于这种情况，我们很容易能想到做法，直接把A柱上面的第一个球（其实是木块）移到C，再把B上的第一个球移动到A，最后把C上的球移动到B，过程就是这样：

那么对于m=2的情况就讨论完了，可以轻松解决，接下来就是m=3的情况，这里我举一个比较有代表性的例子

现在我们的问题就是如何把颜色尽可能的集中到一根柱子上去，其实我们对比一下上图m=2的情况，可以看出来如果把 A_3 和 B_3 移动到 C 柱上面，就可以把 A , B 柱处理成 m=2 的情况，然后就可以把 A , B 柱的颜色变成纯色，剩下 C 柱上还有两个异色的分别放到相同颜色的柱子上就行。

想到这里我们欣喜若狂，仿佛找到了正解，于是想继续往下推，看看是否能继续推广，试探 m=4 可以！，再试探一下 m=5 ，突然发现如果要把 A , B 都变成只有两个球，那么 C 柱上就会有六个球，超出了 m=5 的限制，这条路到这里就死了。

于是我们只能另寻他路，再想一想 m>2 和 m=2 有什么相同与不同之处，想啊想，想啊想，相同之处就是只有两种颜色，至于不同之处嘛，哪哪都不同。既然不同之处下不了手，那就从相同之处开始下手。

Step2

相同之处是只有两种颜色，我们应该如何去利用这样的条件呢？开始往往是最难的地方，而一个百试不厌的方法就是去试，多种情况去试试，那么对于 m=3 ，有以下几种情况(其中可以通过颜色互换对称相同的视为同一种)

通过手动模拟可以发现，如果对于两根柱子上同种颜色的球都是连续的情况就可以通过类似 m=2 的方法解决，如图中的①，②，⑦，⑨种情况。我们不妨把这种柱子称作伪纯色柱，那么在 n=2 的情况下，如果两根柱子都是伪纯色柱，解法就很明了了，我们可以把连续一段相同颜色的球看作一个大球，那么就自然而然的转化成 m=2 的情况了。

所以，我们的又一个思路就是把所有杂色柱转变为伪纯色柱，这看起来是不是比直接变成纯色柱要简单一点。我们又对自己有了信心，开始思考有什么办法可以把杂色变成伪纯色。两根柱子一起处理可以吗，思考一下会发现想不到什么好的办法，于是只能想从一根柱子开始处理的办法。

这里我们可以联想到魔方，没错，就是魔方。我们在复原魔方的时候会借助公式一层一层向上拼，同时又能在变化上层色块的时候保持下层色块在转动后回到原位。想到了这个，我们就可以去想一想这道题的结构是不是跟魔方十分相似，都是打乱色块，最后要把色块复原；都是有多种方法,但最后殊途同归。（所以我们可以把这道题目改名为CCF家的新魔方）

好，发现与魔方的相似之处后再来思考一根柱子上的球如何能把相同颜色的放在一起，假设没有任何限制，就是给你一根柱子，让你把上面混乱的两种颜色球使颜色相同的变成连续的。如果是我的话肯定就是把上面的球无脑全部拿下来，同种颜色的放到一块，然后再无脑拼回去。好，此时再回归题目，我们能不能无脑把 A 柱上面的球全部拿下来分类呢？

如果 B 柱不去动他，我们就只能把A柱上的球挨个放到C柱上面，最后 C 柱(活成了 A 柱的模样)就变成了倒过来的 A 柱，对与解题貌似没有任何帮助。

所以，我们不得不去借助 B 柱了，我们要注意在借助 B 柱的时候不能打乱 B 柱原始的顺序，否则到调整 B 柱的时候需要借助 A 柱，如果需要打乱原始顺序的话 A 柱就白整了。

我们先想个法调整，最后再验证是否打乱顺序（这是一类常用的方法，先去满足必要性，再从必要性中一步步去剥充分性）。

联系到上面无限制条件的方法，我们需要借助 B 柱给 A 柱中的某一个颜色腾出空间，让 A 柱上的某一种颜色能全部集中到一根柱子上去。

我们就假设 A 柱上有黑球和白球两种颜色吧，我们不妨记录其中白球的数量为 cnt 个，则黑球的数量就是 m-cnt 个，所以 B , C 柱上一个要留 cnt 个位置，一个要留 m-cnt 个位置，我们不妨把所有白球放到 B 柱上面去，所有黑球放到 C 柱上面去（反正都是对称的），所以我们需要把 B 柱上的前 cnt 个球移动到 C 柱上面，于是乎 B 柱留下了 cnt 个位置， C 柱留下了 m-cnt 个位置。如图：

接着我们从 A 柱上一个一个向外拿球，如果是白球就放到 B 柱，反之放到 C 柱，当 A 柱刚好拿完的时候， B , C 柱也刚好放满。此时 A 柱的白球和黑球被完美分开了，接下来我们只需要先把 B 柱上前 cnt 个来自 A 柱的白球放回 A 柱，接着把 C 柱上前 m-cnt 个黑球放回 A 柱，最后再把 C 柱上来自 B 柱的 cnt 个不知道什么颜色的球放回 B 柱，就完成了一次对 A 柱的完美调整。

由于放球有先进后出的属性，可以轻松验证最后 C 柱上 cnt 个来自 B 柱的球放回到 B 柱的时候排列顺序与从 B 柱拿走的时候不发生任何变化。由此便满足了我们所需要的一种调整方法。

接着对 B 柱用相同的方法进行调整，便可以让 A , B 变成伪纯色柱，再用上文对于伪纯色柱的方法操作就可以了。

到此为止， n=2 的十分就拿到手了，有的选手想到了这一步却没有继续往下做真的很可惜，因为这 10 分的策略其实就是 100 分的策略。

Step3

解决完了两个柱子之间的策略之后其实与最终解法之间就只剩下一层薄薄的膜了（绝不是什么可悲的厚障壁），下面就要去讨论 n 更大的情况，由于我很笨，所以我还是一个个试。

当这样偷懒之后，居然可以分类了！ 我们可以把蓝笔画的分为一类，黑笔画的分为一类，对这两类分析，先选两个柱子，把蓝笔画的颜色看作 $1$ ，黑笔画的颜色看作 $2$ ，把选中的两个柱子整理为关于 $1$ , $2$ 的伪纯色柱，接着可以把 $1$ , $2$ 彻底分开，变成两个 $1$ 的纯色柱和一个 $2$ 的纯色柱，由于 $2$ 只代表一种颜色，所以 $2$ 的那一个纯色柱其实就已经完成了它的使命，接下来再去看 $1$ 的那两根纯色柱，问题就非常明了了，又变回了 $n=2$ 的情况。 到这里，所有迷雾都已经消散，我相信你们都已经看出来了，这已经可以通过分治解决了。 具体策略就很好想了，对于 $n$ 个柱子，把 $1$~$[\frac {n}{2}]$ 视为同一种颜色， $([\frac{n}{2}]+1)$~$n$ 视为同一种颜色，对其进行二分递归，具体操作其他大佬都已经讲过了，这里不再赘述。 # Summary 打完这篇题解，我一直在想，为什么考场上面我上面都没有想出来，如果静下心来好好分析的话至少10分还是可以拿到的，但是一开始就奔着满分去打，导致没有基础思路，无从下手，就像一个平面没有基底向量，什么也构成不了，平时喜欢玩魔方也没有看出这道题其实有魔方的思路在内，更没有发现这道题的思想早在初一上学期的《走一步再走一步》中就已经告诉过我。 一个复杂的问题可以被拆分成若干个简单的小问题。这句耳朵都听吐了的话到了真用上的时候却忘却。 所以，对于一个看起来很复杂的问题，还是要踏踏实实的从最简单的情况开始分析，然后一层一层的往上走，盖高楼大厦从来都是先打好地基，总不能直接从楼顶开始盖吧。 这篇题解更多的是想去把这道题想出来的过程呈现给大家，建立一个思维方式，懂得先走一步，再走一步。 **谨以此题解，祭奠我逝去的2020NOIP** ------------ **update 2020.12.14** 之前有个可以考场上猜出大致思考方向的方法忘记说了，其实ccf已经给过我们提示了，就在大数据答案中： ``` 11 51 11 51 50 51 50 51 50 51 50 51 50 51 50 51 50 51 50 51 50 51 50 51 ``` 我们可以清楚的到有很长一串都是同一根柱子进行相同的操作，事实上这个从 $50$ 转移到 $51$ 的操作一共有 $31$ 次，再往下看就是从 $51$ 移动回 $50$ ， $11$ 移动到 $51$ ，下面的答案也是类似操作，考场上看样例答案也许会有意想不到的启发哟。 ---------