枚举经典例题

1 UVA725 除法

问题：输入正整数 $n$ ，按从小到大的顺序输出所有形如 $abcde/fghij=n$ 的表达式，其中 $a\sim j$ 恰好为数字 $0\sim 9$ 的一个排列（可以有前导零） $2\le n\le 79$

// 输入
62

// 输出
79546 / 01283 = 62
94736 / 01528 = 62

分析：如果我们选择枚举 $0\sim 9$ 的所有排列，那么时间复杂度是 $O(n!)$ ，有必要这么做吗？只枚举 $fghij$ 就可以算出来 $abcde$，然后判断是否所有数字都不相同即可，而且当 $abcde$ 和 $fghij$ 加起来超过 10 位时可以终止枚举，时间复杂度下降至不到 1 万。

2 UVA11059 最大乘积

问题：输入 $N$ 个元素组成的序列 $S$，你需要找出一个乘积最大的连续子序列。如果这个最大乘积不是正数，应输出 $0$。$1\le N\le 18-10\le S_i\le 10$

// 输入
3
2 4 -3
// 输出
8

// 输入
5
2 5 -1 2 -1
// 输出
20

分析：枚举连续子序列的起点和终点，计算最大值。由于每个元素的绝对值不超过 $10$，且个数不超过 $18$，则最大乘积不超过 ${10}^{18}$，使用 long long 存储。

3 分数拆分

问题：输入正整数 $k$，找到所有的正整数 $x\le y$，使得 $\frac{1}{k}=\frac{1}{x}+\frac{1}{y}$。

// 输入
2
// 输出
2
1/2 = 1/6 + 1/3
1/2 = 1/4 + 1/4

分析：由于 $x\le y$，有 $\frac{1}{x}\le \frac{1}{y}$，即 $y\le 2k$ 此时可以枚举 $y$，根据 $y$ 计算出 $x$。

4 火柴棒等式

给你 $n(1\le n\le 24)$ 根火柴棍，你可以拼出多少个形如 $A+B=C$ 的等式？等式中的 $A$、$B$、$C$ 是用火柴棍拼出的整数（若该数非零，则最高位不能是 $0$）。用火柴棍拼数字 $0\sim 9$ 的拼法如图所示：

注意：

1. 加号与等号各自需要两根火柴棍；
2. 如果 $A\ne B$，则 $A+B=C$ 与 $B+A=C$ 视为不同的等式（$A,B,C\ge 0$）；
3. $n$ 根火柴棍必须全部用上。

14

2

// 输入
18
// 输出
9

总结反思

枚举算法本质上就是假设出更多的条件，把原问题从复杂转换成简单，方便我们设计算法求解。

举例：给定一个整数 $n(n\le 1000000)$，求所有合法的 $x,y,z$ 满足下述条件：

1. $x\le y\le z$
2. $n=x^2+y+z^2$

样例输入：

105

样例输出：

1 4 10
4 8 9
7 7 7

分析：我们只需要枚举 $x,y,z$ 就可以把原问题的求解问题转换成合法性判定问题。从小到达枚举 $x,y,z$ 显然可以，但是有没有更好的办法呢？

只枚举 $x,z$ 由等式 $n=x^2+y+z^2$ 计算 $y$，之后判断 $y$ 是否在区间 $[x,y]$ 中即可。

为什么选择 $x,z$？因为 $x,z$ 的范围最大只能到 $1000$，可以显著减少我们的枚举量。

枚举专题补充

枚举算法的本质是提供条件，把问题转换为简单的问题。设计枚举算法的核心就是用尽量少的枚举内容，去提供更多的信息，以来简化问题。

举例：现在有 $n(n\le {10}^5)$ 个变量 $x_1,x_2,x_3\dots x_n$，每个变量的取值都是 $[1,n]$ 范围内的正整数。现在有 $n$ 个方程，第 $i$ 个方程是 $a_i{x}_i+b_i{x}_{i+1}+c_i{x}_{i-1}=d_i$。其中：对于 $i=1$, $x_{i-1}$ 表示 $x_n$，对于 $i=n$，$x_{i+1}$ 表示 $x_1$。

样例输入：

x[1] + x[2] + x[4] = 7
2x[2] + x[3] + 3x[1] = 10
x[3] + x[4] - x[2] = 5
x[4] + 2x[1] + x[3] = 9

样例输出：

x[1] = 1
x[2] = 2
x[3] = 3
x[4] = 4

分析：很自然的我们会想到依次枚举 $x_1,x_2\dots x_n$ 的值，然后去检验是否符合条件即可。不过，这样做的枚举量高达 $n^n$ 并且请你想一想代码好写吗？

换一种思路，我们尝试枚举 $x_n$ 和 $x_1$。利用第一个方程可以解得 $x_2$ 的值。利用第二个方程可以解得 $x_3$ 的值。依次类推，利用第 $n-2$ 个方程，我们可以解得 $x_{n-1}$ 的值，最后检查一下看看是否满足最后两个方程即可。这样做我们只需要枚举两个变量，然后循环 $n$ 次检验合法性即可。时间复杂度 $O(n^3)$。

可以继续优化吗？只枚举一个值，假设为 $x_4$，依次带入每一个方程，求出每一个变量的表示形式，直接求解。

具体如下：假设 $x_4=4$

带入第一个方程：$x_2=3-x_1$

带入第二个方程：$x_3=4-x_1$

带入第三个方程：$x_4=4+0x_1$

此时利用第四个方程 $x_4+2x_1+x_3=9$，带入上式可得 $x_1$，进而求解其他变量。

更进一步，什么都不枚举，直接带入变量形式。

带入第一个方程：$x_2=7-x_1-x_4$

带入第二个方程：$x_3=2x_4-x_1-4$

联立最后两个方程，求解即可。

双指针算法

对于一些问题，我们需要枚举变量 $x$，计算对于 $x$ 时候的答案 $an{s}_x$。假设我们计算 $an{s}_x$ 的时候，需要枚举 $an{s}_x$，然后检验答案的合法性。那么在这个时候，我们需要枚举两个变量 $x,an{s}_x$。有的时候，$x,an{s}_x$ 会有明显的上下界，比如 $1\le x\le an{s}_x\le n$。这时候，也许还会有一些明显的性质，比如：$an{s}_{x}lean{s}_{x+1}$ 对于任意 $x$ 都成立。那么，我们可以考虑使用双指针的办法来优化我们的枚举量。

例如，一些题目问：最小找到一个多长的区间 $[l,r]$ 满足题目中要求的条件。暴力枚举的代码一般长这样：

for (int i = 1; i <= n; i++) {
	for (int j = x; j <= n; j++) {
		if (is_ok(x, y)) {
			ans[x] = y;
			break;
		}
	}
}

双指针实现：

int y = 1;
for (int i = 1; i <= n; i++) {
	while (!is_ok(x, y) && y <= n) y++;
	if (is_ok(x, y)) ans[x] = y;
}

还记得奶牛的舞会这道题吗？

有 $n$ 头牛，每头牛都一个长度 $L_i$ 有一件长度为 $S$ 的服装，如果两头牛的长度之和不超过 $S$ 那么她们就能穿下这套服装。问：选择两头不同的奶牛来穿这套衣服，一共有多少种满足条件的方案。

我们可以使用双指针解决它。

#include <bits/stdc++.h>
using namespace std;

const int N = 50010;
int L[N];

int main() {
	int n, s;
	cin >> n >> s;
	for(int i = 0; i < n; i++) cin >> L[i];

	sort(L, L + n);

	int res = 0;
    int i = 0, j = n - 1;
    while (i < j) {
        if (L[i] + L[j] <= s) {
            res += j - i;
            i++;
        }
        else {
        	j--;
        }
    }
	cout << res << endl;

	return 0;
}

课后习题

问题 #1

有一个长度为 $n(n\le {10}^5)$ 的数组 $a$，问，在里面选两个位置 $(i,j)$ 其中 $(j<i)$，问：$a_i-a_j$ 的最大值是多少？

问题 #2

有一个长度为 $n(n\le {10}^5)$ 的数组 $a$，问，在里面选两个位置 $(l,r)$ 其中 $(l\le r)$，问：$a_l+a_{l+1}+\cdots +a_r$ 的和的最大值是多少？

问题 #3

校门外有连续的 $n(n\le {10}^7)$ 棵树，现在来了一个拆迁队，一共拆迁了 $m(m\le {10}^5)$ 次。第 $i$ 次拆迁，是把从第 $l_i$ 到 $r_i$ 棵树铲走（如果已经没了就不用管）。问最后还剩几棵树？

问题 #4

给你一个大小为 $n$ 行 $m$ 列的矩阵，每个位置上有一个数字，问：边长恰好为 $k$ 的正方形，和最大是多少？$n,m\le 1000,k\le min(n,m)$

问题 #5

给你 $n(n\le 100)$ 个数字，每个数字都小于等于 ${10}^6$，其中若干个位置用 * 代替，例如：

15*
1*0
1**
1*1*
1**1

已知这 $n$ 个数字从上到下是递增的，请输出所有数字都最小的方案。

问题 #6

有 $n$ 个人，从 $1$ 开始报数，报到 $k$，再变成 $1$，也就是报数序列是 $1,2,3\dots k,k-1\dots 2,1,2,3\dots$ 现在已知你是第 $n$ 个人，报的是 $x$，问：$k$ 有多少种不同的可能？$1\le x<n\le {10}^9$