注:本帖为搬运帖，在原作者基础上本蒻蒟稍加改动（） 原贴：https://zhuanlan.zhihu.com/p/634162167

2 暴力枚举的方法论与优化技巧 – 大力出奇迹

暴力枚举法（Brute Force）:

是许多刚接触编程或算法的选手最容易上手，也最明显的算法。虽然暴力枚举往往效率极低，但是可以很快地解决一些问题。

本文将介绍暴力枚举法的方法和优化技巧。注意本文中许多名字并非专业学名，而是我自己定义的，请不要过于纠结。

1.确定解的形式（枚举变量）

在进行暴力之前，我们需要分析出解的形式，比如要求满足条件的三元组的个数，我们就枚举所有三元组，检查哪些满足条件。比如我们要求满足条件的区间的个数，就可以枚举所有的二元组（表示左右端点）。

有些题目解的形式可能不太唯一，需要选择合适的形式，对于不同的形式选择不同的枚举方法。比如枚举子集，可以用循环，也可以用dfs，有时候在能够剪枝的情况下，dfs会比循环直接枚举子集快很多。

2.选择枚举方法

常见的枚举方法有直接枚举法和递归枚举法，根据题目不同，有时候也可能有用一些构造方法来进行枚举。

常见的直接枚举（循环）不会超过4层循环，且循环层数固定。

如果你发现循环层数是可变的，往往就要用递归枚举，比如你要枚举所有长度小于等于的一个东西，就需要用到递归。

3.判断函数

在枚举出一个解后，我们需要判断其是否是可行解，于是我们要写一个判断函数。

这个判断函数可以根据你枚举出的一个解，来判断这个解是否可能。

举个栗子:

我们要求范围的所有质数

那么我们解的形式就是一个整数，于是我们遍历解空间的所有解，说人话就是的所有整数，然后编写判断函数，用于判断一个解是否是可行解，即判断一个数字是否是质数，并执行操作: 例题-点击查看

这道题看数据范围，明显支持，所以可以大胆地暴力，枚举所有的三元组，并判断是否满足条件即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef ll = long long;
const ll N = 1e6 + 9, inf = 8e18;
ll a[N];
bool check(ll a, ll b, ll c, ll m)
{
    return (a + b + c) * (a ^ b ^ c) >= m;
}
void solve()
{
	int n, m;cin >> n >> m;
	for(int i = 1;i <= n; ++ i)cin >> a[i];
		ll ans = 0;
		for(int i = 1;i <= n; ++ i)
			for(int j = i + 1;j <= n; ++ j)
				for(int k = j + 1;k <= n; ++ k)
					if(check(a[i], a[j], a[k], m)) ans ++;
	cout<<ans<<"\n";
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int nn = 1;
    while(nn--)solve();
    return 0;
}

全排列-例题-点击查看

暴力枚举，但是我们发现这次用循环来写其实不好写了，所以改用递归。

注意需要按照字典序升序来写。 代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 20, inf = 8e18;
ll a[N];
bitset<N> vis;
void dfs(ll dep, ll n)
{
    if(dep == n + 1)
    {
     for(ll i = 1;i <= n; ++ i)cout << a[i] << " \n"[i == n];
        return;
    }
    for(ll i = 1;i <= n; ++ i)
    {
        if(vis[i])continue;
        vis[i] = true;
        a[dep] = i;
        dfs(dep + 1, n);
        vis[i] = false;
    }
}
void solve()
{
    ll n;cin >> n;
    dfs(1, n);
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _ = 1;
    while(_ --)solve();
    return 0;
}

本次对暴力算法的内容到此结束 感谢阅读，喜欢的点个关注吧！