D2. 杀手（困难版本）详细题解

1. 问题回顾

• 与 D1 相同的问题，但要求使用最少询问次数 $f(n)$
• 已知 $f(3) = 4$，$f(n) \le n$ 对于 $n \ge 4$
• 目标是实现一个使用 $\le f(n)$ 次询问的策略

2. 关键引理

将询问建模为有向图：对每次询问 $i \to j$，定义边权：

• $w(i,j) = 0$ 如果回答是"是"（$1$）
• $w(i,j) = 1$ 如果回答是"否"（$0$）

引理：一个环上的边权之和为奇数 $\iff$ 内鬼在环上。

证明思路：

• 骑士和恶棍在环上交替出现时，边权模式有规律
• 内鬼的存在会改变奇偶性
• 可以通过枚举所有可能的角色分配验证

3. 算法策略

3.1 基本情况

• $n = 3$：需要 $4$ 次询问（已知下界）
• $n = 4$：需要 $4$ 次询问
• $n = 5$：需要 $5$ 次询问

3.2 归纳步骤（$n > 5$）

while n > 5:
    询问 n → n-1 和 n-1 → n
    if 回答不同:
        // 内鬼在 {n-1, n} 中
        询问 n → n-2 和 n-2 → n
        if 回答不同:
            内鬼 = n
        else:
            内鬼 = n-1
        return
    else:
        n -= 2  // 两人都不是内鬼，安全移除

3.3 处理剩余规模

• 如果 $n = 4$：用 $4$ 次询问解决
• 如果 $n = 5$：用 $5$ 次询问解决

4. 下界证明思路

要证明 $f(n) \ge n$（对于 $n \ge 4$）：

1. 考虑任意 $n-1$ 次询问的交互图
2. 由鸽巢原理，存在入度为 $0$ 的节点 $A$ 和出度为 $0$ 的节点 $B$
3. 构造两种角色分配：
   • $A$ 是内鬼，其余都是恶棍
   • $B$ 是内鬼，其余都是骑士
4. 这两种分配对所有询问的回答相同
5. 因此无法用 $n-1$ 次询问区分，所以 $f(n) \ge n$

对于奇数 $n$，还需要证明 $f(n) > n-1$，实际上 $f(n) = n$。

5. $n=5$ 的解法

$n=5$ 可以用 $5$ 次询问解决，具体策略：

1. 询问 $1 \to 2$ 和 $2 \to 1$
2. 如果不同，内鬼在 $\{1,2\}$ 中，再用两次询问确定
3. 如果相同，询问 $3 \to 4$ 和 $4 \to 3$
4. 根据结果模式判断

详细逻辑见代码。

6. 算法复杂度

• 每次循环减少 $2$ 个玩家，使用 $2$ 次询问
• 最多 $\lfloor n/2 \rfloor$ 次循环
• 最后处理 $n=4$ 或 $n=5$ 需要常数次询问
• 总询问次数 $\le n$

7. 代码实现要点

int query(int a, int b) {
    cout << "? " << a << " " << b << endl;
    int r; cin >> r;
    return r;
}

void answer(int a) {
    cout << "! " << a << endl;
}

关键：

• 每次询问后刷新输出
• 处理 $n=3$ 作为特例
• 对于 $n>3$，成对处理直到规模缩小到 $4$ 或 $5$

8. 总结

核心思想：

1. 双向询问可以检测内鬼
2. 成对排除非内鬼玩家
3. 小规模直接解决
4. 总询问次数达到理论下界 $n$