枚举

• 基于逐个尝试答案的一种问题求解策略

完美立方：

• 形如 a^3 = b^3 + c^3 + d^3 的等式称为完美立方式。编写一个程序，对任何给定的正整数N(N<=100)，寻找所有的四元组(a,b,c,d)使得a^3 = b^3 + c^3 + d^3，其中a,b,c,d大于1，小于等于N，且b<=c<=d.
• 输入：一个正整数N(N<=100)
• 输出：每行输出一个完美立方。输出格式为：
  Cube = a, Triple = (b,c,d)
  按照a的值从小到大依次输出。当a的值相同时，b值小的优先输出...
• 样例输入：
• 样例输出：
• 解题思路：四重循环枚举a,b,c,d。a在最外层，d在最里层。每一层都是从小到大枚举。
• a枚举范围：[2,N], b枚举范围：[2,a-1],c枚举范围：[b,a-1],d枚举范围：[c,a-1]

#include <iostream>
using namespace std;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
    int N;
    cin>>N;
    for(int a=2;a<=N;a++)
    {
        for(int b=2;b<a;b++)
        {
            for(int c=b;c<a;c++)
            {
                for(int d=c;d<a;d++)
                {
                    if(a*a*a==b*b*b+c*c*c+d*d*d)
                    {
                        cout<<"Cube = "<<a<<",";
                        cout<<"Triple = ("<<b<<","<<c<<","<<d<<")"<<endl;
                    }
                }
            }
        }
    }
    return 0;
}

生理周期：

• 问题描述：人有体力、智力和情商高峰的日子，它们分别每隔23，28，33天出现一次。给定三个高峰出现的日子p,e,i，再给定另一个指定的日子d,输出日子d后下一个三高峰出现的日子(用距离d的天数表示)。
• 解题思路：从d+1天开始，一直试到第21252天(232833=21252),对其中的每个日期K查看是否满足(k-p)%23==0 &&(k-e)%28==0 &&(k-i)%33==0
• 跳着试

#include <iostream>
using namespace std;
#define N 21252
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
    int p,e,i,d,caseNo=0;
    while(cin>>p>>e>>i>>d &&p!=-1)
    {
        ++caseNo;
        int k;
        for(k=d+1;(k-p)%23;++k);
        for(;(k-e)%28;k+=23);
        for(;(k-i)%33;k+=23*28);
        cout<<"Case "<<caseNo<<
        " :The next triple peek occurs in "<<k-d<<"days."<<endl;
        
    }
    return 0;
}

称硬币：

• 问题描述：有一打（12枚）硬币，其中有且仅有1枚假币，11枚真币，用A~L作为各个硬币的代号，假币可能比真币略轻，也可能略重，现在利用天枰，根据输入的3次称量，找出假币，并输出假币是轻还是重（数据保证一定能找出来）
• 输入：第一行为用例组数T，每组用例占三行每行表示一次称量结果，一次称量结果由三个字符串组成，前两个字符串等长表示放在天秤两边的硬币编号，第三个字符串表示称量结果，even表示平衡，up表示左端略高，down表示左边略低（以右侧为标准，up表示右侧高）
• 输出：对于每组用例，输出假币编号并判断其是轻还是重
• 解题思路：对于每一枚硬币，先假设它是假币且轻，如果符合，问题即解决。否则假设它是假币且重，看是否符合称量结果。把所有硬币都假设一遍，一定能找出假币。

#include <iostream>
#include <cstring>
char Left[3][7];//天平左侧硬币，一共有12个硬币，称量的时候一边放6个，三次称量，所以数组开[3][7].
char Right[3][7];//天平右侧硬币
char result[3][7];//三次称量结果
bool isFake(char c,bool light);//假设硬币c是假币，light==true时假设它为轻，light==false时假设为重，返回值为true表示假设成立
using namespace std;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
    int t;
    cin>>t;
    while(t--)
    {
        for(int i=0;i<3;++i)cin>>left[i]>>right[i]>>result[i];
        for(char c='A';c<='L';c++)//从'A'硬币到'L'硬币枚举
        {
            if(isFake(c,true))
            {
                cout<<c<<"is the counterfeit coin and it is light."<<endl;
                break;
            }
            if(isFake(c,false))
            {
                cout<<c<<"is the counterfeit coin and it is heavy."<<endl;
                break;
            }
            
        }
    }
    return 0;
}

//下面这个函数很重要，是本题的核心
bool isFake(char c,bool light)
{
    //light==true假设假币为轻，否则假设假币为重 
    for(int i=0;i<3;++i)
    {
        char* pleft;  //指向天平两边的字符串
        char* pright;
        if(light)   
        {
            pleft=Left[i];
            pright=Right[i];
        }
        else
        {
            pleft=Right[i];      //这么做是为了让下面的代码可重用
            pright=Left[i];
        }       
                //假设假币为轻
                switch(result[i][0])
        {
            case 'u':
                if(strchr(pright,c)==NULL)  //右侧up，右侧轻，轻假币在右侧。通过调用strchr判断char c是否在pright里
                    return false;
                break;
            case 'e':
                if(strchr(pright,c) || strchr(pright,c))  //两边相平，两侧都没有假币
                    return false;
                break;
            case 'd':
                if(strchr(pleft,c)==NULL)    //右侧下沉，轻假币在左侧
                    return false;
                break;
                
        } 
        
    }
    return true;
}

熄灯问题：

• 问题描述：有一个由按钮组成的矩阵，5行6列，每个按钮的位置上有一盏灯，当按下一个按钮时，该按钮以及周围位置（上下左右）灯的状态都会改变。给定矩阵中每盏灯的初始状态，求一种按钮方案，使得所有的灯都熄灭。
• 问题分析：第二次按下一个按钮时，将抵消第一次按下时产生的结果，所以一个按钮最多只需要按一次。
• 第一想法是通过枚举所有可能的按钮状态，对每个状态计算一下最后灯的情况，看是否都熄灭。但是30个开关有2的30次方种状态，程序会运超时。
• 枚举局部

#include <iostream>
#include <string>
#include <cstring>
#include <memory>
using namespace std;
char oriLights[5];//原始灯亮灭情况
char lights[5];// 运行时灯亮灭情况
char result[5];//存放按开关的情况
int getBit(char c,int i);
void setBit(char &c,int i,int v);
void flipBit(char& c,int i);
void printResult(int i,char result[]);
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
    int T;
    cin>>T;
    for(int t=1;t<=T;++t)
    {
        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)//枚举第一行按开关情况000000~111111 
        {
            int switchs=n;
            memcpy(lights,oriLights,sizeof(oriLights));
            for(int i=0;i<5;++i)
            {
                result[i]=switchs;
                for(int j=0;j<6;++j)//改变同行灯状态 
                {
                    if(getBit(switchs,j))
                    {
                        if(j>0)flipBit(lights[i],j-1);
                        flipBit(lights[i],j);
                        if(j<5)flipBit(lights[i],j+1);
                    }
                }
                lights[i+1]^=switchs;//改变下一列灯状态
                switchs=lights[i]; //下一行按开关取决于这一行灯的亮灭情况，如果本行某一列灯亮，就要在下一行按相同列的开关让它熄灭
            }
            if(lights[4]==0)
            {
                printResult(t,result);
                break;
            }
        }
    }
    return 0;
}

int getBit(char c,int i) 
{
    return (c>>i)&1;
}

void setBit(char &c,int i,int v)
{
    if(v)
    {
        c |= (1<<i);
    }
    else
    {
        c &= ~(1<<i);
    }
}

void flipBit(char& c,int i)
{
    c ^= (1<<i);
}

void printResult(int i,char result[]) 
{
    cout<<"PUZZLE #"<<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;
    }
}