枚举算法详解OI-wiki 视角下的穷举思想、解空间剪枝与实战优化【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文基于 OI-wiki 基础算法章节中的枚举算法文档系统讲解枚举Enumerate这一最基础的问题求解策略从不断猜测、一一尝试的核心思想出发明确给出解空间、缩小枚举范围、选择合适的枚举顺序三大要点并借助数组中求和为 0 的数对这一经典例题走完从 $O(n^2)$ 双层循环到 $O(n)$ 桶判定的完整优化链路。读完本文你将掌握枚举问题的思考框架、可复现的多语言实现以及配套测试数据的验证方法。什么是枚举基于已有知识的猜测枚举英语Enumerate是基于已有知识来猜测答案的一种问题求解策略。其核心思想是不断猜测从可能的集合中一一尝试然后再判断题目的条件是否成立。它不依赖精巧的数学构造或复杂的数据结构而是把试这件事做得足够聪明——既要保证不漏掉正确答案又要尽量少试、快试。作为基础算法章节的入门内容枚举的重要性在于其极强的通用性许多看似高深的算法二分、折半搜索、状态压缩 DP 等本质上都是更聪明的枚举。理解枚举的边界与代价是后续学习更复杂算法的前提。枚举的三条要点原文档将使用枚举法解决问题的关键总结为三条缺一不可。给出解空间首先建立简洁的数学模型。枚举之前必须想清楚两个问题可能的情况是什么即正确答案落在哪个候选集合里要枚举哪些要素即候选集合由哪些变量、维度或状态构成。只有把解空间刻画清楚枚举才不会是瞎试也才能为后续的剪枝提供数学依据。减少枚举的空间枚举的范围是什么是所有内容都需要枚举吗这是枚举法中最容易忽略、也最影响性能的一点。解空间虽然已经给定但其规模往往可以被大幅压缩——通过题目条件排除明显不可能的候选或者通过对称性、单调性等性质成批地跳过候选。原文档明确指出用枚举法解决问题时一定要想清楚这两件事否则会带来不必要的时间开销。选择合适的枚举顺序根据题目判断枚举的顺序。例如例题要求的是最大的符合条件的素数那自然是从大到小枚举更合适——一旦找到即可提前终止避免无谓的扫描。顺序的选择往往与剪枝和早期退出策略绑定是枚举从能跑到跑得快的关键一步。例题实战和为 0 的数对以下例题完整演示了写出朴素枚举 → 缩小枚举范围 → 用数据结构替代内层枚举的优化过程。题目给定一个数组其所有元素互不相同且均不为 $0$。求该数组中和为 $0$ 的数对个数。第一版朴素双层循环最容易想到的做法是枚举所有数对(i, j)逐一判断a[i] a[j] 0 Ccpp for (int i 0; i n; i) for (int j 0; j n; j) if (a[i] a[j] 0) ans; Pythonpython for i in range(n): for j in range(n): if a[i] a[j] 0: ans 1 Javajava for (int i 0; i n; i) for (int j 0; j n; j) if (a[i] a[j] 0) ans;该做法的时间复杂度为 $O(n^2)$。它把全部 $n^2$ 个有序数对都枚举了一遍其中存在大量冗余。第二版利用对称性缩小枚举范围题目没有要求数对是有序的。如果(a, b)是一组答案那么(b, a)显然也是答案——也就是说答案是有序情况的一半。因此只需统计满足某种顺序约束的数对例如要求第一个数出现在靠后的位置即j i最后把答案乘上 $2$ 即可 Ccpp for (int i 0; i n; i) for (int j 0; j i; j) if (a[i] a[j] 0) ans; ans * 2; Pythonpython for i in range(n): for j in range(i): if a[i] a[j] 0: ans 1 ans * 2 Javajava for (int i 0; i n; i) for (int j 0; j i; j) if (a[i] a[j] 0) ans; ans * 2;这里把j的枚举范围从[0, n)压缩到[0, i)枚举量减半时间开销随之下降。这正是减少枚举空间的直观体现。第三版用桶替代内层枚举两个数是否都一定要枚举出来呢原文档给出了更进一步的洞察枚举其中一个数之后题目的条件已经确定了另一个数的取值——一旦确定a[i]与之配对的数只能是-a[i]。因此问题转化为如何快速判断-a[i]是否已经出现过在数据范围允许的情况下可以用桶桶排序中使用的桶数据结构记录遍历过的数把每个已出现的数标记进桶中之后只需 $O(1)$ 查询即可。C 的完整实现见仓库中的 enumerate_1.cpp#include cstring constexpr int MAXN 100000; // 此处 MAXN 是数组内元素的界 int solve(int n, int a[]) { bool met[MAXN * 2 1]; // 创建一个能装下 [-MAXN, MAXN] 的桶 memset(met, 0, sizeof(met)); int ans 0; for (int i 0; i n; i) { if (met[MAXN - a[i]]) ans; // 如果桶内有想要的元素答案加一 met[MAXN a[i]] true; // 无论如何都要把当前元素放进桶里 } return ans * 2; }实现细节说明桶的容量met的大小为MAXN * 2 1用下标偏移MAXN的方式把值域[-MAXN, MAXN]映射到非负下标从而支持负数元素先查后放对每个a[i]先查询MAXN - a[i]是否已在桶中即-a[i]是否出现在之前遍历过的位置再把当前元素MAXN a[i]放入桶中从而保证每个数对只按靠后的数统计一次对称加倍返回ans * 2与第二版一致补回有序数对的计数。Python 与 Java 版本同理 Pythonpython met [False] * (MAXN * 2 1) for i in range(n): if met[MAXN - a[i]]: ans 1 met[a[i] MAXN] True ans * 2 Javajava boolean[] met new boolean[MAXN * 2 1]; for (int i 0; i n; i) { if (met[MAXN - a[i]]) ans; met[MAXN a[i]] true; } ans * 2;复杂度分析时间复杂度只对a数组完整遍历了一遍即可完成题目要求当 $n$ 足够大时时间复杂度为 $O(n)$空间复杂度$O(n\max{|x|:x\in a})$即存储数组本身与桶的开销之和。值得注意的是这一优化能否成立取决于值域桶的大小由MAXN元素的界决定。只有当值域规模可接受时用空间换时间的策略才可行这也是在数据范围允许的情况下这一前提的由来。仓库配套源码组织与测试验证OI-wiki 为每个例题都提供了可编译、可验证的配套代码与测试数据本例题也不例外读者可以直接在仓库中复现。可运行的完整程序enumerate_1.cpp 只包含solve核心函数与之配套的主程序位于 enumerate_1.aux1.cpp负责读取输入、调用solve并输出结果#include cstdio #include iostream constexpr int MAXN 100000; int a[MAXN]; extern int solve(int n, int a[]); // see enumerate_1.cpp int main() { int n; std::cin n; for (int i 0; i n; i) { std::cin a[i]; } std::cout solve(n, a) std::endl; return 0; }将两个文件放在同一编译单元下编译运行即可得到与官方测试一致的输出。测试数据验证仓库提供了标准输入输出样例输入文件 enumerate_1.in10 1 2 3 4 5 -5 -4 -3 -2 6期望输出文件 enumerate_1.ans8手工验证一下数组中互为相反数的数对有(2, -2)、(3, -3)、(4, -4)、(5, -5)共 4 组无序数对乘以 2 后得到 8与期望输出完全一致。1与6没有对应的相反数-5与5已在其中。该样例恰好覆盖了存在多组相反数、存在孤立元素两种情形可用于快速检验实现正确性。相关算法延伸枚举与桶数据结构关系密切。当需要快速判断某个值是否存在时桶或哈希表是常见的选择本例题的第三版优化正是其典型应用。可进一步阅读桶排序桶作为数据结构的系统性介绍包括空桶设置、元素入桶、桶内排序与回填的完整流程主元素问题另一个利用桶/计数思想离线判定存在性的经典问题。习题2811: 熄灯问题 - OpenJudge一道适合练习确定枚举对象、压缩枚举状态的经典枚举题其枚举对象的选择与状态压缩思路是本题的核心考察点。小结枚举不是暴力的同义词而是一门关于猜测的艺术先想清楚解空间再想尽办法缩小它最后用合适的顺序和数据结构让每次猜测都更快。本例题的三段式优化——对称性剪枝$O(n^2) \to O(n^2/2)$与桶替代内层枚举$O(n^2) \to O(n)$——展示了从朴素枚举到高效枚举的典型路径这套思维方法在二分答案、折半搜索、哈希判重等进阶算法中会反复出现。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/10 20:52:43 · 阅读 1.2k 枚举算法详解：OI-wiki 视角下的穷举思想、解空间剪枝与实战优化
枚举算法详解OI-wiki 视角下的穷举思想、解空间剪枝与实战优化【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文基于 OI-wiki 基础算法章节中的枚举算法文档系统讲解枚举Enumerate这一最基础的问题求解策略从不断猜测、一一尝试的核心思想出发明确给出解空间、缩小枚举范围、选择合适的枚举顺序三大要点并借助数组中求和为 0 的数对这一经典例题走完从 $O(n^2)$ 双层循环到 $O(n)$ 桶判定的完整优化链路。读完本文你将掌握枚举问题的思考框架、可复现的多语言实现以及配套测试数据的验证方法。什么是枚举基于已有知识的猜测枚举英语Enumerate是基于已有知识来猜测答案的一种问题求解策略。其核心思想是不断猜测从可能的集合中一一尝试然后再判断题目的条件是否成立。它不依赖精巧的数学构造或复杂的数据结构而是把试这件事做得足够聪明——既要保证不漏掉正确答案又要尽量少试、快试。作为基础算法章节的入门内容枚举的重要性在于其极强的通用性许多看似高深的算法二分、折半搜索、状态压缩 DP 等本质上都是更聪明的枚举。理解枚举的边界与代价是后续学习更复杂算法的前提。枚举的三条要点原文档将使用枚举法解决问题的关键总结为三条缺一不可。给出解空间首先建立简洁的数学模型。枚举之前必须想清楚两个问题可能的情况是什么即正确答案落在哪个候选集合里要枚举哪些要素即候选集合由哪些变量、维度或状态构成。只有把解空间刻画清楚枚举才不会是瞎试也才能为后续的剪枝提供数学依据。减少枚举的空间枚举的范围是什么是所有内容都需要枚举吗这是枚举法中最容易忽略、也最影响性能的一点。解空间虽然已经给定但其规模往往可以被大幅压缩——通过题目条件排除明显不可能的候选或者通过对称性、单调性等性质成批地跳过候选。原文档明确指出用枚举法解决问题时一定要想清楚这两件事否则会带来不必要的时间开销。选择合适的枚举顺序根据题目判断枚举的顺序。例如例题要求的是最大的符合条件的素数那自然是从大到小枚举更合适——一旦找到即可提前终止避免无谓的扫描。顺序的选择往往与剪枝和早期退出策略绑定是枚举从能跑到跑得快的关键一步。例题实战和为 0 的数对以下例题完整演示了写出朴素枚举 → 缩小枚举范围 → 用数据结构替代内层枚举的优化过程。题目给定一个数组其所有元素互不相同且均不为 $0$。求该数组中和为 $0$ 的数对个数。第一版朴素双层循环最容易想到的做法是枚举所有数对(i, j)逐一判断a[i] a[j] 0 Ccpp for (int i 0; i n; i) for (int j 0; j n; j) if (a[i] a[j] 0) ans; Pythonpython for i in range(n): for j in range(n): if a[i] a[j] 0: ans 1 Javajava for (int i 0; i n; i) for (int j 0; j n; j) if (a[i] a[j] 0) ans;该做法的时间复杂度为 $O(n^2)$。它把全部 $n^2$ 个有序数对都枚举了一遍其中存在大量冗余。第二版利用对称性缩小枚举范围题目没有要求数对是有序的。如果(a, b)是一组答案那么(b, a)显然也是答案——也就是说答案是有序情况的一半。因此只需统计满足某种顺序约束的数对例如要求第一个数出现在靠后的位置即j i最后把答案乘上 $2$ 即可 Ccpp for (int i 0; i n; i) for (int j 0; j i; j) if (a[i] a[j] 0) ans; ans * 2; Pythonpython for i in range(n): for j in range(i): if a[i] a[j] 0: ans 1 ans * 2 Javajava for (int i 0; i n; i) for (int j 0; j i; j) if (a[i] a[j] 0) ans; ans * 2;这里把j的枚举范围从[0, n)压缩到[0, i)枚举量减半时间开销随之下降。这正是减少枚举空间的直观体现。第三版用桶替代内层枚举两个数是否都一定要枚举出来呢原文档给出了更进一步的洞察枚举其中一个数之后题目的条件已经确定了另一个数的取值——一旦确定a[i]与之配对的数只能是-a[i]。因此问题转化为如何快速判断-a[i]是否已经出现过在数据范围允许的情况下可以用桶桶排序中使用的桶数据结构记录遍历过的数把每个已出现的数标记进桶中之后只需 $O(1)$ 查询即可。C 的完整实现见仓库中的 enumerate_1.cpp#include cstring constexpr int MAXN 100000; // 此处 MAXN 是数组内元素的界 int solve(int n, int a[]) { bool met[MAXN * 2 1]; // 创建一个能装下 [-MAXN, MAXN] 的桶 memset(met, 0, sizeof(met)); int ans 0; for (int i 0; i n; i) { if (met[MAXN - a[i]]) ans; // 如果桶内有想要的元素答案加一 met[MAXN a[i]] true; // 无论如何都要把当前元素放进桶里 } return ans * 2; }实现细节说明桶的容量met的大小为MAXN * 2 1用下标偏移MAXN的方式把值域[-MAXN, MAXN]映射到非负下标从而支持负数元素先查后放对每个a[i]先查询MAXN - a[i]是否已在桶中即-a[i]是否出现在之前遍历过的位置再把当前元素MAXN a[i]放入桶中从而保证每个数对只按靠后的数统计一次对称加倍返回ans * 2与第二版一致补回有序数对的计数。Python 与 Java 版本同理 Pythonpython met [False] * (MAXN * 2 1) for i in range(n): if met[MAXN - a[i]]: ans 1 met[a[i] MAXN] True ans * 2 Javajava boolean[] met new boolean[MAXN * 2 1]; for (int i 0; i n; i) { if (met[MAXN - a[i]]) ans; met[MAXN a[i]] true; } ans * 2;复杂度分析时间复杂度只对a数组完整遍历了一遍即可完成题目要求当 $n$ 足够大时时间复杂度为 $O(n)$空间复杂度$O(n\max{|x|:x\in a})$即存储数组本身与桶的开销之和。值得注意的是这一优化能否成立取决于值域桶的大小由MAXN元素的界决定。只有当值域规模可接受时用空间换时间的策略才可行这也是在数据范围允许的情况下这一前提的由来。仓库配套源码组织与测试验证OI-wiki 为每个例题都提供了可编译、可验证的配套代码与测试数据本例题也不例外读者可以直接在仓库中复现。可运行的完整程序enumerate_1.cpp 只包含solve核心函数与之配套的主程序位于 enumerate_1.aux1.cpp负责读取输入、调用solve并输出结果#include cstdio #include iostream constexpr int MAXN 100000; int a[MAXN]; extern int solve(int n, int a[]); // see enumerate_1.cpp int main() { int n; std::cin n; for (int i 0; i n; i) { std::cin a[i]; } std::cout solve(n, a) std::endl; return 0; }将两个文件放在同一编译单元下编译运行即可得到与官方测试一致的输出。测试数据验证仓库提供了标准输入输出样例输入文件 enumerate_1.in10 1 2 3 4 5 -5 -4 -3 -2 6期望输出文件 enumerate_1.ans8手工验证一下数组中互为相反数的数对有(2, -2)、(3, -3)、(4, -4)、(5, -5)共 4 组无序数对乘以 2 后得到 8与期望输出完全一致。1与6没有对应的相反数-5与5已在其中。该样例恰好覆盖了存在多组相反数、存在孤立元素两种情形可用于快速检验实现正确性。相关算法延伸枚举与桶数据结构关系密切。当需要快速判断某个值是否存在时桶或哈希表是常见的选择本例题的第三版优化正是其典型应用。可进一步阅读桶排序桶作为数据结构的系统性介绍包括空桶设置、元素入桶、桶内排序与回填的完整流程主元素问题另一个利用桶/计数思想离线判定存在性的经典问题。习题2811: 熄灯问题 - OpenJudge一道适合练习确定枚举对象、压缩枚举状态的经典枚举题其枚举对象的选择与状态压缩思路是本题的核心考察点。小结枚举不是暴力的同义词而是一门关于猜测的艺术先想清楚解空间再想尽办法缩小它最后用合适的顺序和数据结构让每次猜测都更快。本例题的三段式优化——对称性剪枝$O(n^2) \to O(n^2/2)$与桶替代内层枚举$O(n^2) \to O(n)$——展示了从朴素枚举到高效枚举的典型路径这套思维方法在二分答案、折半搜索、哈希判重等进阶算法中会反复出现。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考