在算法竞赛中，很多问题是来不及用数学公式推导出来的。或者说根本就找不到数学规律，这时我们就需要使用枚举来暴力破解。

不过枚举也是需要脑子的，一味的暴力只能超时。因此我这里选择了几道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=;a<=N;a++){

        for(int d=;d<=a;d++){

            for(int c=;c<=d;c++){

                for(int b=;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 ;

}

运行结果如下：

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=;

    while(cin >> p >> e >> i >> d&&p!=-) {

        int k;

        for(k=d+;(k-p)%||(k-e)%||(k-i)%;k++);

        cout<<"Case "<<++N<<": The next triple peak occurs in "<<k-d<<" days."<<endl;

    }

    return ;

}
不过在此我们是否会有个疑问。一个一个的尝试是否过于浪费时间了？
这里我们给出另一种思路。
我们先枚举出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=;

    while(cin >> p >> e >> i >> d&&p!=-) {

        int k;

        for(k=d+;(k-p)%;k++);//c++中正数就是true

       for(;(k-e)%;k+=);

        for(;(k-i)%;k+=*);

        cout<<"Case "<<++N<<": The next triple peak occurs in "<<k-d<<" days."<<endl;

    }

    return ;

}

运行结果如下。

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=;i<;i++) {

        m[(char)i]=;

    }

    while(N--){

        string str[];

        cin>>str[]>>str[]>>str[]>>str[]>>str[]>>str[]>>str[]>>str[]>>str[];

        for(int i=;i<;i++){

            int sign = ;

            int left = ,right = ;

            string res="";

            m[(char)i]=;

            for(int k=;k<;k++) {

                for (int j = ; j < str[+*k].length(); j++)left += m[str[+*k][j]];

                for (int j = ; j < str[+*k].length(); j++)right += m[str[+*k][j]];

                if (left == right) res = "even";

                if (left > right) res = "up";

                if (left < right) res = "down";

                if (res == str[+*k])sign++;

                left=;

                right=;

            }

            if(sign==)cout<<(char)i<<" is the counterfeit coin and it is heavy.\n";

            sign=;

            res="";

            m[(char)i]=-;

            for(int k=;k<;k++) {

                for (int j = ; j < str[+*k].length(); j++)left += m[str[+*k][j]];

                for (int j = ; j < str[+*k].length(); j++)right += m[str[+*k][j]];

                if (left == right) res = "even";

                if (left > right) res = "up";

                if (left < right) res = "down";

                if (res == str[+*k])sign++;

                left=;

                right=;

            }

            if(sign==) cout<<(char)i<<" is the counterfeit coin and it is light.\n";

            m[(char)i]=;

        }

    }

    return ;

}

4、EXTENDED LIGHTS OUT（POJ 1222）

题目链接

这道题着实有点难。不过我们这次用枚举的方法解答这个问题。

分析：

输入一个5*6的矩阵，让我们从中选取一个按钮方案，使最终所有灯都熄灭。

思路：

0、目标使所有灯的状态变为0。

1、想不干扰第1行别的灯的状态来改变第1行，就需要按下面的按钮才能准确的改变。

2、别的行数也是以此类推。

3、这样别的行数的状态都会随着第一行的变化而确定。

AC代码如下：

#include <iostream>

using namespace std;

int Matrix[][];

int res[][];

int temp[][];

void Flip(int &a){

    if(a) a=;

    else a=;

}

bool Check(){

    for(int i=;i<;i++){

        if(temp[][i]) return false;

    }

    return true;

}

void print(int t){

    cout<<"PUZZLE #"<<t<<endl;

    for(int i=;i<;i++){

        for(int j=;j<;j++) {

            if(j==)cout<<res[i][j];

            else cout << res[i][j] << " ";

        }

        cout<<endl;

    }

}

int main(){

    int N;cin>>N;

    for(int t=;t<=N;t++){

        for(int i=;i<;i++)for(int j=;j<;j++)cin>>Matrix[i][j];//输入矩阵

        for(int a=;a<;a++)for(int b=;b<;b++)for(int c=;c<;c++)for(int d=;d<;d++)for(int e=;e<;e++)for(int f=;f<;f++){

            int A[] = {a,b,c,d,e,f};

             for(int i=;i<;i++){

               for(int j=;j<;j++) res[i][j]=;

             }

            for(int i=;i<;i++) {

                for(int j=;j<;j++){

                    temp[i][j]=Matrix[i][j];

                }//循环copy

            }

            for(int i=;i<;i++){//依照枚举数组将第一排按下

                if(A[i]==){

                    res[][i]=;

                    switch (i){

                        case :

                            Flip(temp[][i]);

                            Flip(temp[][i+]);

                            Flip(temp[][i]);

                            break;

                        case :

                            Flip(temp[][i]);

                            Flip(temp[][i-]);

                            Flip(temp[][i]);

                            break;

                        default:

                            Flip(temp[][i]);

                            Flip(temp[][i-]);

                            Flip(temp[][i+]);

                            Flip(temp[][i]);

                            break;

                    }

                }

            }

            for(int i=;i<;i++){//其他数组依次往下按

                for(int j=;j<;j++){

                    if(temp[i][j]==){

                        res[i+][j]=;

                        switch (j){

                            case :

                                Flip(temp[i][j]);

                                Flip(temp[i+][j+]);

                                Flip(temp[i+][j]);

                                Flip(temp[i+][j]);

                                break;

                            case :

                                Flip(temp[i][j]);

                                Flip(temp[i+][j-]);

                                Flip(temp[i+][j]);

                                Flip(temp[i+][j]);

                                break;

                            default:

                                Flip(temp[i][j]);

                                Flip(temp[i+][j-]);

                                Flip(temp[i+][j]);

                                Flip(temp[i+][j+]);

                                Flip(temp[i+][j]);

                                break;

                        }

                    }

                }

            }

            for(int i=;i<;i++){

                if(temp[][i]==){

                    res[][i]=;

                    switch (i){

                        case :

                            Flip(temp[][i]);

                            Flip(temp[][i+]);

                            Flip(temp[][i]);

                            break;

                        case :

                            Flip(temp[][i]);

                            Flip(temp[][i-]);

                            Flip(temp[][i]);

                            break;

                        default:

                            Flip(temp[][i]);

                            Flip(temp[][i-]);

                            Flip(temp[][i+]);

                            Flip(temp[][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 ) & ;

}

void SetBit(char & c,int i, int v) {

//设置c的第i位为v

    if( v )

        c |= (  << i);

    else

        c &= ~(  << i);

}

void Flip(char & c, int i) {

//将c的第i位为取反

    c ^= (  << i);

}

void OutputResult(int t,char result[]) //输出结果

{

    cout << "PUZZLE #" << t << endl;

    for( int i = ;i < ; ++i ) {

        for( int j = ; j < ; ++j ) {

            cout << GetBit(result[i],j);

            if( j <  )

                cout << " ";

        }

        cout << endl;

    }

}

int main() {

    char oriLights[]; //最初灯矩阵，一个比特表示一盏灯

    char lights[]; //不停变化的灯矩阵

    char result[]; //结果开关矩阵

    char switchs; //某一行的开关状态

    int T;

    cin >> T;

    for( int t = ; t <= T; ++ t) {

        memset(oriLights,,sizeof(oriLights));

        for( int i = ;i < ; i ++ ) { //读入最初灯状态

            for( int j = ; j < ; j ++ ) {

                int s;

                cin >> s;

                SetBit(oriLights[i],j,s);

            }

        }

        for( int n = ; n < ; ++n ) { //遍历首行开关的64种状态

            memcpy(lights,oriLights,sizeof(oriLights));

            switchs = n; //第i行的开关状态

            for( int i = ;i < ; ++i ) {

                result[i] = switchs; //第i行的开关方案

                for( int j = ; j < ; ++j ) {

                    if( GetBit(switchs,j)) {

                        if( j > )

                            Flip(lights[i],j-);//改左灯

                        Flip(lights[i],j);//改开关位置的灯

                        if( j <  )

                            Flip(lights[i],j+);//改右灯

                    }

                }

                if( i <  )

                    lights[i+] ^= switchs;//改下一行的灯

                switchs = lights[i]; //第i+1行开关方案和第i行灯情况同

            }

            if( lights[] ==  ) {

                OutputResult(t,result);

                break;

            }

        } // for( int n = 0; n < 64; n ++ )

    }

    return ;

}

PS:这手二进制枚举秀到我了。

总结：暴力破解也不是很轻松。需要使用者对破解边界有足够的熟练度才行。

最新文章

  1. centos7 打开mysql 3306端口并 设置外部访问
  2. linux线程的实现
  3. codeforces 451D Count Good Substrings
  4. Neo4j 高可用集群安装
  5. Hibernate控制insert\update语句
  6. java.lang.StackOverflowError: stack size 8MB
  7. RMI、RPC、SOAP通讯技术介绍及比对 - XML/SOAP
  8. sql中truncate 、delete与drop区别
  9. 传感器 Sensor 加速度【示例】
  10. spring-data-mongodb查询结果返回指定字段
  11. 「CSS3 」3D效果 &amp; 透视
  12. java关键字中文对比
  13. （一）SpringBoot基础篇- 介绍及HelloWorld初体验
  14. AI应用开发实战 - 定制化视觉服务的使用
  15. 深度解密HTTP通信细节
  16. 【转】深入分析 Parquet 列式存储格式
  17. Oracle 获取前几行数据问题的陷阱
  18. 编译UNITY的MONO模块记录
  19. ubuntu 服务器配置
  20. @RequestBody 处理类型 和 对象 和 json 相互转换

热门文章

  1. python文件打包为exe可执行文件的方法
  2. CentOS 7.X 中systemctl命令用法详解
  3. zookeeper安装、配置、使用
  4. BZOJ 5441: [Ceoi2018]Cloud computing
  5. HDU 5514 Frogs 欧拉函数
  6. day05 模块以及内置常用模块用法
  7. [每日App一]QQ主题要逆天！轻轻松松月入30万！
  8. 【bzoj3307】雨天的尾巴 权值线段树合并
  9. [NOIP2009] 最优贸易 (最短路,分层图)
  10. 关于vue属性绑定的问题