在算法竞赛中，很多问题是来不及用数学公式推导出来的。或者说根本就找不到数学规律，这时我们就需要使用枚举来暴力破解。
不过枚举也是需要脑子的，一味的暴力只能超时。因此我这里选择了几道mooc上经典的题目来做复习。
1、完美立方。
思路：
从2到N枚举a的值，2到a枚举d的值，2到d的枚举b的值，2到c枚举b的值。当
满足a*a*a==b*b*b+c*c*c+d*d*d
的时候对结果输出。
代码如下：
#include <iostream> using namespace std; int main() { int N; cin>>N; for(int a=2;a<=N;a++){ for(int d=2;d<=a;d++){ for(int c=2;c<=d;c++){ for(int b=2;b<=c;b++){ if(a*a*a==b*b*b+c*c*c+d*d*d) cout<<"Cube = "<<a<<", Thiple = ("<<b<<","<<c<<","<<d<<")"<<endl; } } } } return 0; }
运行结果如下：
2、生理周期
做此题我们首先会有个思路就是从d+1开始一个一个尝试，直至满足条件(
(k-p)%23==0&&(k-e)%28==0&&(k-i)%33==0)
所以我们很轻易地就能写出对应的代码。代码如下：
#include <iostream> using namespace std; int main(){ int p,e,i,d,N=0; while(cin >> p >> e >> i >> d&&p!=-1) { int k; for(k=d+1;(k-p)%23||(k-e)%28||(k-i)%33;k++); cout<<"Case "<<++N<<": The next triple peak occurs in "<<k-d<<" days."<<endl; } return 0; }
不过在此我们是否会有个疑问。一个一个的尝试是否过于浪费时间了？
这里我们给出另一种思路。
我们先枚举出k+1后，第一个满足高峰的时间点作为第一种高峰的基数，这时我们需要等到k-p%23==0的时候停止。
这时的k代表着满足了k-p。
然后我们枚举下一种高峰的时间基数。这次我们每次只需要+23就够了。因为23以内肯定不满足第一种高峰。
随后我们再枚举第三个满足高峰的时间点的基数，这个基数-d就是我们最终的答案，这次我们每次跳过23*28个单位即可。
总体代码如下所示。
#include <iostream> using namespace std; int main(){ int p,e,i,d,N=0; while(cin >> p >> e >> i >> d&&p!=-1) { int k; for(k=d+1;(k-p)%23;k++);//c++中正数就是true for(;(k-e)%28;k+=23); for(;(k-i)%33;k+=23*28); cout<<"Case "<<++N<<": The next triple peak occurs in "<<k-d<<" days."<<endl; } return 0; }
运行结果如下。
3、POJ1013 Counterfeit Dollar(mooc中称硬币)
这题目不难，但是这道题我WA了很多次。其中我说下WA的原因：
1.每个盘子称的牌子不一定有4个。
2.如果某个假币可能轻可能重，不要continue，要以heavy----light的俩次形式输出。
思路：
定义一个大小为9字符串数组。作为每次输入的字符串。
依次假设每个硬币为假的。然后从重到轻挨个枚举，当找到假币的时候输出。
下面是AC代码：
#include <iostream> #include <string> #include <map> using namespace std; int main(){ int N; cin>>N; map<char,int> m; for(int i=65;i<77;i++) { m[(char)i]=0; } while(N--){ string str[9]; cin>>str[0]>>str[1]>>str[2]>>str[3]>>str[4]>>str[5]>>str[6]>>str[7]>>str[8]; for(int i=65;i<77;i++){ int sign = 0; int left = 0,right = 0; string res=""; m[(char)i]=1; for(int k=0;k<3;k++) { for (int j = 0; j < str[0+3*k].length(); j++)left += m[str[0+3*k][j]]; for (int j = 0; j < str[1+3*k].length(); j++)right += m[str[1+3*k][j]]; if (left == right) res = "even"; if (left > right) res = "up"; if (left < right) res = "down"; if (res == str[2+3*k])sign++; left=0; right=0; } if(sign==3)cout<<(char)i<<" is the counterfeit coin and it is heavy. "; sign=0; res=""; m[(char)i]=-1; for(int k=0;k<3;k++) { for (int j = 0; j < str[0+3*k].length(); j++)left += m[str[0+3*k][j]]; for (int j = 0; j < str[1+3*k].length(); j++)right += m[str[1+3*k][j]]; if (left == right) res = "even"; if (left > right) res = "up"; if (left < right) res = "down"; if (res == str[2+3*k])sign++; left=0; right=0; } if(sign==3) cout<<(char)i<<" is the counterfeit coin and it is light. "; m[(char)i]=0; } } return 0; }
4、EXTENDED LIGHTS OUT（POJ 1222）
这道题着实有点难。不过我们这次用枚举的方法解答这个问题。
分析：
输入一个5*6的矩阵，让我们从中选取一个按钮方案，使最终所有灯都熄灭。
思路：
0、目标使所有灯的状态变为0。
1、想不干扰第1行别的灯的状态来改变第1行，就需要按下面的按钮才能准确的改变。
2、别的行数也是以此类推。
3、这样别的行数的状态都会随着第一行的变化而确定。
AC代码如下：
#include <iostream> using namespace std; int Matrix[5][6]; int res[5][6]; int temp[5][6]; void Flip(int &a){ if(a) a=0; else a=1; } bool Check(){ for(int i=0;i<6;i++){ if(temp[4][i]) return false; } return true; } void print(int t){ cout<<"PUZZLE #"<<t<<endl; for(int i=0;i<5;i++){ for(int j=0;j<6;j++) { if(j==5)cout<<res[i][j]; else cout << res[i][j] << " "; } cout<<endl; } } int main(){ int N;cin>>N; for(int t=1;t<=N;t++){ for(int i=0;i<5;i++)for(int j=0;j<6;j++)cin>>Matrix[i][j];//输入矩阵 for(int a=0;a<2;a++)for(int b=0;b<2;b++)for(int c=0;c<2;c++)for(int d=0;d<2;d++)for(int e=0;e<2;e++)for(int f=0;f<2;f++){ int A[6] = {a,b,c,d,e,f}; for(int i=0;i<5;i++){ for(int j=0;j<6;j++) res[i][j]=0; } for(int i=0;i<5;i++) { for(int j=0;j<6;j++){ temp[i][j]=Matrix[i][j]; }//循环copy } for(int i=0;i<6;i++){//依照枚举数组将第一排按下 if(A[i]==1){ res[0][i]=1; switch (i){ case 0: Flip(temp[0][i]); Flip(temp[0][i+1]); Flip(temp[1][i]); break; case 5: Flip(temp[0][i]); Flip(temp[0][i-1]); Flip(temp[1][i]); break; default: Flip(temp[0][i]); Flip(temp[0][i-1]); Flip(temp[0][i+1]); Flip(temp[1][i]); break; } } } for(int i=0;i<3;i++){//其他数组依次往下按 for(int j=0;j<6;j++){ if(temp[i][j]==1){ res[i+1][j]=1; switch (j){ case 0: Flip(temp[i][j]); Flip(temp[i+1][j+1]); Flip(temp[i+1][j]); Flip(temp[i+2][j]); break; case 5: Flip(temp[i][j]); Flip(temp[i+1][j-1]); Flip(temp[i+1][j]); Flip(temp[i+2][j]); break; default: Flip(temp[i][j]); Flip(temp[i+1][j-1]); Flip(temp[i+1][j]); Flip(temp[i+1][j+1]); Flip(temp[i+2][j]); break; } } } } for(int i=0;i<6;i++){ if(temp[3][i]==1){ res[4][i]=1; switch (i){ case 0: Flip(temp[3][i]); Flip(temp[4][i+1]); Flip(temp[4][i]); break; case 5: Flip(temp[3][i]); Flip(temp[4][i-1]); Flip(temp[4][i]); break; default: Flip(temp[3][i]); Flip(temp[4][i-1]); Flip(temp[4][i+1]); Flip(temp[4][i]); break; } } } if(Check()){ print(t); } } } }
不过这题可以利用二进制枚举法进行简化。
什么是二进制枚举法呢？
我在枚举从000000~111111的时候，我嵌套了6层循环，如果使用二进制来表示这个数组，我只需要枚举从0到31即可。
下面就是mooc老师写的代码。
#include <memory> #include <string> #include <cstring> #include <iostream> using namespace std; int GetBit(char c,int i) { //取c的第i位 return ( c >> i ) & 1; } void SetBit(char & c,int i, int v) { //设置c的第i位为v if( v ) c |= ( 1 << i); else c &= ~( 1 << i); } void Flip(char & c, int i) { //将c的第i位为取反 c ^= ( 1 << i); } void OutputResult(int t,char result[]) //输出结果 { cout << "PUZZLE #" << t << endl; for( int i = 0;i < 5; ++i ) { for( int j = 0; j < 6; ++j ) { cout << GetBit(result[i],j); if( j < 5 ) cout << " "; } cout << endl; } } int main() { char oriLights[5]; //最初灯矩阵，一个比特表示一盏灯 char lights[5]; //不停变化的灯矩阵 char result[5]; //结果开关矩阵 char switchs; //某一行的开关状态 int T; cin >> T; for( int t = 1; t <= T; ++ t) { memset(oriLights,0,sizeof(oriLights)); for( int i = 0;i < 5; i ++ ) { //读入最初灯状态 for( int j = 0; j < 6; j ++ ) { int s; cin >> s; SetBit(oriLights[i],j,s); } } for( int n = 0; n < 64; ++n ) { //遍历首行开关的64种状态 memcpy(lights,oriLights,sizeof(oriLights)); switchs = n; //第i行的开关状态 for( int i = 0;i < 5; ++i ) { result[i] = switchs; //第i行的开关方案 for( int j = 0; j < 6; ++j ) { if( GetBit(switchs,j)) { if( j > 0) Flip(lights[i],j-1);//改左灯 Flip(lights[i],j);//改开关位置的灯 if( j < 5 ) Flip(lights[i],j+1);//改右灯 } } if( i < 4 ) lights[i+1] ^= switchs;//改下一行的灯 switchs = lights[i]; //第i+1行开关方案和第i行灯情况同 } if( lights[4] == 0 ) { OutputResult(t,result); break; } } // for( int n = 0; n < 64; n ++ ) } return 0; }
PS:这手二进制枚举秀到我了。