复杂度与暴力枚举

前言

你刚学编程的时候，可能觉得”让电脑算不就行了”。比如要在 1000 个数里找最大的那个，写个循环扫一遍，瞬间出结果。但如果要在 $10^9$ 个数里找呢？或者要在 $10^9$ 个数里找两个数使它们的和等于某个值呢？

答案不是”电脑更快就行”——而是”你的算法得更快”。但快多少才够？$O(n)$ 够吗？还是需要 $O(\log n)$？这一章先回答”多快才算快”这个问题，然后介绍最朴素但常常最有效的策略——暴力枚举：把所有可能的答案都试一遍。

别觉得暴力”低级”。很多题目不需要花哨的算法，暴力就够了——前提是你知道什么时候暴力能过。而知道这一点的前提，就是理解时间复杂度。

问题的本质

时间复杂度：多快才算快？

不同的算法处理同一个问题时，“速度”可以差很多。我们用大 O 记号来描述一个算法的运行时间随数据量增长的趋势：

$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$

这些符号看起来抽象，但背后有一个非常实用的经验法则：1 秒内大约能跑 $10^8$ 次基本运算（加减乘除、比较、赋值）。有了这个数字，拿到题目后看一眼数据范围，就能反推你需要什么复杂度的算法：

$n$ 的大小	能接受的复杂度	对应算法举例
$n \le 10$	$O(n!)$ 甚至 $O(n^n)$	全排列、暴力搜索
$n \le 20$	$O(2^n \cdot n)$	位掩码枚举子集
$n \le 5000$	$O(n^2)$	双重循环
$n \le 10^5$	$O(n \log n)$	排序、二分
$n \le 10^7$	$O(n)$	单次遍历
$n \le 10^{18}$	$O(\log n)$	快速幂、二分答案

这张表是整个系列的基础。后面每一篇笔记里的算法，都在这张表里有自己的位置。

暴力枚举：最直觉的策略

暴力枚举的核心思想朴素到不能再朴素：把所有可能的答案都试一遍，检查哪个满足条件。但它要回答两个问题：

1. 搜索范围有多大？——“所有可能的答案”到底是多少种？如果是 $n$ 个数里选 1 个，那就是 $n$ 种；如果是选任意个，那就是 $2^n$ 种。
2. 来得及吗？——搜索范围 × 每次检查的耗时 ≤ 时限？

如果两个问题的答案都是”行”，那暴力就是正确答案。不需要想更复杂的算法。

理论 + 代码

单层循环：遍历找最大值

最简单的暴力就是遍历一遍找最值。

// 在数组 a[0..n-1] 中找最大值
int max_val = a[0];          // ① 假设第一个是最大值
for (int i = 1; i < n; i++)  // ② 从第二个开始逐个比较
    if (a[i] > max_val)       // ③ 比当前最大值还大？
        max_val = a[i];       // ④ 更新最大值
// 时间复杂度：O(n)
// n = 10^7 时约 10^7 次运算，1 秒内搞定

双重循环：选两个数

如果要从 $n$ 个数里选 2 个，就需要双重循环。

// 找最大的 a[i] + a[j]（i != j）
int best = 0;
for (int i = 0; i < n; i++)          // ① 枚举第一个数
    for (int j = i + 1; j < n; j++)   // ② 枚举第二个数，j > i 避免重复
        best = max(best, a[i] + a[j]);
// 时间复杂度：O(n²)
// n = 5000 时约 1.25×10⁷ 次运算，可以
// n = 10^5 时约 5×10⁹ 次运算，TLE！

• ② j = i + 1 而不是 j = 0：因为选 $(i, j)$ 和 $(j, i)$ 是同一种方案，只需要枚举 $j > i$ 的情况。这把循环次数从 $n^2$ 减半到 $\frac{n(n-1)}{2}$，但复杂度仍然是 $O(n^2)$。

位运算枚举子集

“从 $n$ 个元素中选任意个”——这就是子集。子集有多少个？$2^n$ 个（每个元素都有选或不选两种可能）。怎么枚举？用一个 $n$ 位二进制数来表示：第 $i$ 位是 1 表示选了，是 0 表示没选。

// 枚举 {0, 1, ..., n-1} 的所有子集
for (int mask = 0; mask < (1 << n); mask++) {
    // ① mask 从 0 到 2^n - 1
    // 每个二进制位代表"选"或"不选"
    // 比如 n=3，mask=5（二进制 101）代表选了第 0 个和第 2 个

    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (mask >> i & 1) {    // ② 提取第 i 位
            sum += a[i];        // ③ 选了就加上
        }
    }
    // 现在 sum = 这个子集的元素之和
}
// 时间复杂度：O(n × 2^n)
// n = 20 时：20 × 2^20 ≈ 2×10^7，可以
// n = 25 时：25 × 2^25 ≈ 8×10^8，有点紧
// n = 30 时：30 × 2^30 ≈ 3×10^10，跑不完

mask >> i & 1 是什么意思？ 拆开来看：

• mask >> i：把 mask 右移 $i$ 位，让原来第 $i$ 位来到最低位。比如 mask = 13（二进制 1101），mask >> 2 就是 3（二进制 11）——原来的第 2 位（从 0 开始数）现在是最低位。
• & 1：和 1 做按位与。只有最低位是 1 时结果才是 1，否则是 0。
• 合起来就是”检查 mask 的第 $i$ 位是不是 1”。

十进制转二进制

位运算的基础是理解二进制。怎么把一个十进制数 $n$ 转成二进制？不断除以 2，记余数：

以 $n = 13$ 为例：

步骤	$n$	$n \bmod 2$	$n / 2$
1	13	1	6
2	6	0	3
3	3	1	1
4	1	1	0

从下往上读余数：$1101_2 = 8 + 4 + 0 + 1 = 13$。✓

// 十进制转二进制（从低位到高位输出）
int n = 13;
for (int i = 9; i >= 0; i--) {  // ① 从高位到低位
    cout << (n >> i & 1);        // ② 提取第 i 位
}
// 输出：0000001101（10位）

• ① 从第 9 位（最高位）到第 0 位（最低位）依次输出。
• ② n >> i & 1：和上面一样，提取第 $i$ 位的值。

这个技巧在后面很多地方都会用到——比如 02-04 快速幂 里快速幂的”二进制拆分指数”就是同样的思路。

走一遍具体过程：$n = 3$，数组 [3, 1, 4]。

mask（二进制）	选了哪些	子集之和
000	无	0
001	a[0]=3	3
010	a[1]=1	1
011	a[0], a[1]	4
100	a[2]=4	4
101	a[0], a[2]	7
110	a[1], a[2]	5
111	全部	8

共 $2^3 = 8$ 个子集，每个子集的和都算出来了。

折半枚举（Meet in the Middle）

暴力枚举的时间瓶颈往往是搜索空间太大——$n = 40$ 时 $2^{40} \approx 10^{12}$，根本跑不完。但如果把数据分成两半呢？

思路：把 $n$ 个数分成两组，每组 $n/2$ 个。分别枚举每组的所有子集和，得到两个数组 $L$ 和 $R$。然后问题变成：在 $L$ 和 $R$ 中各找一个数，使它们的和等于目标 $K$。

$2^{40}$ 变成了 $2 \times 2^{20} \approx 2 \times 10^6$——突然就可行了！

// 折半枚举：从 n 个数中选若干个，使和等于 K
// n <= 40
vector<long long> L, R;
int half = n / 2;

// ① 枚举前半部分的所有子集和
for (int mask = 0; mask < (1 << half); mask++) {
    long long sum = 0;
    for (int i = 0; i < half; i++)
        if (mask >> i & 1) sum += a[i];
    L.push_back(sum);
}

// ② 枚举后半部分的所有子集和
for (int mask = 0; mask < (1 << (n - half)); mask++) {
    long long sum = 0;
    for (int i = 0; i < n - half; i++)
        if (mask >> i & 1) sum += a[half + i];
    R.push_back(sum);
}

// ③ 排序 R，对每个 L 中的元素在 R 中二分搜索
sort(R.begin(), R.end());
bool found = false;
for (long long x : L) {
    // 找 R 中是否存在 K - x
    if (binary_search(R.begin(), R.end(), K - x)) {
        found = true;
        break;
    }
}

• ①② 每组最多 $2^{20} \approx 10^6$ 个子集，枚举很快。
• ③ binary_search 是 C++ STL 函数，在排序数组中 $O(\log n)$ 判断元素是否存在。也可以用 lower_bound。

折半枚举在竞赛中经常出现——它把 $O(2^n)$ 变成 $O(2^{n/2})$，让 $n = 40$ 的问题变得可解。

例题

例题 1：M&A 001 — Print 5+N（★1）

题目：有 5 个苹果和 $N$ 个橘子。给定整数 $N$，输出苹果和橘子一共多少个。

数据范围：$1 \le N \le 100$

—— AtCoder M&A 001

思路：这是 AtCoder 的入门题——直接输出 $5 + N$。用来确认代码模板没有问题。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);          // ① 读入 N
    printf("%d\n", 5 + N);    // ② 输出 5+N
}

逐行解析：

• ① scanf("%d", &N)：%d 表示读 int 类型，&N 是变量 N 的地址。这是 C 风格输入，比 cin 快。
• ② 直接输出 $5+N$。复杂度 $O(1)$——连循环都没有。

---

例题 2：Tessoku Book — A03 Two Cards

题目：有 $N$ 张红色卡片（上面写着 $P_1, P_2, \ldots, P_N$）和 $N$ 张蓝色卡片（上面写着 $Q_1, Q_2, \ldots, Q_N$）。从红色和蓝色各选 1 张，是否存在一种选法使得两张卡片上的数字之和恰好等于 $K$？存在输出 Yes，否则输出 No。

数据范围：$1 \le N \le 100$，$1 \le K \le 100$，$1 \le P_i, Q_i \le 100$

—— AtCoder Tessoku Book A03

思路：从红色选 1 张、蓝色选 1 张，总共 $N \times N$ 种组合。$N \le 100$ 时 $N^2 = 10000$，轻轻松松。直接双重循环枚举所有组合，检查是否有 $P_i + Q_j = K$。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N, K;
    scanf("%d%d", &N, &K);
    int P[110], Q[110];
    for (int i = 0; i < N; i++) scanf("%d", &P[i]);
    for (int i = 0; i < N; i++) scanf("%d", &Q[i]);

    bool found = false;
    for (int i = 0; i < N; i++) {          // ① 枚举红色卡片
        for (int j = 0; j < N; j++) {      // ② 枚举蓝色卡片
            if (P[i] + Q[j] == K) {        // ③ 检查和是否等于 K
                found = true;
            }
        }
    }
    printf("%s\n", found ? "Yes" : "No");   // ④ 输出结果
}

逐行解析：

• ①② 双重循环：$O(N^2)$。$N = 100$ 时约 $10^4$ 次运算，远小于 $10^8$。
• ③ 一旦找到就设 found = true。可以加 break 提前退出，但不加也能过。
• ④ 三目运算符：found ? "Yes" : "No"——如果 found 为真输出 Yes，否则输出 No。

---

例题 3：M&A 008 — Brute Force 1（★1）

题目：有红色和蓝色卡片各 1 张。你要在红色卡片上写一个 $1$ 到 $N$ 的整数，在蓝色卡片上也写一个 $1$ 到 $N$ 的整数。两张卡片上的数字之和不超过 $S$ 的写法有多少种？

数据范围：$1 \le N \le 1000$，$1 \le S \le 2000$

—— AtCoder M&A 008

思路：红色写 $a$（$1 \le a \le N$），蓝色写 $b$（$1 \le b \le N$），要求 $a + b \le S$。双重循环枚举所有 $(a, b)$，统计满足条件的数量。$N \le 1000$ 时 $N^2 = 10^6$，没问题。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N, S;
    scanf("%d%d", &N, &S);

    int cnt = 0;
    for (int a = 1; a <= N; a++) {         // ① 红色写 a
        for (int b = 1; b <= N; b++) {     // ② 蓝色写 b
            if (a + b <= S)                // ③ 和不超过 S
                cnt++;                     // ④ 计数
        }
    }
    printf("%d\n", cnt);
}

逐行解析：

• ①② 双重循环枚举 $a \in [1, N]$ 和 $b \in [1, N]$，共 $N^2$ 种。
• ③ $a + b \le S$：检查条件。
• ④ 满足条件就加 1。最终 cnt 就是答案。

走一遍过程：$N = 3, S = 4$。

$a$ \ $b$	1	2	3
1	2 ✓	3 ✓	4 ✓
2	3 ✓	4 ✓	5 ✗
3	4 ✓	5 ✗	6 ✗

满足条件的 6 种：$(1,1), (1,2), (1,3), (2,1), (2,2), (3,1)$。✓

优化思路：内层循环可以只算 $\min(N, S - a)$ 而不用遍历到 $N$，但 $N \le 1000$ 不需要。

---

例题 4：M&A 009 — Brute Force 2（★1，部分分）

题目：$N$ 张卡片排成一排，第 $i$ 张写着整数 $A_i$。能否从中选出若干张卡片（至少 0 张），使得选出的卡片上数字之和恰好等于 $S$？能则输出 Yes，否则输出 No。

数据范围：$1 \le N \le 60$，$1 \le A_i \le 10000$，$1 \le S \le 10000$

注意：$N \le 20$ 时可以用子集枚举拿部分分。$N \le 60$ 时需要 DP（05-01 会讲）。

—— AtCoder M&A 009

思路：题目说 $N \le 60$，但 $2^{60} \approx 10^{18}$，子集枚举跑不完。不过当 $N \le 20$ 时 $2^{20} \approx 10^6$，完全可以。所以这道题用子集枚举只能拿部分分（$N \le 20$ 的测试点）。下面的代码只处理 $N \le 20$ 的情况。

代码（$N \le 20$，子集枚举）：

#include <cstdio>
using namespace std;

int main() {
    int N, S;
    scanf("%d%d", &N, &S);
    int A[70];
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);

    bool found = false;
    for (int mask = 0; mask < (1 << N); mask++) {   // ① 枚举所有子集
        int sum = 0;
        for (int i = 0; i < N; i++) {
            if (mask >> i & 1)                       // ② 检查第 i 张是否选中
                sum += A[i];                          // ③ 选中就加到总和
        }
        if (sum == S) {                               // ④ 恰好等于 S
            found = true;
            break;
        }
    }
    printf("%s\n", found ? "Yes" : "No");
}

逐行解析：

• ① mask 从 0 到 $2^N - 1$，每个值代表一种子集。1 << N 就是 $2^N$。
• ② mask >> i & 1：检查 mask 的第 $i$ 位是否为 1（即第 $i$ 张卡片是否被选中）。
• ③ 把选中的卡片值累加。
• ④ 如果某个子集之和恰好等于 $S$，就找到了答案。break 提前退出——不用枚举剩下的子集了。

走一遍过程：$N = 3, S = 11$，卡片 [2, 5, 9]。

mask	选中	子集和	== 11?
000	无	0	✗
001	A[0]=2	2	✗
010	A[1]=5	5	✗
011	2,5	7	✗
100	A[2]=9	9	✗
101	2,9	11	✓

找到！第 1 张和第 3 张卡片之和 $2 + 9 = 11$。输出 Yes。✓

为什么只能拿部分分？ $N = 60$ 时 $2^{60} \approx 10^{18}$，即使每秒 $10^8$ 次运算也需要约 $10^{10}$ 秒——比宇宙年龄还长。完整解法需要动态规划，我们在 05-01 DP 入门 再讲。

---

例题 5：Typical 90 — 063 Monochromatic Subgrid（★4）

题目：给定一个 $H$ 行 $W$ 列的网格，格子 $(i, j)$ 的值为 $P_{i,j}$。选若干行和若干列（都至少选 1 个）构成子网格，要求子网格中所有格子的值都相同。求满足条件的子网格的最大面积（选的行数 $\times$ 列数）。

数据范围：$1 \le H \le 8$，$1 \le W \le 10000$，$1 \le P_{i,j} \le HW$

—— AtCoder Typical 90 063

思路：$H$ 非常小——最多 8 行！$2^8 = 256$，可以枚举所有行的子集。对于每种行的选法，再统计每一列中选中行的值是否全部相同：如果相同，这一列就可以选进来。

具体来说：枚举行子集 $S$（$2^H - 1$ 种），对于每种 $S$，遍历每一列 $j$，检查所有选中行的 $P_{i,j}$ 是否相等。如果相等，这列的贡献是 $|S|$（行数），答案更新为 $|S| \times$（满足条件的列数）。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int P[10][10010];

int main() {
    int H, W;
    scanf("%d%d", &H, &W);
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            scanf("%d", &P[i][j]);

    int ans = 0;
    // ① 枚举所有非空行子集
    for (int mask = 1; mask < (1 << H); mask++) {
        int rows = __builtin_popcount(mask);   // ② 选了多少行
        int cols = 0;                           // ③ 满足条件的列数

        for (int j = 0; j < W; j++) {           // ④ 遍历每一列
            bool ok = true;
            int val = -1;
            for (int i = 0; i < H; i++) {
                if (mask >> i & 1) {            // ⑤ 第 i 行被选中
                    if (val == -1) val = P[i][j]; // ⑥ 第一个选中行的值
                    else if (P[i][j] != val) {   // ⑦ 和之前的不一样
                        ok = false;
                        break;
                    }
                }
            }
            if (ok) cols++;                     // ⑧ 这一列所有选中行的值都相同
        }

        ans = max(ans, rows * cols);            // ⑨ 更新最大面积
    }
    printf("%d\n", ans);
}

逐行解析：

• ① mask 从 1 开始（至少选 1 行），到 $2^H - 1$（最多选全部 $H$ 行）。
• ② __builtin_popcount(mask)：mask 中 1 的个数，即选了几行。
• ④⑦ 对每一列，检查选中行的值是否全部相等。如果出现不同的值，ok = false。
• ⑧⑨ 所有选中行的值都相同的列数 cols，面积 = rows * cols，取最大值。

复杂度：$2^H \times H \times W$。$H = 8, W = 10000$ 时：$256 \times 8 \times 10000 \approx 2 \times 10^7$，1 秒内搞定。

走一遍过程：$H = 2, W = 3$，网格 $\begin{bmatrix} 1 & 2 & 1 \\ 1 & 2 & 3 \end{bmatrix}$。

mask	选中行	第1列	第2列	第3列	cols	面积
01	行0	{1} ✓	{2} ✓	{1} ✓	3	1×3=3
10	行1	{1} ✓	{2} ✓	{3} ✓	3	1×3=3
11	行0,1	1,1 ✓	2,2 ✓	1,3 ✗	2	2×2=4

最大面积 = 4（选两行、前两列，所有值都是 $\begin{bmatrix} 1 & 2 \\ 1 & 2 \end{bmatrix}$）。✓

参考文献

理论讲义 — AtCoder Algorithm Lectures

• 競技プログラミング基本用語集（難易度 1）

教材讲解 — 競技プログラミングの鉄則 第 1 章

• 1.1 B01 A+B Problem（基础输入输出 解说）
• 1.2 B02 Divisor Check（全探索 解说）
• 1.3 B03 Supermarket 1（三重循环枚举 解说）
• 计算量分析在教材本体 1.3 节讲解

基础练习 — アルゴリズムと数学 演習問題集

• 001 Print 5+N（基础输出）【例题】
• 008 Brute Force 1（双层循环计数）【例题】
• 009 Brute Force 2（子集枚举 N≤60）【例题】
• 002 Sum of 3 Integers（简单加法）
• 003 Sum of N Integers（循环累加）
• 004 Product of 3 Integers（简单乘法）
• 006 Print 2N+3（简单算术）
• 018 Convenience Store 1（子集和 N≤20）
• 020 Choose Cards 2（五重循环 N≤100）
• 091 How Many Ways?（三重循环计数）

系统练习 — 競技プログラミングの鉄則

• A03 Two Cards（O(N²)暴力配对）【例题】
• A01 The First Problem（基础输出）
• A02 Linear Search（线性搜索）
• A04 Binary Representation 1（二进制理解）
• B04 Binary Representation 2（十进制↔二进制）
• A05 Three Cards（O(N³)暴力枚举）

实战练习 — 競プロ典型 90 問

• 063 Monochromatic Subgrid（★4，子集枚举 H≤8）【例题】

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化