Party Lamps
Description
To brighten up the gala dinner of the IOI’98 we have a set of N coloured lamps numbered from
1 to N. The lamps are connected to four buttons:
button 1 — when this button is pressed, all the lamps change their state: those that are ON are turned OFF and those that are OFF are turned ON.
button 2 — changes the state of all the odd numbered lamps.
button 3 — changes the state of all the even numbered lamps.
button 4 — changes the state of the lamps whose number is of the form 3K+1 (with K >= 0), i.e., 1,4,7,…
There is a counter C which records the total number of button presses.
When the party starts, all the lamps are ON and the counter C is set to zero.
You are given the value of counter C and information on the final state of some of the lamps. Write a program to determine all the possible final configurations of the N lamps that are consistent with the given information, without repetitions.
Input
Your program is to read from standard input. The input contains four lines, describing the number N of lamps available, the number C of button presses, and the state of some of the lamps in the final configuration.
The first line contains the number N and the second line the final value of counter C. The third line lists the lamp numbers you are informed to be ON in the final configuration, separated by one space and terminated by the integer -1. The fourth line lists the lamp numbers you are informed to be OFF in the final configuration, separated by one space and terminated by the integer -1.
The parameters N and C are constrained by:
10 <= N <= 100
1 <= C <= 10000
The number of lamps you are informed to be ON, in the final configuration, is less than or equal to 2.The number of lamps you are informed to be OFF, in the final configuration, is less than or equal to 2.
Output
Your program is to write to standard output. The output must contain all the possible final configurations (without repetitions) of all the lamps. There is at least one possible final configuration. Each possible configuration must be written on a different line. Each line has N characters, where the first character represents the state of lamp 1 and the last character represents the state of lamp N. A 0 (zero) stands for a lamp that is OFF, and a 1 (one) stands for a lamp that is ON. Configurations should be listed in binary ascending order.
Sample Input
10 1 -1 7 -1
Sample Output
0000000000 0101010101 0110110110
我的代码
每一个按钮其实只有按下去和不按下去两种情况，因为按n(n>=2)次等价于按n-2次。因此四个按钮总共也就16种可能。那么搜索这16中可能时，有两个限界条件：1.是否符合给出的必须明或暗的灯的条件；2.按钮数是否符合c。
先根据条件2判断当前按钮组合是否与c冲突，主要是两个方面：1.按钮按下的总数是否超过c；2.是否与c同奇偶。关于为什么要同奇偶，是因为连续按下两次等于没按，可以通过多按两次某个按钮来补足总次数以达到c，因此如果奇偶性不同就显然没办法使得总次数等于c。
再根据条件1来判断，只要看特定的灯是否是明或者暗即可。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct answer
{
char number[101];
}ans[16];
int n,c,ans_num=0;//ans_num是答案的条数
int lamps[102];//lamps[]是记录所有灯的明暗状态
int on[101]={0};//记录哪些灯必须亮
int off[101]={0};//记录哪些灯必须暗
bool cmp(answer a,answer b)
{
if (strcmp(a.number,b.number )==-1) return 1;
else return 0;
}
void press(int all,int odd,int even,int k3)
//按下当前选择的按钮的生成灯的情况
{
if (all)
{
for (int i=1;i<=n;i++)
{
lamps[i]=(lamps[i]+1)%2;
}
}
if (odd)
{
for (int i=1;i<=n;i++)
{
if (i&1)
{
lamps[i]=(lamps[i]+1)%2;
}
}
}
if (even)
{
for (int i=1;i<=n;i++)
{
if (!(i&1))
{
lamps[i]=(lamps[i]+1)%2;
}
}
}
if (k3)
{
for (int i=1;i<=n;i++)
{
if (!((i-1)%3))
{
lamps[i]=(lamps[i]+1)%2;
}
}
}
}
int judge()
//判断是否符合要求的明暗情况
{
for (int i=1;i<n;i++)
{
if (on[i])
{
if (!lamps[i]) return 0;
}
if (off[i])
{
if (lamps[i]) return 0;
}
}
return 1;
}
int main()
{
scanf("%d%d",&n,&c);
int a;
scanf("%d",&a);
while (a!=-1)
{
on[a]=1;
scanf("%d",&a);
}
scanf("%d",&a);
while (a!=-1)
{
off[a]=1;
scanf("%d",&a);
}
//遍历四个按钮
for (int i=0;i<2;i++)
{
for (int j=0;j<2;j++)
{
for (int k=0;k<2;k++)
{
for (int m=0;m<2;m++)
{
if ((i+j+k+m)%2==c%2&&(i+j+k+m)<=c)
//如果按钮选择数小于c且与c同奇偶，按下按钮并判断情况
{
for (int t=1;t<=n;t++)
{
lamps[t]=1;
}
press(i,j,k,m);
if (judge())
{
for (int t=0;t<n;t++)
{
ans[ans_num].number[t]=(char)(lamps[t+1]+'0');
}
ans[ans_num].number[n]='#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct answer
{
char number[101];
}ans[16];
int n,c,ans_num=0;//ans_num是答案的条数
int lamps[102];//lamps[]是记录所有灯的明暗状态
int on[101]={0};//记录哪些灯必须亮
int off[101]={0};//记录哪些灯必须暗
bool cmp(answer a,answer b)
{
if (strcmp(a.number,b.number )==-1) return 1;
else return 0;
}
void press(int all,int odd,int even,int k3)
//按下当前选择的按钮的生成灯的情况
{
if (all)
{
for (int i=1;i<=n;i++)
{
lamps[i]=(lamps[i]+1)%2;
}
}
if (odd)
{
for (int i=1;i<=n;i++)
{
if (i&1)
{
lamps[i]=(lamps[i]+1)%2;
}
}
}
if (even)
{
for (int i=1;i<=n;i++)
{
if (!(i&1))
{
lamps[i]=(lamps[i]+1)%2;
}
}
}
if (k3)
{
for (int i=1;i<=n;i++)
{
if (!((i-1)%3))
{
lamps[i]=(lamps[i]+1)%2;
}
}
}
}
int judge()
//判断是否符合要求的明暗情况
{
for (int i=1;i<n;i++)
{
if (on[i])
{
if (!lamps[i]) return 0;
}
if (off[i])
{
if (lamps[i]) return 0;
}
}
return 1;
}
int main()
{
scanf("%d%d",&n,&c);
int a;
scanf("%d",&a);
while (a!=-1)
{
on[a]=1;
scanf("%d",&a);
}
scanf("%d",&a);
while (a!=-1)
{
off[a]=1;
scanf("%d",&a);
}
//遍历四个按钮
for (int i=0;i<2;i++)
{
for (int j=0;j<2;j++)
{
for (int k=0;k<2;k++)
{
for (int m=0;m<2;m++)
{
if ((i+j+k+m)%2==c%2&&(i+j+k+m)<=c)
//如果按钮选择数小于c且与c同奇偶，按下按钮并判断情况
{
for (int t=1;t<=n;t++)
{
lamps[t]=1;
}
press(i,j,k,m);
if (judge())
{
for (int t=0;t<n;t++)
{
ans[ans_num].number[t]=(char)(lamps[t+1]+'0');
}
ans[ans_num].number[n]='\0';
ans_num++;
}
}
}
}
}
}
sort(ans,ans+ans_num,cmp);
for (int i=0;i<ans_num;i++)
{
printf("%s\n",ans[i].number);
}
return 0;
}
';
ans_num++;
}
}
}
}
}
}
sort(ans,ans+ans_num,cmp);
for (int i=0;i<ans_num;i++)
{
printf("%s\n",ans[i].number);
}
return 0;
}规律循环
总觉得自己在写搜索题时，搜索的对象太复杂。简单的题目还能应付，题目难起来就处理不了了。上网查询了这道题其它人的做法，都是利用规律循环，也就是找规律，根据所得的规律来产生搜索的对象。
通过观察可以发现，这些灯一共可以分成4种，同种灯无论在何种操作下，状态都是相同的。即：（1）编号为1,7,13,19….的灯。（2）编号为4,10,16,22….的灯。（3）编号为奇数，但是不属于（1）的灯。 （4）编号为偶数，但是不属于（2）的灯。
对于第（1）种灯，唯1,2,4号开关能够控制，且这些开关的作用是等效的。
对于第（2）种灯，唯有1,3,4号开关能够控制，且这些开关的作用是等效的。
对于第（3）种灯，唯有1,2号开关能够控制，且这些开关的作用是等效的。
对于第（4）种灯，唯有第1,3号开关能够控制，且这些开关的作用是等效的。
同一个开关无论按动多少次，其效果只有两种。即所有奇数次的按动的效果与按动一次相同；所有偶数次的按动与不按动的效果也相同。
也就是说，题目给出的一些必须是明的或者暗的灯，可以根据他们的类别来确定一些按钮的组合的总数。例如有某个必须是亮着的灯是第一类的，那么1、2、4个按钮的总操作次数必须是偶数次，即相当于没有按下那个灯。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct answer
{
char number[101];
}ans[16];
int n,c,ans_num=0;
int lamps[102];
int on[4]={0};//记录必须亮的灯的种类
int off[4]={0};//记录必须灭的灯的种类
bool cmp(answer a,answer b)
{
if (strcmp(a.number,b.number )==-1) return 1;
else return 0;
}
//判断一个灯的类别
int JudgeClass(int x)
{
if ((x&1)&&((x-1)%3)==0) return 0;
else if (!(x&1)&&((x-1)%3)==0) return 1;
else if (x&1) return 2;
else return 3;
}
//产生一个结果，并加入结果结构体
void press(int all,int odd,int even,int k3)
{
for (int t=1;t<=n;t++)
{
lamps[t]=1;
}
if (all)
{
for (int i=1;i<=n;i++)
{
lamps[i]=(lamps[i]+1)%2;
}
}
if (odd)
{
for (int i=1;i<=n;i++)
{
if (i&1)
{
lamps[i]=(lamps[i]+1)%2;
}
}
}
if (even)
{
for (int i=1;i<=n;i++)
{
if (!(i&1))
{
lamps[i]=(lamps[i]+1)%2;
}
}
}
if (k3)
{
for (int i=1;i<=n;i++)
{
if (!((i-1)%3))
{
lamps[i]=(lamps[i]+1)%2;
}
}
}
for (int t=0;t<n;t++)
{
ans[ans_num].number[t]=(char)(lamps[t+1]+'0');
}
ans[ans_num].number[n]='#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct answer
{
char number[101];
}ans[16];
int n,c,ans_num=0;
int lamps[102];
int on[4]={0};//记录必须亮的灯的种类
int off[4]={0};//记录必须灭的灯的种类
bool cmp(answer a,answer b)
{
if (strcmp(a.number,b.number )==-1) return 1;
else return 0;
}
//判断一个灯的类别
int JudgeClass(int x)
{
if ((x&1)&&((x-1)%3)==0) return 0;
else if (!(x&1)&&((x-1)%3)==0) return 1;
else if (x&1) return 2;
else return 3;
}
//产生一个结果，并加入结果结构体
void press(int all,int odd,int even,int k3)
{
for (int t=1;t<=n;t++)
{
lamps[t]=1;
}
if (all)
{
for (int i=1;i<=n;i++)
{
lamps[i]=(lamps[i]+1)%2;
}
}
if (odd)
{
for (int i=1;i<=n;i++)
{
if (i&1)
{
lamps[i]=(lamps[i]+1)%2;
}
}
}
if (even)
{
for (int i=1;i<=n;i++)
{
if (!(i&1))
{
lamps[i]=(lamps[i]+1)%2;
}
}
}
if (k3)
{
for (int i=1;i<=n;i++)
{
if (!((i-1)%3))
{
lamps[i]=(lamps[i]+1)%2;
}
}
}
for (int t=0;t<n;t++)
{
ans[ans_num].number[t]=(char)(lamps[t+1]+'0');
}
ans[ans_num].number[n]='\0';
ans_num++;
}
int main()
{
scanf("%d%d",&n,&c);
int a;
scanf("%d",&a);
while (a!=-1)
{
on[JudgeClass(a)]=1;
scanf("%d",&a);
}
scanf("%d",&a);
while (a!=-1)
{
off[JudgeClass(a)]=1;
scanf("%d",&a);
}
for (int i=0;i<2;i++)
{
for (int j=0;j<2;j++)
{
for (int k=0;k<2;k++)
{
for (int m=0;m<2;m++)
{
if ((i+j+k+m)%2==c%2&&(i+j+k+m)<=c)
{
//以下就是根据灯的种类来判断按钮操作数是否合法
if ((i+j+m)%2)
{
if (on[0]) continue;
}
else
{
if (off[0]) continue;
}
if ((i+k+m)%2)
{
if (on[1]) continue;
}
else
{
if (off[1]) continue;
}
if ((i+j)%2)
{
if (on[2]) continue;
}
else
{
if (off[2]) continue;
}
if ((i+k)%2)
{
if (on[3]) continue;
}
else
{
if (off[3]) continue;
}
press(i,j,k,m);
}
}
}
}
}
sort(ans,ans+ans_num,cmp);
for (int i=0;i<ans_num;i++)
{
printf("%s\n",ans[i].number);
}
return 0;
}
';
ans_num++;
}
int main()
{
scanf("%d%d",&n,&c);
int a;
scanf("%d",&a);
while (a!=-1)
{
on[JudgeClass(a)]=1;
scanf("%d",&a);
}
scanf("%d",&a);
while (a!=-1)
{
off[JudgeClass(a)]=1;
scanf("%d",&a);
}
for (int i=0;i<2;i++)
{
for (int j=0;j<2;j++)
{
for (int k=0;k<2;k++)
{
for (int m=0;m<2;m++)
{
if ((i+j+k+m)%2==c%2&&(i+j+k+m)<=c)
{
//以下就是根据灯的种类来判断按钮操作数是否合法
if ((i+j+m)%2)
{
if (on[0]) continue;
}
else
{
if (off[0]) continue;
}
if ((i+k+m)%2)
{
if (on[1]) continue;
}
else
{
if (off[1]) continue;
}
if ((i+j)%2)
{
if (on[2]) continue;
}
else
{
if (off[2]) continue;
}
if ((i+k)%2)
{
if (on[3]) continue;
}
else
{
if (off[3]) continue;
}
press(i,j,k,m);
}
}
}
}
}
sort(ans,ans+ans_num,cmp);
for (int i=0;i<ans_num;i++)
{
printf("%s\n",ans[i].number);
}
return 0;
}反思
尽管这两个思路的效率看上去不是差很多，但是搜索题必须谨慎地选择搜索对象，这需要在前期做好准备工作，对题目进行合理的分解与重构。