GESP C++ 三级讲义：枚举法

核心目标：理解枚举算法的原理与特点，掌握枚举的三要素（枚举对象、枚举范围、判断条件），能熟练运用单重枚举、双重枚举、逆向枚举解决实际问题，掌握枚举的优化技巧。
枚举就是“把所有可能的情况逐一试一遍，从中找出满足条件的解”；关键在于想清楚“枚举什么、枚举到哪、怎么判断”，并在数据范围允许的前提下做到“不重复、不遗漏”。

一、考纲定位

根据CCF官方考纲，三级的知识目标明确要求：“理解枚举算法、模拟算法的原理及特点，可以解决实际问题”。考核目标进一步指出：“掌握枚举法、模拟法的原理和运用技巧，对于较简单的实际问题能构造算法、描述算法、实现算法并调试程序”。

在三级考试中，枚举法与模拟法并列为核心算法考点，分值占比极高。

三级明确不考的算法（避免浪费时间）：递归算法、排序算法、DFS/BFS、动态规划、贪心算法。

二、枚举算法的原理与特点

1. 什么是枚举法

枚举算法是一种通过列举所有可能的解，逐一检查每个解是否满足问题要求的算法。它的核心思想是遍历所有可能性，找出符合条件的结果，常用于解空间有限且可以直接遍历的场景。

可以把枚举法理解成一种“地毯式搜索”——就像你有一串钥匙但不知道哪把能开锁，最直接的办法就是一把一把地试过去。

2. 枚举法的优缺点

优点	缺点
思路直接，不需要复杂数学推导	解空间大时计算量爆炸
代码简单，容易实现和调试	时间复杂度通常较高
正确性容易保证（不遗漏即可）	需要提前判断数据范围是否允许
适合数据范围小的场景	可能需要优化才能通过

三、枚举法的三要素

枚举算法有三个核心要素，写代码前必须先想清楚：

要素	含义	思考问题
枚举对象	要枚举什么变量	需要尝试哪些量？
枚举范围	变量的取值范围	从哪里开始？到哪里结束？
判断条件	如何验证是否满足要求	什么情况下算“找到了解”？

不重复、不遗漏是枚举法的基本要求。枚举时既不能重复计算同一个解，也不能漏掉任何可能的解。

四、枚举法的基本模板

1. 单重枚举

只枚举一个变量，适用于“遍历某个范围内的数，判断是否满足条件”的问题。

for (int i = 起始值; i <= 结束值; i++) {
    if (判断条件) {
        // 处理结果
    }
}

典型应用：水仙花数、素数判断、完全平方数判断。

2. 双重枚举

枚举两个变量，适用于“从序列中找两个元素”或“组合问题”。

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (判断条件) {
            // 处理结果
        }
    }
}

注意：j 从 i + 1 开始，保证不重复枚举同一对元素。

3. 逆向枚举

当正向枚举困难时，枚举最后一个状态，然后倒推验证是否满足初始条件。

典型应用：小猫分鱼（枚举最后一只猫拿走的鱼数，倒推初始鱼数）。

五、真题精讲

真题1：完全平方数

题目描述：给定n个非负整数序列a，统计有多少对下标组合 (i, j)（i < j）使得 a[i] + a[j] 是完全平方数。

数据范围：n ≤ 1000。

解题思路：数据规模n ≤ 1000，允许O(n²)算法。使用双重循环枚举所有下标对，判断两数之和是否为完全平方数。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[1005];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int s = a[i] + a[j];
            int r = (int)sqrt(s);
            if (r * r == s) {
                cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

关键点：

• j 从 i + 1 开始，避免重复统计同一对。
• 判断完全平方数：int(sqrt(s)) * int(sqrt(s)) == s。
• 时间复杂度 O(n²)，n ≤ 1000 时完全可行。

真题2：寻找倍数

题目描述：给定n个正整数的序列a，判断是否存在一个元素a[i]，使得a[i]是序列中所有其他数的倍数。

数据范围：n ≤ 10⁵。

解题思路：数据规模较大，不能直接双重循环。关键洞察：一个数如果是所有数的倍数，它必然是序列中的最大值。因此只需先找最大值，再验证最大值是否整除所有元素。这是“聪明枚举”的典型体现——将O(n²)的枚举优化为O(n)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[100005];
        int maxv = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] > maxv) maxv = a[i];
        }

        bool found = true;
        for (int i = 0; i < n; i++) {
            if (maxv % a[i] != 0) {
                found = false;
                break;
            }
        }
        if (found) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

关键点：利用“最大值一定是所有数的倍数中最大的可能”这一数学性质，将枚举对象从“所有元素”缩小为“最大值”。

真题3：小猫分鱼

题目描述：n只小猫分鱼。第一只猫把鱼平均分成n份，多了i条，扔掉i条，拿走一份。第二只猫对剩下的鱼同样操作，直到第n只猫。求海滩上最少有多少条鱼。

解题思路：正向枚举初始鱼数非常困难，因为不知道从哪里开始。经典技巧是倒推+枚举：枚举最后一只猫拿走的鱼数k（从1开始），然后倒推每一步，验证是否满足条件。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, i;
    cin >> n >> i;

    long long k = 1;
    while (true) {
        bool flag = true;
        long long ans = k * n + i;    // 最后一只猫面对的数量
        for (int j = 1; j < n; j++) { // 倒推 n-1 次
            if (ans % (n - 1) != 0) {
                flag = false;
                break;
            }
            ans = ans / (n - 1) * n + i;
        }
        if (flag) {
            cout << ans << endl;
            break;
        }
        k++;
    }
    return 0;
}

关键点：当正向枚举困难时，试试逆向枚举。枚举最后一个状态，然后验证是否满足初始条件，这是枚举法中非常高效的技巧。

六、枚举的优化技巧

枚举法的关键技巧往往不在于“枚举”本身，而在于如何“聪明地枚举”——在枚举之前，先动脑筋把需要尝试的范围尽可能缩小。

1. 缩小枚举范围

根据数学性质，跳过不可能满足条件的值。

场景	优化前	优化后
找因子	枚举1~n	枚举1~√n
寻找倍数	枚举所有元素	枚举最大值
鸡兔同笼	枚举鸡和兔两层循环	枚举鸡，兔由头数推出

2. 利用条件剪枝

在循环内部提前判断，不满足就跳过。

for (int i = 1; i <= n; i++) {
    if (i % 2 != 0) continue;   // 只枚举偶数，跳过奇数
    // 处理偶数的情况
}

3. 枚举对象的选择

有时枚举“差值”或“分割点”比枚举“元素”更高效。

真题示例：平衡序列 ：需要判断序列能否被分割为左右两部分，使得两部分的元素和相等。如果枚举所有分割点，需要O(n)次；每次判断左右和相等，可以预先计算前缀和，将每次判断优化为O(1)，总时间复杂度降为O(n)。

七、枚举法与模拟法的区别

对比项	枚举法	模拟法
核心思想	遍历所有可能，用条件筛选	按规则逐步复现过程
适用场景	解空间有限，答案可枚举	有明确的规则和流程
代码结构	多层循环 + 条件判断	循环 + 状态更新
关键难点	确定枚举范围和优化	忠实复现每一步规则
典型题目	完全平方数、寻找倍数	数组清零、日期推进

八、易错点汇总

1. 枚举范围错误

• 枚举范围过大：可能超时，需要提前估算数据规模。
• 枚举范围过小：可能遗漏解，需要仔细分析边界。
• 边界值未考虑：如n=0、n=1、空序列等。

2. 重复枚举

// ❌ 重复枚举：每个组合被算了两次
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) { ... }

// ✅ 正确：j 从 i+1 开始，不重复
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) { ... }

3. 忘记判断特殊情况

// 完全平方数判断时，sqrt返回浮点数，可能有精度误差
int r = (int)sqrt(s);
if (r * r == s) { ... }   // ✅ 用整数乘法验证

4. 循环变量作用域混淆

for (int i = 0; i < n; i++) { }
cout << i;   // ❌ 错误，i 只在循环内有效

5. 数据范围估计错误

写代码前必须先估算：枚举次数是多少？是否会超时？

数据规模	允许的枚举复杂度
n ≤ 100	O(n³)
n ≤ 1000	O(n²)
n ≤ 10⁵	O(n) 或 O(n log n)

6. 逆序枚举时变量更新顺序错误

逆向枚举时，每一步的更新顺序很关键，写错一步会导致整个倒推失败。

7. 输出格式错误

注意空格、换行、大小写，严格按题目要求输出。

九、速查表

需求	写法	关键注意
单重枚举	for (i = 起; i <= 止; i++) if (条件) ...	确定枚举范围
双重枚举	for (i) for (j = i+1) if (条件) ...	j 从 i+1 开始
逆向枚举	for (k = 1; ; k++) { 倒推验证 }	正向困难时使用
枚举优化	缩小范围、剪枝、利用数学性质	先估算复杂度
完全平方数	int r = sqrt(s); if (r * r == s)	用整数乘法验证
找因子	枚举 1~√n	利用因子成对性质
鸡兔同笼	枚举鸡，兔 = 总数 - 鸡	减少一重循环

十、总结

枚举法是GESP三级最核心的算法思想，也是编程题中占比最高的考点。

1. 枚举法的核心是“遍历所有可能，用条件筛选”。
2. 三要素：枚举对象、枚举范围、判断条件。
3. 不重复、不遗漏是枚举的基本要求。
4. 写代码前先估算数据规模，判断枚举复杂度是否可行。
5. 双重枚举时内层从 i+1 开始，避免重复。
6. 正向枚举困难时，试试逆向枚举（小猫分鱼）。
7. 利用数学性质缩小枚举范围（寻找倍数→枚举最大值）。
8. 枚举次数过多时，考虑剪枝或改变枚举对象。
9. 完全平方数判断用 r * r == s，不要用浮点数比较。
10. 多练真题，熟悉“组合枚举”“极值枚举”“逆向枚举”“分割点枚举”四类模型。

复习建议：先从水仙花数、鸡兔同笼等经典入门题开始，掌握单重和双重枚举的基本写法；再练习“完全平方数”“寻找倍数”两道真题，体会组合枚举和优化枚举的差别；最后挑战“小猫分鱼”“平衡序列”等需要逆向思维和分割点枚举的题目。考试中先读懂题目，确定枚举对象和范围，估算复杂度是否可行，再写循环和条件判断。