学习视频链接：程序设计与算法（二）算法基础（北京大学）
第一周：枚举
枚举，就是将所有可能性都扫一遍，然后看那种可能符合要求，那就是我们要的答案
枚举一般也是暴力搜索，一般要很考虑时间复杂度，以免超时。
因此在使用枚举的方法的时候，要看是否会超时，若超时，则不能使用枚举方法。
有些题目的枚举，可以确定“局部”，从而尽可能的减少枚举的范围，避免超时的可能。
例题1：完美立方
具体的题目链接：
https://vjudge.net/problem/OpenJ_Bailian-2810
分析：
根据题意，我们可以知道，枚举a,b,c,d四个所有可能的值，然后利用 if 语句进行判断。
那么由于a,b,c,d都要从小到大输出，所以a在最外层，然后依次到b，c，d。
其中a的范围：[2，N]。b的范围：[2，a-1]。c的范围：[b,a-1]。d的范围：[c,a-1]
如果符合完美立方的条件，就按要求进行输出。
AC代码：
#include
int main()
{
int n;
scanf("%d",&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)
printf("Cube = %d, Triple = (%d,%d,%d)\n",a,b,c,d);
}
return 0;
}
例题2：生理周期
具体的题目链接：
https://vjudge.net/problem/OpenJ_Bailian-4148
分析：
利用枚举的方法。
方法1：
循环k，从d+1开始到21252+d（因为说距离，即k-d<=21252，所以k的范围是到21252+d）
条件就是：(k-p)%23==0 && (k-e)%28==0 && (k-i)%33==0，最后输出 k-d
方法2：
考虑减少枚举的范围，即我们可以先找到从k=d+1开始的时间，先满足第一个条件(k-p)%23==0
说明这样子找到符合的了，那么要满足下一个条件的k，为了使上一个条件一定是满足，那就k=k+23，这样子上一个条件一定满足，这时候就找到 (k-e)%28==0即可。
然后继续往下找k，为了满足上面的两个条件，我们 k = k+23*28，直到 (k-i)%33==0，那我们就找到对应的k值了。最后输出 k-d
AC代码：
#include
#include
using namespace std;
int main()
{
//freopen("in.txt","r",stdin);
int p,e,i,d;
int Case = 1;
int k;
while(cin >> p >> e >> i >> d && p!=-1)
{
// 求出的答案最大为21252，所以k的范围应该到21252+d
for(k = d+1;k <= 21252+d;k++) { if((k-p)%23==0 && (k-e)%28==0 && (k-i)%33==0) { printf("Case %d: the next triple peak occurs in %d days.\n",Case++,k-d); break; } } } return 0; } /* // 方法2，跳着找 int main() { //freopen("in.txt","r",stdin); int p,e,i,d; int Case = 1; while(cin >> p >> e >> i >> d && p!=-1)
{
int k;
for(k = d+1; (k-p)%23;k++);
for(; (k-e)%28; k+=23);
for(; (k-i)%33; k+=23*28);
printf("Case %d: the next triple peak occurs in %d days.\n",Case++,k-d);
}
return 0;
}
例题3：称硬币（Counterfeit Dollar）POJ1013
具体的题目链接：
https://vjudge.net/problem/POJ-1013
分析：
总共是有A-L的12枚硬币，11枚真1枚假（不知是轻了还是重了），根据题目给出的三次称的一个结果，我们要找出哪一枚是假币。
由于总共才12枚，而且两种情况，要么轻，要么重，所以枚举的话，也最多24种。
所以我们依次从A到L枚举，假设这次的这枚硬币是假的，同时两种情况：轻或者重。然后对三次称的结果进行判断，如果三中结果都符合，那就说明这种枚举的可能就是答案。
而且轻和重，如果把重的情况左右称反过来就是轻了，所以这个判断可以同时用一个自定义函数解决，就不能弄两个函数。只用在这个函数的输入参数中，用一个bool型，真表示轻，假表示重。
那么需要一些字符串数组的知识，判断一个字符数组中是否有一个我们要的字符，一般用strchr函数，strchr(char s[],char c)，如果在，返回值是下标；如果不在，返回值是NULL。
还要知道一个字符指针的使用，一个字符指针相当于可以指向一个字符数组。char *p p = s[]。
AC代码：
#include
#include
#include
using namespace std;
// 总共12，平分一边6，所以存的要大于6，所以为8
char Left[3][8];
char Right[3][8];
char Res[3][6];// 判断是不是假的
bool isFake(char c,bool light)
{
char *pLeft,*pRight;
// 要检查是否满足了输入的三种情况
for(int i = 0;i < 3;i++)
{
// 重和轻两种情况是相反的，所以只需要反着，然后一起同一个函数判断即可
if(light)
{
pLeft = Left[i];
pRight = Right[i];
}
else
{
pLeft = Right[i];
pRight = Left[i];
}// 检查up，down和even三种
switch(Res[i][0])
{
case 'e': // 平衡，说明是没有的，如果有，就是假
if(strchr(pLeft,c) || strchr(pRight,c))
return false;
break;
case 'u': // 右边up，说明轻的在右边，如果不在，说明是false
if(strchr(pRight,c)==NULL)
return false;
break;
case 'd': // 右边down，说明轻的在左边，如果不在，说明是false
if(strchr(pLeft,c)==NULL)
return false;
break;
}
}
return true;
}
int main()
{
//freopen("in1.txt","r",stdin);
int n;
scanf("%d",&n);
getchar();
while(n--)
{
for(int i = 0;i < 3;i++)
scanf("%s %s %s",Left[i],Right[i],Res[i]);
// 枚举，假设从A到L，轻或重，然后检查是否满足输入
// 如果满足，说明就是答案
// 其中，轻&重其实是刚好两边互换，所以可以只用一个函数判断即可
// strchr(*char,char)判断在字符串数组中，是否有这个字符
// 如果有，返回值为下标，如果没有，返回值是NULL
char c;
for(c = 'A';c <= 'L';c++)
{
if(isFake(c,true))
{
printf("%c is the counterfeit coin and it is light.\n",c);
break;
}
else if(isFake(c,false))
{
printf("%c is the counterfeit coin and it is heavy.\n",c);
break;
}
}
//printf("%s\n",Left[0]);
}
return 0;
}例题4：熄灯问题（EXTENDED LIGHTS OUT）POJ1222 具体的题目链接： https://vjudge.net/problem/POJ-1222题意说明： 大致就是给出一个目前的灯状态的一个5行6列数组（1表示灯亮，0表示灯灭），然后如果按下一个开关，除了这个开关本身位置的灯状态发生改变，该位置的上下左右四个位置的灯状态也要发生该表。这个时候我们要找出一组开关的按下和不按下的方案，从而使所有的灯都关闭。分析： 我们先要分清，一个开关，只有要么按下和不按下两种情况，如果按下2次，其实就是相当于不按，按3次相当于按1次，也就是同一个开关按下2次，相当于没改变，
然后灯的一个先后顺序其实也是没有关系的。
如果我们要枚举所有可能性，总共30个开关，一个开关两种状态，所以总共有2^30，会超时（一般1s的运行次数4*10^8）。
那么我们考虑，有没有一个“局部”，假如这个局部确定了，剩下的是不是就确定了。我们发现第一行其实就是这个“局部”，假如第一行的开关状态确定，也就是第一行的灯状态确定下来了，那么第二行的一个开关状态，肯定要使第一行的灯状态全变为0，所以此时下一行的开关状态是由上一行的灯状态决定的。
因此我们只用枚举第一行的开关状态——从而可以确定第一行的灯状态。这样子的枚举可能性2^6（即从000000到111111，也就是0到2^6-1=63），不会超时。
那么剩下的就是实现了，还有一个知识点，那就是因为一行一行，一行6位，而我们知道一个char可以存8bit的二进制，刚好状态都是0和1，所以我们可以使用位运算，也就是一个char就是一行，那么有5行，那就char s[5]就可以把五行的灯状态，开关状态分别存下来了。
所以要对位运算有了解：^（异或，相同为0，不同为1），&（与，全1为1，有0则0），|（或，有1则1，全0为0），！（非，！0=1，！1=0）。
具体的我在代码里都有详细讲解，就可以参考代码进行学习。
AC代码：
#include
#include
#include
#include
using namespace std;
char result[5];
char oriLight[5];
char Light[5];// &c 表示在调用函数里改变c，也会改变其实参，没有&就不会改变实参
void setBit(char &c,int i,int state)
{
// 是1的话，比如 0010 要加入0100，应该为0110，那么就是有1就为1，所以就是|
// 是0的话，比如 0010 要加入0000，应该为0010，那我们就不用动 c
if(state)
{
c |= (1<<i);
}
return;
}
int getBit(char c,int i)
{
// (1<<i)&c，不能这样，不然比如0010&0010=0010,输出就会变为2了 // 尽量还是要么1，要么0，所以把c>>i后&1，就可以了
return (c>>i)&1;
}
void changeBit(char &c,int i)
{
c ^= (1<<i);
}
// 数组的形参是不能有大小的，所以往往需要形参多一个int siz
// 只是这里我们知道了，所以不多此一举
void dispAns(char res[],int t)
{
printf("PUZZLE #%d\n",t);
for(int i = 0;i < 5;i++)
{
for(int j = 0;j < 6;j++)
{
printf("%d",getBit(res[i],j));
if(j < 5) printf(" "); } printf("\n"); } } int main() { //freopen("2in.txt","r",stdin); //freopen("2out.txt","w",stdout); int n; cin >> n;
for(int Case = 1;Case <= n;Case++)
{
memset(oriLight,0,sizeof(oriLight));
int input;
for(int i = 0;i < 5;i++)
{
for(int j = 0;j < 6;j++) { cin >> input;
setBit(oriLight[i],j,input);
}
}
int switchs;
for(int t = 0;t <= 64-1;t++)
{
switchs = t;
memcpy(Light,oriLight,sizeof(oriLight)); // 把一个数组的内容复制给另一个数组
for(int i = 0;i < 5;i++)
{
result[i] = switchs; // 把每次的开关状态存下，为了最后输出
for(int j = 0;j < 6;j++) { // 获取这一行的开关状态对应的第j个位置，如果是1才用改变状态 if(getBit(switchs,j)) { // 改变的时候，除了本身j，还有j-1，j+1 // 又要注意，只有j>0，才有j-1，只有j<5才有j+1 if(j>0)
changeBit(Light[i],j-1);
if(j<5)
changeBit(Light[i],j+1);
changeBit(Light[i],j);
}
}
// 因为上一行改变影响了下一行，所以上一行的开关状态影响了下一行灯状态
// 发现了，如上一行开关为 0101，下一行本来是 0110，现在就会变成 0011
// 发现了，相同为0，不同为1，刚好是异或
if(i < 4)
Light[i+1] ^= switchs;
// 下一次的开关状态是由上一行的灯状态来决定
switchs = Light[i];
}
// 判断是否结束枚举，就是最后一行的是不是全为0了
if(Light[4]==0)
{
// 输出答案 ，要用一个来记录每一行的开关状态
dispAns(result,Case);
break;
}
}
}
return 0;
}