ARC070D HonestOrUnkind

题意 ： 有 个人，有 个人是好人，剩下的 个人是坏人。

这 个人都互相知道各自的身份，试图通过询问来得知他们的身份。

你可以指定两个人 ，并向 询问 是否是诚实的。

• 如果 是好人，那么他会按照事实返回答案，也就是说如果 是好人，答案就为 ，否则为 。

• 如果 是坏人，那么他会任意选择 和 来回答。

在 次询问内确定 个人的身份，或指出不可能。

。

---

若 则无解。此时若 个坏人装作好人，且将其他人视为坏人，则无法将他们与 个真正的好人区分开来。

于是我们只需处理 的情况。

当 时，显然只可能是 ，故仅有的一个人一定是诚实的。

对于询问 ，可能的答案有 种，两人的状态也有 种。

列表如下：

(好,好)
(好,坏)
(坏,好)
(坏,坏)

• ： 两人中至少有一个是坏人。

• ： 必是坏人。

• ： 必是坏人。

• ： 是同类人。

如果得到了 ，则转化为 减一的子问题。

若得到 ，则将两人同时暂时取出。这样得到的子问题中也满足 ，处理完子问题后，抓一个诚实的人验明两人正身。

这样，两人没人的花费都为 ，符合题目要求。

对于 ，则将两人连接。

现在有个麻烦，若将连接后的一群人直接看做一个人，则可能不满足 的性质。

于是，我们不化简一群人，同时避免成群的人参与询问，因为问出个 就要把这群人暂时删除，也可能破坏性质。

于是，在一轮处理后，所有剩下的人都两两配对了，此时才能把两个人化简为一个人，继续处理。

有个小问题是可能剩余一个人没有配对。此时若对子有偶数个则将其保留，否则暂时删除。（讨论 的情况即可）

不难证明上述算法所需的询问次数 。

注意标号从 开始 ！！！