13.暴力枚举

发表于 2025-03-19 更新于 2025-03-27 分类于 ACM ， ACMCOURSE

暴力枚举

只要复杂度没问题，暴力又如何？

以合理的方式，不重复、不遗漏地枚举一个问题所有可能的答案，找到正确的或最优的那个。

基本的枚举

暴力需要艺术，不是盲目地暴力，而要通过观察分析问题的特点，有选择地枚举。

例：除法

abcdefghij是0~9的一个排列，给出 \(2\leq n \leq 79\)，输出所有 \(abcde / fghij = n\) 的情况

输入

输出

1 2	79546 / 01283 = 62 94736 / 01528 = 62

直观的暴力是枚举0~9的所有排列，这是 \(10!=362880\) 种情况，或许能通过此题，但数据范围再扩大呢（比如用16进制，甚至更高）？而且枚举排列的代码量也不少。

如果只枚举 fghij，复杂度就会极大降低，甚至不用枚举排列，只需要枚举五位数，判断各位是否不同，然后用 \(n * fghij\) 得到 \(abcde\)，再判断一次各位是否不同就可以了。

例：统计方形

给出 \(n\leq 5000, m\leq 5000\)，求 \(n \times m\) 的方格棋盘正方形、不含正方形的长方形分别有多少个。

直观的暴力是枚举所有左上角和右下角，但这过于暴力了， \(O(n^{2}m^{2})\) 的复杂度也很恐怖。

而如果想用纯数学方法算出来也可以，就比较烧脑。

可以充分利用计算机的优势，在可接受复杂度内枚举，并一定程度结合计算，达到思维量和程序复杂性的平衡。

于是可以这样，枚举右下角，计算以枚举的格子为右下角的正方形个数，和含正方形在内的矩形总个数（这比只算矩形要容易些），进而再计算不含正方形的矩形个数。

估算一下数量可知，总数应该超过 int 了，得用 long long 统计

#include<stdio.h>
#include<string.h>
#include<algorithm>
int main() {
    int n, m;
    long long sq = 0, all = 0;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            sq += std::min(i, j) + 1;   // 以(i,j) 为右下角的正方形个数
            all += (i + 1) * (j + 1);   // 以(i,j) 为右下角的含正方形矩形个数
        }
    }
    printf("%lld %lld\n", sq, all - sq);
    return 0;
}

基本的回溯

回溯的本质是搜索，只不过不是在直观的图上搜索，而是在答案所在的空间中，以某种模式去搜索，比如一堆数字的全排列，一堆物件的各种组合（子集）等等。

不重复不遗漏的搜索过程，构成一棵搜索树，所以某种意义上说，回溯是树上的搜索，通常以深度优先搜索形式实现。

枚举排列

枚举排列就是在 \(n\) 个位置放 \(n\) 个对象，变换他们的顺序，把 \(n!\) 种顺序都枚举出来。

定义排列的字典序：第一个不相同的较小元素所在的排列字典序更小，例如1,2,3的字典序小于1,3,2，按字典序输出排列

思路：尝试第一个数的所有可能，然后第二个……一棵搜索树：

参考代码

void DFS(int cur) {     // cur 指 "current", 当前在确定第 cur 个位置是谁
    if(cur == n) {                              // 递归终点
        for(int i = 0; i < n; i ++)             // 输出一个排列
            printf(" %d" + !i, record[i]);
        printf("\n");
        return;                                 // 注意return
    }
    for(int i = 0; i < n; i ++) {               // 枚举每个元素
        if(vis[i]) continue;                    // 已放元素排除
        vis[i] = true; record[cur] = a[i];      // 标记已放本次排列第cur个为a[i]
        DFS(cur + 1);                           // 递归放第cur+1个
        vis[i] = false;                         // 回溯取消标记
    }
}

例：可重排列

如果有重复元素怎么办：\({2,1,1,4}\)

按字典序生成排列为（先从左到右、后从上到下）：

1 2	1 1 2 4；1 1 4 2；1 2 1 4；1 2 4 1；1 4 1 2；1 4 2 1 2 1 1 4；2 1 4 1；2 4 1 1；4 1 1 2；4 1 2 1；4 2 1 1

思路：数据排序后处理重复，统计每种数的数量cnt，用cnt“还剩下的可用个数”代替vis所表达的“是否放过”。

枚举子集

给定 \(n\) 元素集合，按字典序输出所有子集

思路：子集即每个元素取与不取（是否算在递归终点时得到的子集里），可通过二进制方式构造

枚举排列中的record记录第cur个位置放哪个数，那么在枚举子集中，可以用chose记录第cur个元素取还是没取。

void DFS(int cur) {
    if(cur == -1) {                             // 递归终点,所有元素都已确定
        for(int i = 0, flg = 1; i < n; i ++){   // 输出子集
            if(!chose[i]) continue;
            printf(" %d" + flg, a[i]); flg = 0;
        }
        printf("\n");
        return;                                 // 注意return
    }
    // 由n-1~0逆序以便按字典序枚举子集
    chose[cur] = false; DFS(cur - 1);           // 不取a[cur]后确定第cur-1个
    chose[cur] = true; DFS(cur - 1);            // 取a[cur]后确定第cur-1个
}

指数增长很快，通常需要生成子集的问题不会太大，int的二进制位存得下 chose 所表达的信息，从而可以通过枚举连续的整数（二进制位）来枚举子集：

int m = 1 << n;
for(int i = 0; i < m; i ++) {
    for(int j = 0, flg = 1; j < n; j ++) {
        if((i >> j) & 1) {
            printf(" %d" + flg, a[j]);
            flg = 0;
        }
    }
    printf("\n");
}

知识点：位运算，<<,>>,|,&,^ 是几个针对整数型变量的二进制位进行操作的运算，1<<m指把1的二进制位向“左”移m位。
int的1 的二进制位是 0000000000000000000001（\(31\)个0，\(1\)个1，共\(32\)位），左移2位的话，就变成0000000000000000000100，对应表达的数字是 4。
(i >> j) & 1 就是把 i 右移 j 位之后，再与 0000000000000000000001 每个二进制位分别做一下“与”操作，(i >> j) & 1 就会过滤掉前31个位（无论0还是1，“与”一下0都会变成0），只看最低的位“与”1之后的结果，用来判断 i的第j个位是否是j。

例：枚举\(r\)子集

枚举特定大小的子集，在枚举过程中只输出“取\(r\)”个的情况即可。

基本回溯

例：n皇后

规定棋子可以攻击同一行、同一列、同一斜线的棋子求在 \(n\times n\) 的棋盘上放置 \(n\) 个棋子，互相攻击不到的方法

\(4\) 皇后示例：

以\(8\)皇后为例分析问题规模

枚举每个格子放与不放？\(2^{64}\)太离谱
\(64\) 个格子取 \(8\) 个？\(C_{64}^{8}\)也很离谱
结合约束条件，可极大简化要枚举的内容：每行选 \(1\) 列，行行不重复，各行选的列编号拿出来放一起，就是\(1\sim 8\)的排列！

进一步优化，对于每个格子，它属于：

\(n\)列中的\(1\)列
\(2n−1\)个正斜线的\(1\)个
\(2n−1\)个反斜线的\(1\)个

枚举排列时，可增加两组斜线占领标记，减少状态枚举。

参考代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
const int maxn = 14;
int n;
int ans[maxn];
bool rcdx[maxn], rcdlr[maxn << 1 | 1], rcdrl[maxn << 1 | 1];
void DFS(int cur) {
    if(cur == n) ans[n] ++;
    for(int i = 0; i < n; i ++) {
        if(rcdx[i] || rcdlr[i - cur + n - 1] || rcdrl[i + cur]) 
            continue;
        rcdx[i] = true;
        rcdlr[i - cur + n - 1] = true;  // 左上-右下 对角线标记
        rcdrl[i + cur] = true;          // 右上-坐下 对角线标记
        DFS(cur + 1);
        rcdx[i] = false;
        rcdlr[i - cur + n - 1] = false;
        rcdrl[i + cur] = false;
    }
}
int main() {
    memset(ans, -1, sizeof(ans));
    memset(rcdx, 0, sizeof(rcdx));
    memset(rcdlr, 0, sizeof(rcdlr));
    memset(rcdrl, 0, sizeof(rcdrl));
    while(scanf("%d", &n) != EOF)
    {
        if(ans[n] == -1)
        {
            ans[n] = 0;
            DFS(0);
        }
        printf("%d\n", ans[n]);
    }
    return 0;
}

例：着色问题

给定\(n\)个顶点的无向连通图 \(G\) 和 \(m\) 种不同颜色，每个顶点涂一种颜色，要求每条边的两个顶点颜色不同，求方案个数。

6个点3种颜色示例：

回顾枚举子集：每个点取与不取，取值是0或1，把这个思路扩展一下，每个点颜色有0、1、2 三种选择，其实和枚举子集是同一套思路。

参考代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

const int maxn = 111;
int n, m, q, u, v, color[maxn], ans;
bool g[maxn][maxn];
bool Judge(int cur, int ci) {
    // 判断cur是否能涂ci色
    for(int j = 1; j <= n; j ++)
        if(color[j] == ci && g[cur][j])
            return false;
    return true;
}
void DFS(int cur) {
    if(cur == n + 1) {
        ans ++;
        return;
    }
    for(int i = 1; i <= m; i ++) {
        if(!Judge(cur, i)) continue;
        color[cur] = i; // cur节点尝试i颜色
        DFS(cur + 1);
        color[cur] = 0; // 回溯，取消颜色标记
    }
}
int main() {
    while(scanf("%d%d%d", &n, &m, &q) != EOF) {
        memset(g, 0, sizeof(g));
        memset(color, 0, sizeof(color));
        while(q --) {
            scanf("%d%d", &u, &v);
            g[u][v] = g[v][u] = true;
        }
        ans = 0;
        color[1] = 1;  // 对称问题对节点1只计算一种颜色即可
        DFS(2);
        printf("%d\n", ans * m);
    }
    return 0;
}