QOJ5090 妙妙题

· · 个人记录

题目链接。

题意

有 n 个人围坐在一个圆桌旁，每个人头上有一顶帽子，颜色为黑色或白色。

每个人都能看见其他人头上的帽子而不知道自己头上的帽子，在所有人完成观察后，所有人需要同时猜测自己头上帽子的颜色。

你需要给所有人制定对应的策略，使得每个人可以根据其他所有人的帽子颜色按照顺时针的顺序形成的颜色序列确定自己的帽子颜色。

注意：每个人都不能知道其它的信息，而只能知道对应的颜色序列。

你的策略不需要让所有人都猜对其帽子颜色，只需要使得其中至少有 \lfloor\dfrac{n-1}{2}\rfloor 个人猜对即可。

数据范围：n\le 64。

下面是一个例子：

 0
1 0
 0

在这里，我们用 0 表示白帽子，1 表示黑帽子。

你可以设计如下策略：

这样的策略能够让上述例子中的四个人都猜对，但不一定会对于所有情况均满足条件。

题解

先考虑一个弱化版本，如果每个人知道自己的编号会怎样？

这个时候考虑限制是一半的人猜对，那么把人分成两半，一半一定对，一半一定错是符合要求的。

怎样构造一半对一半错？考虑可以设置一个要么对要么错的条件，一半假设该条件成立，另一半假设其不成立。

可以构造这样的条件为“黑帽子的总数为奇数”，如此设置一半的人认为总数为奇数，另一半认为总数是偶数，可以发现必然有一半正确。

由这个结论显然可以推断自己帽子的颜色，于是至少有 \lfloor\dfrac{n}{2}\rfloor 的人猜对。

再考虑现在的问题，我们显然不能够直接分组，如果分组了就会导致我们的策略无法构造，因为不同的组对于同一个颜色序列的反应是不同的。

思考一下，如果我们此时想要分组，唯一的依据就是颜色序列，如果能够根据颜色序列来分组，我们就可以套用之前的解法解决此题。

人类智慧地，我们利用目前已知的所有黑帽子的人的信息来划定分组依据。

具体地，考虑所有人位于单位圆的 n 等分点上，每个人就是一个向量。

将所有帽子颜色为黑色的人的向量相加，得到的最终向量设为 \bold{v}，显然我们可以利用其把所有人划分成两边。

这样我们达成了分组的目的，套用之前的解法即可。