枚举算法

简介

枚举算法是信息学竞赛中最基础也最重要的算法之一，特别适合初学者掌握。本文将介绍枚举算法的基本概念、应用场景和实现技巧。

枚举（英语：Enumerate）是基于已有知识来猜测答案的一种问题求解策略。

枚举的思想是不断地猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立。

什么是枚举算法

枚举算法（又称穷举算法）是一种通过遍历所有可能情况来解决问题的算法思想。它的核心思路是：系统地列举问题的所有可能解，然后逐一验证哪些解满足题目要求。

枚举算法的基本框架

枚举算法通常遵循以下步骤：

1. 确定枚举对象和范围
2. 设计枚举顺序
3. 构造验证条件
4. 优化枚举过程（减少不必要的枚举）

简单示例：找出100以内的素数

#include <iostream>
using namespace std;
 
int main() {
    for(int i=2; i<=100; i++) {  // 枚举所有数字
        bool is_prime = true;
        for(int j=2; j*j<=i; j++) {  // 验证是否为素数
            if(i%j == 0) {
                is_prime = false;
                break;
            }
        }
        if(is_prime) {
            cout << i << " ";
        }
    }
    return 0;
}

四、枚举算法的优化技巧

1. 缩小枚举范围：通过数学分析减少需要枚举的数量
2. 改变枚举顺序：有时逆序枚举或特定顺序枚举更高效
3. 双向枚举：从两个方向同时枚举（如两数之和问题）
4. 预处理信息：提前计算并存储部分结果

五、典型应用场景

1. 排列组合问题（如全排列、子集生成）
2. 搜索问题（如迷宫问题、八皇后问题）
3. 数学问题（如完数、水仙花数）
4. 字符串匹配问题（如暴力匹配算法）

六、注意事项

1. 枚举算法时间复杂度较高，适合数据规模较小的问题（通常n≤10^6）
2. 注意避免重复枚举
3. 合理利用剪枝策略提前终止不可能的分支

枚举算法虽然简单，但却是许多高级算法的基础。掌握好枚举算法，能帮助你在信息学竞赛中解决大量基础题目，并为学习更复杂的算法打下坚实基础。

要点

给出解空间

建立简洁的数学模型。

枚举的时候要想清楚：可能的情况是什么？要枚举哪些要素？

减少枚举的空间

枚举的范围是什么？是所有的内容都需要枚举吗？

在用枚举法解决问题的时候，一定要想清楚这两件事，否则会带来不必要的时间开销。

选择合适的枚举顺序

根据题目判断。比如例题中要求的是最大的符合条件的素数，那自然是从大到小枚举比较合适。

例题

以下是一个使用枚举解题与优化枚举范围的例子。

for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
    if (a[i] + a[j] == 0) ++ans;

for (int i = 0; i < n; ++i)
  for (int j = 0; j < i; ++j)
    if (a[i] + a[j] == 0) ++ans;

#include <cstring>
const 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;
}

复杂度分析

• 时间复杂度分析：对 $a$ 数组遍历了一遍就能完成题目要求，当 $n$ 足够大的时候时间复杂度为 $O(n)$。
• 空间复杂度分析：$O(n+\max\{|x|:x\in a\})$。

例题