P10873 Solution

· · 题解

写一个可以在现实中使用的策略。

本题解中将选手分别编号为 0\sim n-1。

假设 0 猜 \verb|B|，对于 1 来说，他知道 0 会猜 \verb|B|，所以他不管怎样都会猜 \verb|C|，因为在这种状态下，即使两个人都猜错也满足下取整条件。

那么考虑 2，如果 0 和 1 都猜错，他自己必须要猜对，然而在没有别的信息的情况下，他无论如何都不可能百分百猜对。所以我们回头，让 0 去猜 2 的颜色，这样 2 只需要在猜 0 相反的颜色，在 0 和 1 都猜错的前提下 2 一定会猜对。

考虑 3，如果 0 和 1 猜错 2 猜对，2 相反的颜色还卡在奇数下取整，所以 3 只能猜这个颜色。如果 2,3 颜色相反，3 猜对，0,1,2,3 猜测互相抵消；如果 2,3 颜色相同，3 猜错，两种颜色全部回到奇数下取整，此时 4 无法准确地猜颜色。

但是 0,1 是知道 2,3 颜色的，如果他们看到 2,3 颜色相同，他们知道给 2,3 提供信息无法抵消他们的错误猜测，而如果某一对选手颜色相同，只要他们猜的是相反的，他们就必定一对一错，不需要在意他们接收到的信息是不是对的。所以 0,1 会去找后面第一对颜色不同的选手去和他们配合，而他们也看得到他们和 0,1 中间所有的选手对颜色相同，他们知道自己在和 0,1 配合。

到这里做法就很显然了，将选手两两分组，每组选手组内的猜测不同。对于某一组选手，如果他前面有奇数对异色对，尝试和最后一组选手配合；否则，尝试和后面第一对异色对配合。

如果 n 是奇数，将多余的选手视为一对异色对即可。

一组同色对必定一对一错，两组配合的异色对必定一组全对一组全错，最多会多出一组异色对，此时刚好取到奇数下取整，整个做法完全正确。