速成蓝桥杯之枚举（一）-三亩地-编程学习日记

枚举算法（Enumeration），又称穷举法或暴力搜索，是蓝桥杯省赛中最基础、最常用、最容易拿分的算法。它的核心思想是 **“不找捷径，挨个试错”**，将问题所有可能的解全部列举出来，再逐一验证是否满足条件，最终找到答案。

一、核心思想与特点

思想：遍历解空间 → 验证条件 → 收集结果。
优点：
- 思路简单、逻辑清晰：几乎不需要复杂的数学推导或数据结构知识。
- 正确性高：只要解空间正确、条件判断无误，一定能找到正确答案。
- 保底神器：蓝桥杯按测试点给分，即使大数据超时，小数据点也能拿部分分。
缺点：
- 效率低下：时间复杂度通常为O(n), O(n²), O(n!)等，数据量大时极易超时。

二、解题三步骤

确定解空间明确枚举什么（对象）、范围多大（边界）。
- 例：求 1~100 的奇数 → 解空间是1~100的所有整数。
- 例：百钱买百鸡 → 解空间是公鸡 x、母鸡 y、小鸡 z 的可能组合。
设计循环结构
- 单重循环：单变量问题（如遍历数字）。
- 多重循环：多变量问题（如二维坐标、三元方程）。
- 二进制枚举：用于子集、组合选择（n ≤ 20）。
编写判断条件在循环内用if语句验证候选解是否符合题意。

三、蓝桥杯常见枚举类型

1. 普通循环枚举（最常用）

直接用for/while循环遍历所有可能。例题：反倍数（蓝桥杯基础题）

问题：统计 1~n 中，既不是 a、b、c 倍数的数的个数。

#include <iostream> using namespace std; int main() { int n, a, b, c, ans = 0; cin >> n >> a >> b >> c; // 1. 枚举：遍历1~n for (int i = 1; i <= n; i++) { // 2. 验证条件 if (i % a != 0 && i % b != 0 && i % c != 0) { ans++; } } cout << ans; return 0; }

2. 二进制枚举（子集 / 组合）

用二进制位代表元素是否被选中，适合 “选 / 不选” 的组合问题。

原理：n 个元素 → 遍历0 ~ (1<<n)-1，每一位代表一个元素。
适用：n ≤ 20（2²⁰ ≈ 100 万，可在 1 秒内跑完）。

例题：子集生成

问题：从 {a,b,c} 中选所有子集。

char s[] = {'a', 'b', 'c'}; int n = 3; // 遍历所有状态 (000~111) for (int mask = 0; mask < (1 << n); mask++) { cout << "{"; for (int i = 0; i < n; i++) { // 判断第i位是否为1（选中） if (mask & (1 << i)) { cout << s[i] << " "; } } cout << "}\n"; }

输出：{}, {a}, {b}, {a,b}, {c}, {a,c}, {b,c}, {a,b,c}

3. 排列型枚举

枚举元素的全排列（顺序有关），常用递归 / 回溯实现。

适用：n ≤ 10（10! = 362 万）。

四、蓝桥杯枚举优化技巧

剪枝（提前终止）不满足条件时立即退出循环，减少无效遍历。

// 找第一个符合条件的数，找到就break for (int i = 1; i <= 100; i++) { if (check(i)) { ans = i; break; // 剪枝，不再循环 } }

缩小枚举范围利用数学约束减少循环次数。
- 百钱买百鸡：公鸡 x 最多 20 只（100/5），而非 100。
- 回文日期：只需枚举年份，后半部分由前半部分生成。
改变枚举顺序如逆序枚举找 “最后一个覆盖” 的地毯。

五、时间复杂度判断（能否 AC）

蓝桥杯 1 秒约运行10⁸次操作：

O(n): n ≤ 10⁷ → 安全
O(n²): n ≤ 3000 → 安全（3000²=900 万）
O(n³): n ≤ 200 → 安全（200³=800 万）
O(2ⁿ): n ≤ 20 → 安全
O(n!): n ≤ 10 → 安全

总结：小规模用枚举，大规模想优化。枚举是蓝桥杯的基本功，务必熟练掌握

日记详情

速成蓝桥杯之枚举（一）