CF2022D2 Asesino (Hard Version) 题解

int08 · 2024-11-06 17:24:48 · 题解

前言

神仙题。

题意

交互题，有 n 个人，其中有一些好人和一些坏人，还有一个内鬼，你每次可以选择问一个人回答另一个人是不是好人，回答如下表：

例如，你问内鬼一个好人是不是好人，他会回答 No。

简单版中，你需要通过 n+69 次询问确定内鬼，困难版中，你需要用尽可能少的次数确定，交互库自适应，所以就等于确定一个策略使最坏情况下次数最少。

Solution

Easy Version

如果不考虑内鬼，发现直接的 Yes 或者 No 带来了很少的信息，你同时交换所有人的身份甚至仍然是对的。

进一步的假如没有内鬼，事实上 Yes 和 No 带来的信息是两个人身份相同 / 不同。

不过内鬼会在相同和不同上露馅，如果两个人互相问问，答案应该是一样的，如果中间有一个内鬼，答案就不同。

所以，我们可以用两次询问确定内鬼是否在某两个人当中。

这样很简单了，我们两个人两个人问，如果确定在这两个人当中，选择这两人中的一个和外面的一个人（此时可以确定不是内鬼）再做一次就可以确定是这两个人中哪一个了。

否则最后必然剩下一到两个人，用一样的方案确定即可。

观察到这种情况下，n 为偶数最坏 n 次询问，n 为奇数时候最坏 n+1 次询问（剩下最后 3 人，用了 4 次才确定），可以通过简单版。

你不会以为这个就能通过困难版了吧。

Hard Version

为啥不是最优啊？

首先感觉一下，最优解应该不可能小于 n，证明见最下面。

看来偶数已经是最优了，奇数还可以优化。

感觉上，奇数的方案上，还剩 3 个的时候两种情况用了 2 和 4 次，不平衡，可以优化。

但是我们穷尽了 n=3 的所有问法，也找不到只用 3 次的，所以为什么还没有 AC？

看来只能是 n\ge 5 时候有优化了。

我们需要避免最后剩三个的情况，考虑一开始就除去三个。

最开始就让 1 问 2，2 问 3，3 问 1，如果没有内鬼，应该全是 Yes 或者一个 Yes 两个 No。

否则说明在他们三个中间，我们再用 4 次确定是谁，否则我们就用 3 次排除了三个人。

这下 n\ge 7 最优了，仍然没有 AC，说明还可以优化 n=5！

发现在他们三个中间的时候，我们再问 4 次中有两次前面问过了，直接用就行，所以只需要 5 次，我们也终于得到了 AC。

AC Code

Link

proof

（翻译自 CF 官方题解）

考虑由查询生成的有向图。根据鸽巢原理，至少有一个节点的入度为 0，至少有一个节点的出度为 0。

• 如果这两个节点不同，则称 A 为入度为 0 的节>点，B 为出度为 0 的节点，存在两种情况满足回答全部是 Yes：

• 如果这两个节点相同，那么图看起来就像是一个循环和一个孤立节点的集合。假设最后一次询问是 A 询问 B，存在两种情况满足回答除了最后一次全是 Yes：

因此，我们已经证明，在 n - 1 个询问中，无论问什么问题，都不可能在 n 个人中找到内鬼。 \blacksquare

The End.