暴力枚举法(Brute Force)是许多刚接触编程或算法的选手最容易上手,也最显著的算法。尽管暴力枚举往往效率极低,然而能够很快地解决一些问题。
本文将介绍暴力枚举法的办法和优化技巧。留神本文中许多名字并非业余学名,而是我本人定义的,请不要过于纠结。
作者:Eriktse
简介:19岁,211计算机在读,CCPC全国赛金牌,ICPC区域赛银牌服役选手力争以通俗易懂的形式解说编程和算法!❤️欢送关注我,一起交换C++/Python算法。(优质好文继续更新中……)
欢送加群一起游玩~QQ群:600240150
1.确定解的模式(枚举变量)
在进行暴力之前,咱们须要剖析出解的模式,比方要求满足条件的三元组的个数,咱们就枚举所有三元组,查看哪些满足条件。比方咱们要求满足条件的区间的个数,就能够枚举所有的二元组(示意左右端点)。
有些题目解的模式可能不太惟一,须要抉择适合的模式,对于不同的模式抉择不同的枚举办法。比方枚举子集,能够用循环,也能够用dfs,有时候在可能剪枝的状况下,dfs会比循环间接枚举子集快很多。
2.抉择枚举办法
常见的枚举办法有间接枚举法和递归枚举法,依据题目不同,有时候也可能有用一些构造方法来进行枚举。
常见的间接枚举(循环)不会超过4层循环,且循环层数固定。
如果你发现循环层数是可变的,往往就要用递归枚举,比方你要枚举所有长度小于等于$n$的一个货色,就须要用到递归。
3.判断函数
在枚举出一个解后,咱们须要判断其是否是可行解,于是咱们要写一个判断函数。
这个判断函数能够依据你枚举出的一个解,来判断这个解是否可能。
举个例子
咱们要求范畴$[1, n]$的所有质数。
那么咱们解的模式就是一个整数,于是咱们遍历解空间$x \in [1, n], x \in Z^+$的所有解,说人话就是$[1, n]$的所有整数,而后编写判断函数,用于判断一个解$x$是否是可行解,即判断一个数字$x$是否是质数,并执行操作:[YES->将解退出到解集中,NO->舍弃
]。
例题
ETOJ 1014: straax'aks Array
链接:http://oj.eriktse.com/problem.php?id=1014
这道题看数据范畴,显著反对$O(n^3)$,所以能够大胆地暴力,枚举所有$i < j < k$的三元组,并$O(1)$判断是否满足条件即可。
代码:
#include <bits/stdc++.h>using namespace std; using 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 << a[i] << ' ' << a[j] << ' ' << a[k] << '\n'; } cout << ans << '\n';} signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _ = 1; while(_ --)solve(); return 0;}
ETOJ 1016: 全排列
链接:http://cdn.oj.eriktse.com/problem.php?id=1016
暴力枚举,然而咱们发现这次用循环来写其实不好写了,所以改用递归。
留神须要依照字典序升序来写。
代码:
#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;}