循环枚举
算法简介¶
在算法竞赛中，枚举（Enumeration）是一种基础而直观的方法，通过遍历所有可能的解空间来寻找满足条件的答案。
虽然枚举的时间复杂度往往较高，但在约束较小或加入剪枝（Pruning）后，枚举依然是解决诸多组合问题的利器。
示例场景：
破解四位数字密码，可依次尝试 $0000\sim 9999$ 的所有组合；
循环枚举的基本思路¶
-
确定变量与范围：明确需要枚举的变量数量及各自取值区间。
-
设计嵌套循环：循环层数 = 变量个数，内层循环在外层每种取值下都要完整执行。
-
验证/计算：在最内层循环中，使用当前组合进行判断、计数或累加等操作。
-
剪枝优化（可选）：若部分组合可提前判定不符合条件，可在循环中加入
if语句跳过后续无效枚举，以降低实际运行次数。
例题1：鸡兔同笼¶
已知鸡和兔共 $35$ 只，脚的总数为 $94$。求鸡和兔的数量。
思路：设鸡 $x$ 只，兔 $y$ 只，则
枚举 $x,y$，并判断 $x+y=35,2x+4y=94$ 是否成立。
- $x$ 的范围：$0 \leq x \leq 35$。
- $y$ 的范围：$0 \leq y \leq 35$。
因此需要两个循环嵌套枚举所有 $x$ 和 $y$ 的组合。
for (int x = 0; x <= 35; x++)
{
for (int y = 0; y <= 35; y++)
{
if (x + y == 35 && 2 * x + 4 * y == 94)
{
cout << "鸡: " << x << ", 兔: " << y;
return 0; // 找到解后退出
}
}
}
由此可见很多方程问题都是可以用枚举算法解决的。
应用：[GESP202406 二级] 平方之和¶
题意：判断 $n$ 个方程 $x^2+y^2=a_i$ 是否有正整数解。
- $1\leq n\leq 10$，$1\leq a_i\leq 10^6$。
思路：
类似于鸡兔同笼，一共有两个未知数。因此考虑枚举 $x$ 和 $y$。
- $x$ 的范围：$1 \leq x \leq a_i$。
- $y$ 的范围：$1 \leq y \leq a_i$
这是朴素想法，但时间复杂度过高。这样做最坏时间复杂度为 $O(a_i^2)$ 最坏达到 $10^{12}$ 次计算，从而 TLE。
我们需要减少一些不必要的枚举，降低循环次数。
不难推出 $x^2\leq a_i\leq 10^6$，因此 $x$ 的范围可以缩小为 $x \leq 10^3$。同理推出 $y\leq 10^3$。
这样只需要循环 $10^6$ 次，可以在规定时间内解决答案。
应用：[COCI2017-2018#6] Davor¶
本题的本质也是一个解方程问题。
有两个未知数 $x,k$，需要解决的方程是：
因此考虑枚举 $x,k$ 即可。
- $x$ 的范围：$1 \leq x \leq 100$。（题目已知）
- $k$ 的范围：$1\leq k\leq 200$。
- $k$ 的上限可以根据数据范围推测得知：
- $N$ 最多取值 $145600$，因此 $k$ 的上限为 $\frac{145600}{52 \times 21} \approx 133$。
- 所以 $k$ 的上限其实很小，随便写一个即可。
注意 $x$ 尽可能大，$k$ 尽可能小。因此倒序枚举 $x$，正序枚举 $y$。
例题2：三位数回文数¶
找出所有三位数中正读和反读都相同的数字。
思路：三位数 $abc$ 是回文数当且仅当 $a = c$。
因此可以将所有的三位数 $100\sim 999$ 全部枚举出来，并判断百位和个位是否相等。
#include <bits/stdc++.h>
using namespace std;
int main()
{
for (int i = 100; i < 1000; ++i)
{
int a = i / 100; // 百位
int b = (i / 10) % 10; // 十位
int c = i % 10; // 个位
if (a == c) // 判断回文
{
cout << i << " ";
}
}
return 0;
}
应用：[ABC343C] 343¶
朴素做法
倒序枚举 $n\sim 1$ 的所有整数记作为 $x$。
- 检验 $x$ 是不是立方数。
- 检验 $x$ 是不是回文数。
显然会 TLE，即使可以做到 $O(1)$ 的时间复杂度检验立方数和回文数，也会因为枚举 $n\sim 1$ 的所有整数而超时。
优化做法
由于 $(10^6)^3=10^{18}$，且由于 $x$ 是立方数，必然存在一个正整数 $k$ 使得 $k^3=x$。
那么可以推出 $1\leq k\leq 10^6$。
因此枚举 $k$，通过 $k^3$ 算出 $x$ 才是解题的关键所在！
for (int k = 1; k <= 1e6; k++)
{
long long x = 1ll * k * k * k;
// 1ll 是 long long 类型的 1，避免三个 int 的 k 相乘爆 int
if (x >= n) break;
// 接下来的工作只有检验 x 是不是回文数
}
接下来验证 $x$ 是否是回文数。
检验回文数可以通过数位拆分实现。
bool check(long long x)
{
long long s = x, y = 0;
while (x)
{
y = y * 10 + s % 10;
s /= 10;
}
return x == y;
}
s % 10获取 $s$ 的个位。-
y = y * 10 + s % 10将个位添加到 $y$ 的末尾。- 首先乘以 $10$ 相当于将 $y$ 左移一位。例如：$12\times 10=120$，即创造一个个位。
- 然后将个位添加到 $y$ 的末尾。例如：$120+3=123$。
-
时间复杂度：$O(\log{x})$。
那么本题最终通过枚举 $k$ 和检验回文数，计算量大约为 $10^6\times \log{10^{18}}$ 不会 TLE。
常见的枚举套路¶
区间枚举型¶
示例问题一 给定一个长度为 $n$ 的序列 $a$，求有多少个长度为 $m$ 的区间，满足区间和是偶数。
- $1\leq m\leq n\leq 1000$，$1\leq a_i\leq 10^9$。
解题思路
考虑枚举出所有的长度为 $m$ 的区间，并一一求和检验区间和是否为偶数即可。
对于一个长度为 $m$ 的区间，其左端点如果为 $i$，那么右端点 $j$ 则为 $i + m - 1$。
- 因此一旦确定左端点 $i$，右端点 $j$ 也就确定了。
所以枚举左端点 $i$：
- 左端点 $i$ 最小取值为 $1$，最大取值为 $n - m + 1$。
为何左端点的上限是 $n - m + 1$？ 因为区间长度是 $k$，所以左端点不能超过 $n - m + 1$，否则右端点会超出边界。
for (int i = 1; i <= n - m + 1; i++)
{
int j = i + m - 1; // 右端点
// 准备计算区间和
}
接下来计算区间 $[i,j]$ 的和，然后判断其是否为偶数即可。
时间复杂度：$O(nm)$
int count = 0; // 计数器
for (int i = 1; i <= n - m + 1; i++)
{
int j = i + m - 1; // 右端点
long long sum = 0; // 初始化区间和
for (int k = i; k <= j; k++)
{
sum += a[k]; // 累加区间和
}
if (sum % 2 == 0)
{
count++; // 如果区间和是偶数，计数器加一
}
}
示例问题二 给定一个长度为 $n$ 的序列 $a$，求有多少个区间 $[l, r]$ 满足 区间的和 $a_l+a_l+...+a_r$ 是一个偶数。
- $n\leq 100$，$1\leq a_i\leq 10^9$。
解题思路
这是典型的区间枚举问题。可以枚举所有可能的区间 $[l, r]$，然后判断该区间的和是否为偶数。
一个区间靠左右端点的值来进行确定。
具体来说：
- 枚举左端点 $l$，从 $1$ 到 $n$。
- 枚举右端点 $r$，从 $l$ 到 $n$。
- 右端点 $r$ 需满足 $\geq l$。
for (int l = 1; l <= n; l++)
for (int r = l; r <= n; r++)
- 计算区间和 $a[l] + a[l+1] + ... + a[r]$。
- 定义 $sum$ 初始化为 $0$。
- 遍历区间 $[l,r]$，执行：$sum \leftarrow sum + a[i]$。
- 判断 $sum$ 是否为偶数。
- 若 $sum$ 为偶数，则计数器加一。
时间复杂度：$O(n^3)$。
for (int l = 1; l <= n; l++)
{
for (int r = l; r <= n; r++)
{
int sum = 0; // 初始化区间和
for (int i = l; i <= r; i++)
{
sum += a[i]; // 累加区间和
}
if (sum % 2 == 0)
{
count++; // 如果区间和是偶数，计数器加一
}
}
}
本题可以做到 $O(n)$ 感兴趣的同学可以自行研究。
应用：[GESP202403 三级] 完全平方数¶
这里所有下标组合 $(i,j)$ 类似于区间枚举。
- 枚举左端点 $i$，从 $1$ 到 $n$。
-
枚举右端点 $j$，从 $i+1$ 到 $n$。
- 题目要求右端点 $j>i$。
-
接下来令 $x=a_i+a_j$。判断 $x$ 是否为完全平方数。
如何判断完全平方数？
- 使用
sqrt函数判断 $x$ 是否为完全平方数。
bool check(int x)
{
int y = sqrt(x);
return y * y == x;
}
解析：
sqrt(x)返回 $x$ 的平方根。并向下取证保存到 $y$ 中。- 若 $y^2=x$，则 $x$ 是完全平方数。
- 说明 $\sqrt{x}$ 没有小数部分。
最终整体时间复杂度为：$O(n^2)$。
应用：[NOIP2014 普及组] 珠心算测验¶
题目要求有多少个数字等于另外两个（不同的）数之和。
等价于找到三个下标组合 $(i,j,k)$ 满足：
- $i\not= j\not= k$
- $a_i+a_j=a_k$ 或 $a_i+a_k=a_j$ 或 $a_j+a_k=a_i$
核心： 从小到大排序整个序列不会影响答案的求解。因此考虑升序排序整个序列 $a$。
则问题等价于求解：
- $1\leq i<j<k\leq n$。
- $a_i+a_j=a_k$
解题思路：
- 枚举 $i$，从 $1$ 到 $n$。
- 枚举 $j$，从 $i+1$ 到 $n$。
- 枚举 $k$，从 $j+1$ 到 $n$。
- 判断 $a_i+a_j=a_k$。
注意：本题只是求解有多少个数可以被两外两个不同的数字加出来，一个数字可能被多次加出来，应当计算一次。
例如 $a=[1,2,3,4,5]$，$5=1+4$，$5=2+3$。这样会重复计算。
因此可以使用一个值域数组打标记，定义 bool vis[10005] 给每个算出来的数字打标记。
时间复杂度：$O(n^3)$。
矩阵枚举型¶
示例问题一 给定一个 $n \times m$ 的矩阵，求有多少个 $a \times b$ 的子矩阵满其元素之和不超过 $k$。
其中 $1\leq a\leq n\leq 10^2,1\leq b\leq m\leq 10^2$，$1\leq k\leq 10^9$，$1\leq a_{i,j}\leq 10^7$。
解题思路
这是一个典型的矩阵枚举问题。可以枚举所有可能的 $a \times b$ 子矩阵，然后判断该子矩阵的元素之和是否不超过 $k$。
一个 $a\times b$ 的子矩阵一旦确定了左上角的坐标，那么其右下角的坐标也就确定了。
因此确定左上角的坐标是关键所在。（当然反过来确定其他角的坐标也可以）
步骤如下：
- 枚举左上角坐标：枚举子矩阵的左上角坐标 $(i, j)$，其中 $1 \leq i \leq n - a + 1$，$1 \leq j \leq m - b + 1$。
为何左上角的上限是 $n - a + 1$ 和 $m - b + 1$？ 因为子矩阵的大小是 $a \times b$，所以左上角的坐标不能超过 $n - a + 1$ 和 $m - b + 1$，否则子矩阵会超出边界。
for (int x1 = 1; x1 <= n - a + 1; x1++)
{
for (int y1 = 1; y1 <= m - b + 1; y1++)
{
// 确定左上角坐标 (x1, y1)
// 由于子矩阵大小为 a x b，右下角坐标为 (x1 + a - 1, y1 + b - 1)
int x2 = x1 + a - 1;
int y2 = y1 + b - 1;
}
}
- 计算子矩阵和：对于每个左上角坐标 $(x1, y1)$，计算对应的 $a \times b$ 子矩阵的元素之和。
long long sum = 0; // 初始化子矩阵和
for (int i = x1; i <= x2; i++)
{
for (int j = y1; j <= y2; j++)
{
sum += A[i][j]; // 累加子矩阵元素
}
}
if (sum <= k) // 判断子矩阵和是否不超过 k
{
count++; // 如果满足条件，计数器加一
}
- 时间复杂度：$O(n\cdot m\cdot a\cdot b)$，其中 $a$ 和 $b$ 分别是子矩阵的行数和列数。
示例问题二 给定一个 $n \times m$ 的矩阵，求有多少个 子矩阵满其元素之和不超过 $k$。
其中 $1\leq n,m\leq 10^2$，$1\leq k\leq 10^9$，$1\leq a_{i,j}\leq 10^7$。
解题思路
这是一个典型的矩阵枚举问题。可以枚举所有可能的子矩阵，然后判断该子矩阵的元素之和是否不超过 $k$。
和上一题的主要区别在于，这里不再限定子矩阵的大小，而是可以是任意大小的子矩阵。
因此可以枚举所有可能的左上角和右下角坐标。
步骤如下：
- 枚举左上角坐标 $(x_1, y_1)$，其中 $1\leq x_1 \leq n$，$1 \leq y_1 \leq m$。
-
枚举右下角坐标 $(x_2, y_2)$，其中 $x_1\leq x_2 \leq n$，$y_1 \leq y_2 \leq m$。
- 保证右下角的行和列大于或等于左上角的。
-
接下来遍历子矩阵，计算子矩阵的元素之和。
- 判断子矩阵的和是否不超过 $k$，如果满足条件，则计数器加一。
时间复杂度：$O(n^3 \cdot m^3)$。
for (int x1 = 1; x1 <= n; x1++)
{
for (int y1 = 1; y1 <= m; y1++)
{
for (int x2 = x1; x2 <= n; x2++)
{
for (int y2 = y1; y2 <= m; y2++)
{
long long sum = 0; // 初始化子矩阵和
for (int i = x1; i <= x2; i++)
{
for (int j = y1; j <= y2; j++)
{
sum += A[i][j]; // 累加子矩阵元素
}
}
if (sum <= k) // 判断子矩阵和是否不超过 k
{
count++; // 如果满足条件，计数器加一
}
}
}
}
}
应用：[GESP202406 四级] 黑白方块¶
注意：输入的矩阵都是紧紧挨着一起的字符，因此需要使用 char 类型的二维数组。
这是一个典型的子矩阵枚举问题。题目并未规定子矩阵的大小。因此，我们可以枚举所有可能的子矩阵，并判断子矩阵中黑色格子与白色格子数量是否一致即可。
解法类似于 示例问题二。不再赘述。
应用：First Step¶
本题可以采用枚举法解决。
具体思路是：
- 枚举所有空地 $(i,j)$。（通过双重循环和
if语句枚举） - 歌唱队形要么是以 $(i,j)$ 向右站 $k$ 个人，要么以 $(i,j)$ 向下站 $k$ 个人。
- 不考虑向上和向左，会重复计算。
因此进一步向右遍历，检查是否存在至少连续 $k$ 个 . 。
以及向下遍历检查是否存在至少连续 $k$ 个 .。
若存在则 sum = sum + 1 即可。
注意：当 $k=1$ 向下向右会把一个格子连续算两次，需要对答案除以 $2$。
时间复杂度：$O(r\cdot c\cdot (r+c))$。
for (int i = 1; i <= r; i++)
{
for (int j = 1; j <= c; j++)
{
if (a[i][j] == '#') continue;
int sum = 0;
for (int l = j; l <= c; l++)
{
if (a[i][l] == '#') break;
sum++;
}
if (sum >= k) ans++;
sum = 0;
for (int l = i; l <= r; l++)
{
if (a[l][j] == '#') break;
sum++;
}
if (sum >= k) ans++;
}
}
if (k == 1) cout << ans / 2;
else cout << ans;
其余习题¶
[NOIP2018 普及组] 龙虎斗¶
可以发现 $s_1$ 个人出现在 $p_1$ 没什么用，直接令 c[p1] += s1 即可。
因此问题的关键在于 $s_2$ 个人派到何处，使得两边差距的绝对值最小。
注意到 $s_2$ 个人不管是派给龙还是中立还是派给虎。只是新增了一部分气势而已。
- 例如派给龙，假设派到了 $i$ 号位置。
- 则龙的气势在原有的基础上新增了 $s_2\times (m-i)$ 而已。
因此维护这个增量就可以了。
具体思路：
- 初始化先求出 $s_2$ 个人没有派往任何一个地方时，龙和虎各自的势力值。
- 通过循环遍历即可求得。
完成初始化工作后，接下来就是枚举 $s_2$ 个人派到每一个位置 $i$ 对龙和虎产生的影响来计算最终答案。
初始化 $ans=|\text{dragon}-\text{tiger}|$，以及 $\text{pos}=m$。
- 分别记录双方差值的绝对值以及位置。（假设派到 $m$ 最优）
- 求绝对值可以用
abs函数。
接下来枚举 $i$，其中 $i\in [1,n]$。
- 当 $i<m$，则派给了龙。
- 若 $|\text{dragon}+s_2\times (i-m)-\text{tiger}|<ans$。
- 则更新 $ans$，同时记录 $pos=i$。
- 当 $i>m$ 处理方式同上。
最终只需要在 $O(n)$ 的时间内即可求出答案，注意 long long。