信息学竞赛 C++ 教材

Appearance

第 32 章 暴力出奇迹——枚举进阶 ​

🏗️ 前情回顾：在 M2 模块你第一次接触了枚举——用循环把所有可能的情况试一遍。你学会了用 for 循环枚举一个范围内的所有数，也体验过"模拟"的威力。但那时你只枚举单一变量，遇到排列、子集、多变量组合就束手无策了。这一章，我们要给枚举装上"涡轮引擎"——排列枚举、子集枚举、剪枝优化，让暴力算法也能跑出奇迹！

🎯 本章目标 ​

学完这一章，你能：

  • 用 next_permutation 优雅地枚举全排列
  • 用二进制枚举高效遍历所有子集
  • 掌握多重循环枚举的优化技巧（减少层数、缩小范围）
  • 理解剪枝思想——提前排除不可能的情况
  • 用枚举进阶技巧解决三连击、火柴棒等式、回文日期等经典问题

📖 故事引入 ​

小明在玩一个猜密码的游戏。密码是 1~9 的三位数字，不能重复，而且三个数字之和等于 15。他想知道有多少种可能的密码。

如果是你，你会怎么找？最直接的想法：用三个循环，for (int a=1; a<=9; a++)、for (int b=1; b<=9; b++)、for (int c=1; c<=9; c++)，然后判断 a != b && b != c && a != c && a+b+c == 15。这确实能出答案，但如果题目变成"1~9 的九位数，相邻位差大于 2"呢？九重循环？那代码会写成灾难！

聪明人想到的是：先生成 1~9 的所有排列，然后逐一检查。排列的数量是 9! = 362880，远远少于九重循环的 9⁹ ≈ 3.87 亿。更重要的是，排列天然保证了"不重复"这一条件，省掉了大量判断。

这就是枚举进阶的核心：不是傻傻地遍历所有组合，而是用更聪明的"生成方式"精准覆盖所有可能。

🧱 知识讲解 ​

32.1 排列枚举：next_permutation ​

在 C++ 中，<algorithm> 提供了 next_permutation 函数，它能按字典序生成一个序列的"下一个排列"。如果你从最小的排列开始反复调用它，就能遍历所有排列。

📦 类比：想象你有 3 张牌：A、B、C。把它们排成一行有 6 种排法。next_permutation 就像一个"自动翻牌机"——你把牌放上去，它自动翻到"下一个字典序"的排列。

基本用法：

cpp
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a[] = {1, 2, 3};
    do {
        // 处理当前排列 a[0], a[1], a[2]
        cout << a[0] << " " << a[1] << " " << a[2] << endl;
    } while (next_permutation(a, a + 3));
    return 0;
}

输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

⚠️ 关键细节：next_permutation 要求初始数组必须是升序排列，这样才能遍历所有排列。如果初始是降序，它只会生成当前排列之后的那几个。

next_permutation 的返回值：如果生成了下一个更大的排列，返回 true；如果当前已经是最"大"的排列（如 3 2 1），没有下一个了，返回 false，同时将数组重置为最小的排列。所以 do-while 循环是最自然的写法。

用排列解决"三连击"问题：

题目：将 1~9 这九个数字分成三个三位数，使得第二个数是第一个数的 2 倍，第三个数是第一个数的 3 倍。求所有分法。

cpp
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    do {
        int x = a[0] * 100 + a[1] * 10 + a[2];   // 第一个三位数
        int y = a[3] * 100 + a[4] * 10 + a[5];   // 第二个三位数
        int z = a[6] * 100 + a[7] * 10 + a[8];   // 第三个三位数
        if (y == 2 * x && z == 3 * x) {
            cout << x << " " << y << " " << z << endl;
        }
    } while (next_permutation(a, a + 9));
    return 0;
}

9! = 362880 种排列，对计算机来说眨眼间就能全部检查完（实际上大部分排列根本不符合倍数关系，但枚举全排列依然秒出结果）。这就是"暴力出奇迹"——不必找数学规律，靠遍历也能拿下！

32.2 子集枚举：二进制枚举 ​

很多问题需要枚举一个集合的所有子集。比如有 n 个物品，每个物品可以"选"或"不选"，共有 2ⁿ 种方案。

📦 类比：n 个开关，每个开关可以开（1）或关（0）。用二进制数来表示所有开关的状态——从 000...0（全关）到 111...1（全开）。每遍历一个二进制数，就对应一个子集。

核心技巧：用一个整数 mask 从 0 到 (1 << n) - 1，它的二进制表示中第 i 位为 1 表示选第 i 个元素。

cpp
int n = 4;  // 4 个元素
for (int mask = 0; mask < (1 << n); mask++) {
    cout << "子集 " << mask << ": ";
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) {  // 第 i 位是不是 1？
            cout << i << " ";   // 选了第 i 个元素
        }
    }
    cout << endl;
}

输出（部分）：

子集 0:          // 空集（二进制 0000）
子集 1: 0        // 二进制 0001，选第 0 个
子集 3: 0 1      // 二进制 0011，选第 0 和第 1 个
子集 7: 0 1 2    // 二进制 0111
子集 15: 0 1 2 3 // 二进制 1111

位运算速查：

操作代码含义
判断第 i 位是否为 1mask & (1 << i)非 0 即表示该位为 1
把第 i 位设为 1`mask(1 << i)`
把第 i 位设为 0mask & ~(1 << i)移除一个元素
翻转第 i 位mask ^ (1 << i)0 变 1，1 变 0

32.3 多重循环枚举优化 ​

有时候不得不用多重循环枚举，但可以大幅优化。

技巧 1：缩小枚举范围。如果已知 a + b + c = 100 且 a ≤ b ≤ c，则：

  • a 的范围不是 1~100，而是 1~33（因为 a ≤ 100/3）
  • b 的范围是 a ~ (100-a)/2
  • c 直接由 c = 100 - a - b 算出，不需要第三层循环！
cpp
for (int a = 1; a <= 33; a++) {
    for (int b = a; b <= (100 - a) / 2; b++) {
        int c = 100 - a - b;
        // 处理 (a, b, c)
    }
}

技巧 2：利用已知条件直接计算最后一层。三重循环变两重，效率从 O(n³) 降到 O(n²)。

📦 类比：你知道总花费是 100 元，已经花了 a 元买书、b 元买笔，那剩下来的 c 元就是找零——不需要再去"试遍"c 的所有可能值。

32.4 枚举顺序优化 ​

有时候枚举的顺序比枚举本身更重要。比如"火柴棒等式"问题：

题目：给你 n 根火柴棒，你要拼出 A + B = C 的等式，每个数字需要一定数量的火柴棒（如 1 需要 2 根，2 需要 5 根……）。A、B、C 都是非负整数（如果 A=0 允许，但通常有具体限制），等式中的"+"和"="各需要 2 根火柴。求能拼出的等式个数。

分析思路：

  • 先建一个数组 cost[10] 记录每个数字 0~9 需要的火柴棒数
  • 写一个函数 int need(int x) 计算数字 x 需要的火柴棒总数（逐位拆解）
  • 枚举 A 和 B，计算 total = need(A) + need(B) + need(A+B) + 4（4 是 "+" 和 "="）
  • 当 total == n 时找到一个等式

优化点：A 和 B 的范围不是到 n 那么大——因为随着数字变大，需要的火柴棒急剧增加，A+B 最多到 1111（经验值，取决于火柴棒分配），A 和 B 各自不超过 1000。合理剪枝能大幅缩小范围。

32.5 剪枝枚举 ​

剪枝就是在枚举过程中提前剔除不可能的分支，不用走到最后才发现"白忙活了"。

📦 类比：你在图书馆找一本红色的书。如果走到历史区看到全是蓝色封面的书，你就可以直接跳过这一排书架，不用每一本都抽出来查看封面——这就是"剪枝"。

回文日期问题：

题目：给定起止日期（如 20200101 到 20201231），求这个时间段内有多少个日期是回文日期（正读反读都一样，如 20200202）。

直接思路：枚举每一天，判断是否回文。一年最多 366 天，看似不多；但如果跨度 1000 年，枚举每一天就慢了。

剪枝思路：只枚举回文日期！一个 8 位回文日期的前 4 位决定后 4 位（如前 4 位是 2020，回文就是 20200202）。所以枚举年份（前 4 位），直接构造回文日期，然后判断这个日期是否合法（月份 1~12，日期在该月的有效范围内），如果在给定区间内就计数。

cpp
int days[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isValid(int date) {
    int y = date / 10000, m = (date / 100) % 100, d = date % 100;
    if (m < 1 || m > 12) return false;
    if (d < 1) return false;
    // 闰年判断（简化版）
    bool leap = (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
    int maxd = days[m];
    if (m == 2 && !leap) maxd = 28;
    return d <= maxd;
}

int solve(int start, int end) {
    int cnt = 0;
    for (int year = start / 10000; year <= end / 10000; year++) {
        // 用年份构造回文日期
        int rev = 0, tmp = year;
        for (int k = 0; k < 4; k++) {
            rev = rev * 10 + tmp % 10;
            tmp /= 10;
        }
        int date = year * 10000 + rev;
        if (date >= start && date <= end && isValid(date)) {
            cnt++;
        }
    }
    return cnt;
}

这个剪枝把复杂度从"枚举每天"变成了"只枚举年份"，1000 年只需要 1000 次检查。

✋ 动手试试 ​

试试 1：输入 n（1 ≤ n ≤ 8），用 next_permutation 输出 1~n 的所有全排列，每行一个。

试试 2：输入 n 个互不相同的整数，写程序输出这 n 个整数中所有和为 0 的子集（用二进制枚举）。

试试 3：改进"回文日期"的代码，让它能正确处理闰年判断，并统计给定区间内所有回文日期。

⚠️ 容易犯的错 ​

错 1：用 next_permutation 时初始数组没排序 ​

❌ int a[] = {3, 1, 2}; 然后 do { ... } while (next_permutation(a, a+3)); ——只会输出 3 个排列而不是 6 个。

✅ 先用 sort(a, a+3); 保证升序。

错 2：二进制枚举时循环条件写错 ​

❌ for (int mask = 0; mask < (1 << n); mask++) 中的 1 << n 在 n = 30 时可能溢出 int。

✅ 当 n > 30 时使用 1LL << n（long long 的 1）。

错 3：剪枝条件写反了 ​

❌ 想剪掉"不符合"的分支，却写成 if (条件) continue; ——把符合条件的跳过了。

✅ 剪枝逻辑：if (!条件) continue; 或者 if (条件) { 继续枚举 }。

错 4：多重循环中范围写太大 ​

❌ for (int a = 0; a <= 100; a++) for (int b = 0; b <= 100; b++) for (int c = 0; c <= 100; c++) ——100 万次循环，虽然不算多，但如果 n 变大就炸了。

✅ 缩小每层循环的范围，能用公式算的变量不要单独循环。

📝 练习 ​

基础题 ​

1. 选择题

（1）next_permutation 要求初始序列是：
A. 降序   B. 升序   C. 随机序   D. 无要求

（2）用二进制枚举 n 个元素的子集，需要循环多少次？
A. n   B. n!   C. 2ⁿ   D. n²

（3）"剪枝"的含义是：
A. 删除多余的代码   B. 提前排除不可能的情况   C. 优化输出格式   D. 使用更快的编译器

2. 填空题

（1）1 << 3 的二进制值是 ____，十进制是 ____。

（2）判断整数 mask 的第 i 位是否为 1 的表达式是 ____。

（3）next_permutation 的返回值表示 ____。

提高题 ​

3. 编程题 — 全排列输出

输入 n 个互不相同的字符，用排列枚举输出它们的所有排列，按字典序。

4. 编程题 — 火柴棒等式（简化版）

已知数字 0~9 需要的火柴棒数分别为：6, 2, 5, 5, 4, 5, 6, 3, 7, 6。"+"和"="各需要 2 根。输入 n（≤ 24），求能拼成 A + B = C 的等式个数（A、B、C ≥ 0，不带前导零除非本身就是 0）。

挑战题 ​

5. 编程题 — 子集和问题

输入 n 个整数和 target，输出所有和为 target 的子集（每个子集输出一行，元素用空格分隔）。

6. 编程题 — 回文日期（进阶）

输入起始日期和结束日期（格式 YYYYMMDD），输出该区间内第一个回文日期、回文日期总数，以及是否存在形如 ABABBABA 的回文日期（前 4 位 = 后 4 位的翻转，且年、月、日格式中都满足）。

🧠 本章小结 ​

枚举进阶 = 聪明的"暴力"

排列枚举：
  next_permutation —— 字典序遍历全排列，初始必须升序

子集枚举：
  二进制 mask 0 → 2ⁿ-1，每一位对应一个元素的选/不选

多重循环优化：
  缩小范围 + 用公式计算最后一层

剪枝枚举：
  在搜索过程中提前淘汰不合格分支
  回文日期：只枚举年份构造日期，复杂度 O(年份数)

经典题：三连击（排列）、火柴棒等式（枚举+代价计算）、回文日期（构造+剪枝）

📝 配套练习 ​

共9题。排列/组合/剪枝三大武器各3题覆盖。。★核心（课堂必做） ◆拓展（课后练习）

级别题号链接覆盖知识点
★ 核心luogu-P1088https://hydro.ac/p/luogu-P1088next_permutation、火星文
◆ 拓展luogu-P1157https://hydro.ac/p/luogu-P1157组合、回溯、next_perm
◆ 拓展luogu-P1036https://hydro.ac/p/luogu-P1036组合枚举、质数判、剪枝
◆ 拓展luogu-P1706https://hydro.ac/p/luogu-P1706next_permutation、全排列
◆ 拓展luogu-P1158https://hydro.ac/p/luogu-P1158枚举、导弹拦截、贪心启蒙
◆ 拓展luogu-P1011https://hydro.ac/p/luogu-P1011枚举、斐波那契推、车站
◆ 拓展luogu-P1047https://hydro.ac/p/luogu-P1047枚举、区间标记、差分思想
◆ 拓展luogu-P1464https://hydro.ac/p/luogu-P1464枚举+记忆化、三元递归
◆ 拓展luogu-P1008https://hydro.ac/p/luogu-P1008三连击（组合枚举视角重做）

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 8 道◆拓展题，覆盖不同变式和细节。

配套练习 ​

共9题。排列/组合/剪枝三大武器各3题覆盖。★核心（课堂必做） · ◆拓展（课后练习）

级别题号链接覆盖知识点
★ 核心luogu-P1088https://hydro.ac/p/luogu-P1088next_permutation、火星文
◆ 拓展luogu-P1157https://hydro.ac/p/luogu-P1157组合、回溯、next_perm
◆ 拓展luogu-P1036https://hydro.ac/p/luogu-P1036组合枚举、质数判、剪枝
◆ 拓展luogu-P1706https://hydro.ac/p/luogu-P1706next_permutation、全排列
◆ 拓展luogu-P1158https://hydro.ac/p/luogu-P1158枚举、导弹拦截、贪心启蒙
◆ 拓展luogu-P1011https://hydro.ac/p/luogu-P1011枚举、斐波那契推、车站
◆ 拓展luogu-P1047https://hydro.ac/p/luogu-P1047枚举、区间标记、差分思想
◆ 拓展luogu-P1464https://hydro.ac/p/luogu-P1464枚举+记忆化、三元递归
◆ 拓展luogu-P1008https://hydro.ac/p/luogu-P1008三连击（组合枚举视角重做）

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 8 道◆拓展题，覆盖不同变式和细节。

自查清单：

  • [ ] 我能用 next_permutation 生成全排列并用于解题
  • [ ] 我能用二进制枚举遍历子集
  • [ ] 我理解位运算在枚举中的基本用法（<<、&、|）
  • [ ] 我会缩小多重循环的范围，用公式替代最后一层循环
  • [ ] 我理解剪枝思想并能应用到实际问题
  • [ ] 我能独立解决三连击、火柴棒等式、回文日期这三道题

🚀 下章预告：枚举是"生成"可能性然后检查，模拟则是"复现"一个过程。下一章《现实仿真——模拟进阶》，你将在代码里还原乒乓球比赛、指挥玩具小人走圈、实现扫雷游戏的核心逻辑，用代码构建一个"微型世界"！🎮