枚举：一个不漏地试

什么是枚举？

枚举（穷举）就是把所有可能一个不漏地试一遍，符合条件的留下。

听起来很笨？但它有两大优点：思路零门槛（会循环就会枚举）、正确性有保障（只要列举完整就不会错）。CSP-J 第二轮前两题往往枚举就能拿分——先拿分，再谈优雅。

枚举的三个要领

1. 选对枚举对象：枚举什么最省事？直接枚举答案本身，通常比绕弯快
2. 范围不重不漏：范围写漏答案丢分，范围写重复浪费时间
3. 能省则省：用题目条件缩小范围、跳过不可能的情况（这叫剪枝）

例题 1：水仙花数

题目描述　水仙花数：一个三位数，它的每个位上的数字的 3 次幂之和等于它本身（如 \(153 = 1^3 + 5^3 + 3^3\)）。输出所有水仙花数。

输入格式　无。

输出格式　若干行，每行一个水仙花数，从小到大。

数据范围　水仙花数是三位数，\(100 \sim 999\)。

思路分析　枚举对象就是答案本身：把 100~999 全部试一遍。三位数拆位用第 2 章的口诀——个位 %10、十位 /10%10、百位 /100。

参考代码

#include <iostream>
using namespace std;

int main() {
    for (int n = 100; n <= 999; n++) {
        int a = n / 100;        // 百位
        int b = n / 10 % 10;    // 十位
        int c = n % 10;         // 个位
        if (a*a*a + b*b*b + c*c*c == n) {
            cout << n << endl;
        }
    }
    return 0;
}

输出 153 370 371 407 四个数。900 次循环瞬间跑完——枚举不怕多，就怕漏。

例题 2：百钱买百鸡

题目描述　公鸡 5 元一只，母鸡 3 元一只，小鸡 1 元三只。用 100 元正好买 100 只鸡，公鸡、母鸡、小鸡各买几只？输出所有方案（公鸡数从小到大）。

输入格式　无。

输出格式　每行三个整数：公鸡、母鸡、小鸡的数量。

数据范围　经典题（源自《张邱建算经》）。

思路分析　三个未知数，枚举公鸡 \(a\) 和母鸡 \(b\) 两层循环，小鸡 \(c = 100 - a - b\) 直接算出来——枚举变量能少一个是一个！然后验证两个条件：钱数恰好 100、小鸡数是 3 的倍数（否则没法按「1 元三只」卖）。

参考代码

#include <iostream>
using namespace std;

int main() {
    for (int a = 0; a <= 20; a++) {          // 公鸡最多 100/5 = 20 只
        for (int b = 0; b <= 33; b++) {      // 母鸡最多 100/3 = 33 只
            int c = 100 - a - b;             // 小鸡：凑够 100 只
            if (c % 3 != 0) continue;        // 小鸡必须按 3 只一组
            if (a * 5 + b * 3 + c / 3 == 100) {
                cout << a << " " << b << " " << c << endl;
            }
        }
    }
    return 0;
}

输出四种方案，如 0 25 75、4 18 78。注意两个细节：

• 循环上限别写 100：公鸡不可能超过 20 只——按预算上限剪枝
• continue 把「小鸡不成组」的情况提前跳过，主条件更清爽

枚举的效率账

数据规模	枚举量	能否接受
\(10^6\)	100 万	✅ 秒过
\(10^8\)	1 亿	⚠️ 1 秒左右，临界
\(10^{10}\)	100 亿	❌ 必超时

做题前先估一估枚举量。超了怎么办？缩小范围（剪枝）、减少枚举维度（像百钱买百鸡那样用公式消元）、或者换算法（后面的贪心、二分都是出路）。

动手试一试

1. 枚举所有四叶玫瑰数：四位数，各位数字的 4 次幂之和等于本身
2. 读入 \(n\)（\(n \le 10^4\)），问 1~n 中有多少个数能被 3 整除但不能被 5 整除（想想：这题需要枚举吗？有没有 \(O(1)\) 公式？——枚举是兜底，动脑有惊喜）
3. 完美立方：读入 \(a\)（\(2 \le a \le 100\)），输出所有满足 \(a^3 = b^3 + c^3 + d^3\)（\(b \le c \le d \le a\)）的写法
4. 挑战：三次循环版百钱买百鸡和两层版，循环次数差多少倍？体会「消去一个维度」的价值

---

下一课：把题目逐句翻译成代码——模拟。