速成蓝桥杯之枚举（一）

枚举算法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 ~ (1n)-1每一位代表一个元素。适用n ≤ 202²⁰ ≈ 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 ≤ 1010! 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 → 安全总结小规模用枚举大规模想优化。枚举是蓝桥杯的基本功务必熟练掌握