自动搬运

查看原文

来自洛谷，原作者为

	vzcx_host vzcx 系列第一站

搬运于2025-08-24 23:02:04，当前版本为作者最后更新于2024-08-31 18:18:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

本题解中将选手分别编号为 $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$ 是奇数，将多余的选手视为一对异色对即可。

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