CSP-J 入门级 · CSP 2025 入门级第一轮 第 20 题

（2）（精明与糊涂）有 $N$ 个人，分为两类： i) 精明人：永远能正确判断其他人是精明还是糊涂； ii)糊涂人：判断不可靠，会给出随机的判断。

已知精明人严格占据多数，即如果精明人有 $k$ 个，则满足 $k > N/2$。

你只能通过函数 $\text{query}(i, j)$ 让第 $i$ 个人判断第 $j$ 个人：返回 $\text{true}$ 表示判断结果为“精明人”；返回 $\text{false}$ 表示判断结果为“糊涂人”。你的目标是，通过这些互相判断，找出至少一个百分之百确定的精明人。同时，你无需关心 $\text{query}(i, j)$ 的内部实现。

以下程序利用“精明人占多数”的优势。设想一个“消除”的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选人必然属于多数派，即精明人。

例如，假设有三人 $0, 1, 2$。如果 $0$ 说 $1$ 是糊涂人，而 $1$ 也说 $0$ 是糊涂人，则 $0$ 和 $1$ 至少有一个是糊涂人。程序将同时淘汰 $0$ 和 $1$。由于三人里至少有两个精明人，我们确定 $2$ 是精明人。

试补全程序。

#include <iostream>
#include <vector>
using namespace std;

int N;
bool query(int i, int j);

int main() {
    cin >> N;

    int candidate = 0;
    int count = __①__;
    for (int i = 1; i < N; ++i) {
        if (__②__) {
            candidate = i;
            count = 1;
        } else {
            if (__③__) {
                __④__;
            } else {
            cou

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题本质是多数投票算法的变体：利用‘两人互相指责必有一糊涂’的性质成对抵消，最后剩下的候选人就是精明人。

最容易把③处的判断条件写错成‘两人互相指责’（AND），那样会漏掉很多可以抵消的情况；或者把①初始count写成0，导致第一轮就错误地重置候选人；还有人会纠结于‘必须两人互相说对方糊涂才能淘汰’，其实只要有一人说对方是糊涂，两人中至少有一个是糊涂人，就可以安全淘汰。

这道题考查什么

这道题考查的是多数投票算法（Boyer-Moore）在逻辑判断场景下的变体应用。核心思想不是统计票数，而是利用‘精明人占多数’这一条件，通过两两配对抵消，最终留下的必然是精明人。

概念：什么是‘多数投票’

在数组中找出现次数超过一半的元素，经典做法是：不同元素互相抵消。比如 A 和 B 不同，就同时扔掉；最后剩下的就是多数元素。这里的‘不同’对应到本题就是‘两人中至少有一个是糊涂人’。

命题人怎么挖坑

命题人放了几个经典陷阱： 1. ①初始 count 值：很多人直觉是 0，因为还没开始计数。但算法要求先假设第一个人是候选人，所以 count 必须从 1 开始。 2. ③判断条件：最容易错的是把 OR 写成 AND。题目只要求‘两人中至少有一个糊涂’，而‘互相指责’是充分不必要条件，写 AND 会漏掉大量可抵消的情况。 3. ④抵消操作：抵消意味着两人同时出局，所以 count 要减 1，而不是 break 或加。

思考心法：拿到题先想什么

拿到这种‘找多数’的题，先想：能不能成对抵消？如果能，抵消规则是什么？抵消后剩下的性质是什么？ 本题抵消规则：只要 query(candidate, i) == false 或 query(i, candidate) == false，就说明两人中至少有一个是糊涂人，就可以一起淘汰。 抵消后剩下的候选人，因为精明人数量 > N/2，糊涂人先被抵消完，最后留下的必然是精明人。

逐空推演

①处应填什么？ 程序开头 int candidate = 0; 已经选定 0 号作为初始候选人。按照多数投票算法，此时 count 表示当前候选人的‘净优势’，初始应为 1（假设候选人是多数派）。所以①选 B. 1。

②处应填什么？ 遍历过程中，如果 count 变成 0，说明当前候选人已经被抵消光了，必须换新人。所以②选 C. count == 0。

③处应填什么？ 这是关键。题目要求‘两人中至少有一个是糊涂人’即可抵消。query(candidate, i) == false 表示候选人说 i 是糊涂；query(i, candidate) == false 表示 i 说候选人是糊涂。只要有一个为 true，就满足条件。所以是 OR 关系，选 D. query(candidate, i) == false || query(i, candidate) == false。 （如果写成 AND，就要求两人互相指责，太严格了，会漏掉很多可抵消的情况。）

④处应填什么？ 抵消意味着两人同时出局，所以 count 要减 1，选 A. count--。

⑤处应填什么？ 循环结束后，candidate 就是最后剩下的多数派元素，也就是精明人，选 C. candidate。

避坑：具体错在哪

• ①错成 0：会导致第一轮就错误地重置候选人，算法失效。
• ③错成 AND：会漏掉大量可抵消的情况，导致最终候选人可能是糊涂人。
• ④错成 break：一旦遇到可抵消就跳出循环，后面还有人没处理，结果错误。
• ④错成 count++：抵消时反而增加计数，逻辑完全相反。

考频与趋势

根据题库数据，枚举法共考过 159 题，覆盖 9 个级别，逐年分布：2009 年 1 题、2020 年 1 题、2021 年 1 题、2022 年 1 题、2023 年 5 题、2024 年 6 题、2025 年 6 题、2026 年 13 题、null 年 125 题。其中 CSP 入门级就考了 133 题，说明这类‘找多数/找最优’的枚举思想在入门阶段非常高频。

DFS共考过 61 题，覆盖 7 个级别，逐年分布：2009 年 1 题、2010 年 1 题、2013 年 3 题、2020 年 2 题、2021 年 1 题、2022 年 1 题、2023 年 6 题、2024 年 13 题、2025 年 9 题、2026 年 22 题、null 年 2 题。虽然 DFS 本身不是本题考点，但可以看出搜索类题目在近年（尤其是 2024-2026）考频上升明显，命题人越来越喜欢把‘搜索’和‘贪心/投票’结合出题。

预测未来怎么考

基于数据趋势：

• 枚举/投票类题目在 CSP 入门级持续高频，2026 年已出现 13 题，未来可能继续以‘找多数’‘找最优’‘找满足条件的最小/最大’等形式出现，难度略有提升（例如增加多轮投票或动态更新候选人）。
• DFS 类题目在 2024-2026 年考频显著上升（2026 年 22 题），未来可能会把‘投票抵消’和‘搜索’结合，比如先投票缩小范围，再在剩余候选人中搜索最优解。

暂无足够依据预测更具体的题型细节，但总体方向是：从单一投票扩展到多轮、动态或结合搜索的复合问题。