枚举

枚举法又称穷举法，根据题中的约束条件，将解的所有可能情况一一列举出来，然后再逐个验证该解是否符合整个问题的求解要求，从而求得问题的可行解或最优解。

暴力枚举

暴力枚举一般使用多重循环来实现，没有什么固定的套路。但是，我们可以尽力优化枚举思路，提高枚举效率。

下面以几道习题为例，来说明如何优化枚举思路。

洛谷 P2241. 统计方形（数据加强版）

分析：对于棋盘上的任意两点（不同行、不同列）来说，它们可以唯一确定一个方形。至于是正方形还是长方形，我们还需要根据横向和纵向距离进行判断。这样的枚举时间复杂度是 $O(n^2{m}^2)$ 的，不能通过这道题目。能不能减少枚举量呢？

思路 1：枚举方形的右下角坐标 $(x,y)$，而左上角与 $(x,y)$ 构成斜线上的格点均能与之确定一个正方形，正方形的数量是 $min(x,y)$。除左上角斜线上的点外，其余格点均能与之确定一个长方形，长方形的数量是 $x\ast y-min(x,y)$。

// A 记录正方形的数量，B 记录长方形的数量
long long A = 0, B = 0;
for (long long x = 1; x <= n; x++) {
    for (long long y = 1; y <= m; y++) {
        A += min(x, y);
        B += x * y - min(x, y);
    }
}

思路 2：枚举边长？问题就变成了 $n\times m$ 的大矩形里有多少个边长为 $a\times b$ 的小矩形。那么如何计算小矩形的数量呢？考虑小矩形右上角有多少种可能性 $(n-a+1)\times (m-b+1)$。

long long A = 0, B = 0;
for (long long a = 1; a <= n; a++) {
    for (long long b = 1; b <= m; b++) {
        if (a == b) {
            A += (n - a + 1) * (m - b + 1);
        } else {
            B += (n - a + 1) * (m - b + 1);
        }
    }
}

洛谷 P2089. 烤鸡

分析：暴力枚举，十重循环。由题意可知，美味程度最多是 $30$，最小是 $10$，其他的美味程度均是不可达到的。为此我们可以选择枚举每种调料的用量。

int n, ans = 0;
cin >> n;

for (int a = 1; a <= 3; a++) {
    for (int b = 1; b <= 3; b++) {
        for (int c = 1; c <= 3; c++) {
            for (int d = 1; d <= 3; d++) {
                for (int e = 1; e <= 3; e++) {
                    for (int f = 1; f <= 3; f++) {
                        for (int g = 1; g <= 3; g++) {
                            for (int h = 1; h <= 3; h++) {
                                for (int i = 1; i <= 3; i++) {
                                    for (int j = 1; j <= 3; j++) {
                                        if (a + b + c + d + e + f + g + h + i + j == n) ans++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

cout << ans << endl;

for (int a = 1; a <= 3; a++) {
    for (int b = 1; b <= 3; b++) {
        for (int c = 1; c <= 3; c++) {
            for (int d = 1; d <= 3; d++) {
                for (int e = 1; e <= 3; e++) {
                    for (int f = 1; f <= 3; f++) {
                        for (int g = 1; g <= 3; g++) {
                            for (int h = 1; h <= 3; h++) {
                                for (int i = 1; i <= 3; i++) {
                                    for (int j = 1; j <= 3; j++) {
                                        if (a + b + c + d + e + f + g + h + i + j == n) {
                                            cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << " " << g << " " << h << " " << i << " " << j << endl;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

当然，对于每种调料我们都可以计算它的上下限，例如对于调料 $e\in [n-15-a-b-c-d,n-5-a-b-c-d]$，即假设后面的调料均取 $3$ 所达到的下限，假设后面的调料均取 $1$ 所达到的上限，那么我们可以枚举 $e$ 的取值范围，从而减少枚举量。

洛谷 P1618. 三连击（升级版）

分析：当然我们可以写出九重循环，枚举每一个数位，拼凑成三个三位数，然后计算是否符合题目要求即可，时间复杂度是 $O({10}^9)$。但是这样的枚举量太大，我们需要优化。进一步我们可以枚举每一个三位数（每一个数字的枚举语句如：for (int x = 123; x <= 987; x++)），然后检查这三个数是否满足题目要求即可，还能再优化吗？

思路：我们可以枚举其中一个三位数，然后根据比值关系计算出另外两个三位数，检查是否满足题目要求即可。

int main() {
	long long a, b, c; cin >> a >> b >> c;

    if (a == 0 || b == 0 || c == 0) {
        cout << "No!!!" << endl;
        return 0;
    }

	int vis[10], cnt = 0;
	for (long long i = 123; i <= 987; i++) {
        if (i * b % a || i * c % a) continue;
        long long j = i * b / a, k = i * c / a;

        if (j > 999 || k > 999) continue;

        for (int n = 1; n <= 9; n++) vis[n] = 0;
        vis[i % 10] = vis[i / 10 % 10] = vis[i / 100] = 1;
        vis[j % 10] = vis[j / 10 % 10] = vis[j / 100] = 1;
        vis[k % 10] = vis[k / 10 % 10] = vis[k / 100] = 1;

        bool flag = true;
        for (int n = 1; n <= 9; n++) {
            if (!vis[n]) {
                flag = false;
                break;
            }
        }

        if (flag) {
            cnt++;
            cout << i << " " << j << " " << k << endl;
        }
	}
	if (!cnt) cout << "No!!!" << endl;

    return 0;
}

集合枚举

子集枚举

对于一个有 $n$ 个元素的集合，我们可以使用 $0\sim 2^n-1$ 这 $2^n$ 个数字，也即是 $2^n$ 个状态来表示它的每一个子集（包括空集和全集）。

对于状态 $i$，如果第 $j$ 位为 $1$，则表示选择了集合中第 $j$ 个元素，否则表示不选择。

洛谷 P1036. 选数

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

const int N = 25;
int n, k, cnt, a[N];

// 判断 n 是否为质数
bool is_prime(int n) {
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) return false;
    }

    return true;
}

int lowbit(int x) {
    return x & -x;
}

// 求 n 的二进制表示中 1 的个数
int has(int n) {
    int cnt = 0;
    for (int x = n; x; x -= lowbit(x)) {
        cnt++;
    }

    return cnt;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];

    // 枚举所有可能的状态
    for (int i = 0; i < (1 << n); i++) {
        // 状态 i 中 1 的个数，也即是选择的数的数量是否为 k
        if (has(i) == k) {
            int s = 0;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) s += a[j];
            }
            if (is_prime(s)) cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

注意：对于上述代码中的 has 函数，我们也可以使用 __builtin_popcount 函数来计算二进制表示中 $1$ 的个数，例如 has(i) = __builtin_popcount(i)。

洛谷 P1157. 组合的输出

分析：本题和上一题类似，关键在于如何处理字典序。题目要求按字典序从小到大输出，我们可以考虑倒序枚举，二进制的每一位从高位到低位分别表示数字 $1$ 到 $n$，这样的话我们就可以让 $1$ 尽可能的出现在最左侧，例如 $10110$ 早于 $10101$，符合题目要求。

for (int i = (1 << n) - 1; i >= 0; i--) {
    if (has(i) == m) {
        for (int j = n - 1; j >= 0; j--) {
            if (i & (1 << j)) {
                cout << setw(3) << n - j;
            }
        }
        cout << endl;
    }
}

集合枚举

1. 枚举所有状态的非空子集的代码如下：

// i 从 1 开始枚举状态，n 为状态数
for (int i = 1; i < (1 << n); i++) {
    // 枚举状态 i 的非空子集
    for (int j = i; j; j = (j - 1) & i) {
        // j 遍历了 i 的所有非空子集
    }
}

时间复杂度 $O(3^n)$。

1. 枚举超集的代码如下：

for (int i = 0; i < (1 << n); i++) {
    for (int j = i; ; j = (j + 1) | i) {
        // j 遍历了 i 的所有超集
        if (j == (1 << n) - 1) break;
    }
}

时间复杂度 $O(3^n)$。

排列枚举

STL 中的 next_permutation 函数可以用来枚举所有排列。例如 $[2,3,1]$ 的下一个排列是 $[3,1,2]$，而 $[3,1,2]$ 的下一个排列是 $[3，2，1]$。

洛谷 P1618. 三连击（升级版）

分析：上面我们说了可以直接使用九重循环枚举每一个数字，拼凑成三个三位数，这样的话时间复杂度为 $O(9!)$，其实还算 OK。这里我们给出使用 next_permutation 函数的简单写法。

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

int main() {
    int A, B, C; cin >> A >> B >> C;

    int cnt = 0, a[10];

    for (int i = 1; i <= 9; i++) a[i] = i;

    do {
        int x = a[1] * 100 + a[2] * 10 + a[3];
        int y = a[4] * 100 + a[5] * 10 + a[6];
        int z = a[7] * 100 + a[8] * 10 + a[9];

        if (x * B == y * A && y * C == z * B) {
            cout << x << " " << y << " " << z << endl;
            cnt++;
        }
    } while (next_permutation(a + 1, a + 10));

    if (!cnt) puts("No!!!");

    return 0;
}

下面再给出两道习题来练习 next_permutation 的使用。

1. 洛谷 P1706. 全排列问题
2. 洛谷 P1088. 火星人