暴力枚举
一.循环枚举
例题1
可以通过枚举点的坐标来计算长方形和正方形的个数
普通思路：
枚举所有可能性（通过枚举）：
int main()
{
int n,m,squ=0,rec=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){ //枚举左上角的点
for(int k=i+1;k<=n+1;k++){
for(int z=j+1;z<=m+1;z++){ //枚举右下角的点
if((k-i)==(z-j)){ //满足条件就++
squ++;
}else{
rec++;
}
}
}
}
}
cout<<squ<<" "<<rec;
return 0;
}
该代码可以得出正确答案，可是会TLE，时间复杂度为O(m2n2)，考虑新的枚举策略。
思路一：减少枚举量
枚举一个点，统计以这个点为顶点的方形数量，再除4（每个方形被算了4遍) ，注意long long类型。
int main()
{
int n,m;
long long squ=0,rec=0;
cin>>n>>m;
for(int i=0;i<=n;i++){ //枚举平面每一个点
for(int j=0;j<=m;j++){
long long t=min(j,i)+min(j,n-i)+min(m-j,i)+min(m-j,n-i);
squ+=t;
rec+=n*m-t;
}
}
squ/=4,rec/=4;
cout<<squ<<" "<<rec<<endl;
return 0;
}
思路二：去掉重复的情况
去掉思路一的代码重复的情况。仅仅枚举方形右下角的顶点。
for(int j=0;j<=m;j++){
long long t=min(j,i);
squ+=t;
rec+=i*j-t;
}
思路三：枚举其他要素
如可以枚举方形的边长，枚举a*b的方形数量
for(int i=1;i<=n;i++){ //枚举方形边长
for(int j=1;j<=m;j++){
if(i!=j){
rec+=(m-j+1)*(n-i+1); //简单分析得到公式
}else{
squ+=(m-j+1)*(n-i+1);
}
}
}
例题二
思路一：暴力
可以直接写10层for循环再加一个if判断
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
int main()
{
int n,cnt=0;
cin>>n;
if(n<10){
cout<<"0";
}else{
rep(a,1,3) rep(b,1,3) rep(c,1,3) rep(d,1,3) rep(e,1,3)
rep(f,1,3) rep(g,1,3) rep(h,1,3) rep(i,1,3) rep(j,1,3){
if(a+b+c+d+e+f+g+h+i+j==n){
cnt++;
}
}
cout<<cnt<<endl;
rep(a,1,3) rep(b,1,3) rep(c,1,3) rep(d,1,3) rep(e,1,3)
rep(f,1,3) rep(g,1,3) rep(h,1,3) rep(i,1,3) rep(j,1,3){
if(a+b+c+d+e+f+g+h+i+j==n){
printf("%d %d %d %d %d %d %d %d %d %d\n",
a,b,c,d,e,f,g,h,i,j);
}
}
}
return 0;
}
#define rep(i,a,b) for(int i=a;i<=b;i++) 是宏定义，只会做简单的字符串变换，所以使用时要勤加括号。
思路二：限定变量的范围（枚举剪枝）
当ans已经超过了n，便可以不用再枚举以下的元素。
例题三
思路：减少枚举次数
可以不用枚举9个数字，只需要枚举出一个三位数，便可以通过比例确定另外两个数。
#include <bits/stdc++.h>
using namespace std;
int s[10];
void go(int x) //分解3位数到桶里
{
s[x%10]=1;
s[x/10%10]=1;
s[x/100]=1;
}
bool check(int x,int y,int z)
{
if(z>999){ //保证三位数
return 0;
}
go(x),go(y),go(z); //保证1-9每个数都存在
for(int i=1;i<10;i++){
if(!s[i]){
return 0;
}
}
return 1;
}
int main()
{
long long a,b,c,x,y,z,cnt=0;
cin>>a>>b>>c;
if(a==0||b==0||c==0){ //排除特殊数据
cout<<"No!!!"<<endl;
}
for(x=123;x<=987;x++){ //枚举第一个三位数
if(x*b%a||x*c%a){ //判断后两位数是否存在
continue;
}
y=x*b/a;
z=x*c/a;
if(check(x,y,z)){ //函数判断三个数是否符合要求
cnt++;
cout<<x<<" "<<y<<" "<<z<<endl;
}
memset(s,0,sizeof(s));
}
if(cnt==0){
cout<<"No!!!"<<endl;
}
return 0;
}
总结
循环枚举可以通过如下方式优化
- 根据题目减少枚举量
- 去掉重复情况
- 枚举其他要素
- 枚举裁剪
除以上常见策略，同时也要通过做题来积累常见简化方法。