枚举

暴力枚举

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

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

洛谷 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;
}

洛谷 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. 火星人

课后习题

1. 洛谷 P3392. 涂国旗
2. 洛谷 P3654. First Step
3. 洛谷 P1217. 回文质数
4. 洛谷 P1149. 火柴棒等式
5. 洛谷 P3799. 妖梦拼木棒
6. 洛谷 P2036. Perket
7. 洛谷 P1433. 吃奶酪