2.2.4 Party Lamps 派对灯
时间： 1ms 内存：64M
描述：
在IOI98的节日宴会上，我们有N(10<=N<=100)盏彩色灯，他们分别从1到N被标上号码。 这些灯都连接到四个按钮： 按钮1：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。 按钮2：当按下此按钮，将改变所有奇数号的灯。 按钮3：当按下此按钮，将改变所有偶数号的灯。 按钮4：当按下此按钮，将改变所有序号是3*K+1(K>=0)的灯。例如：1,4,7...
一个计数器C记录按钮被按下的次数。
当宴会开始，所有的灯都亮着，此时计数器C为0。
你将得到计数器C(0<=C<=10000)上的数值和经过若干操作后所有灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态，并且没有重复。
输入：
不会有灯会在输入中出现两次。
第一行: N。
第二行: C最后显示的数值。
第三行: 最后亮着的灯,用一个空格分开，以-1为结束。
第四行: 最后关着的灯,用一个空格分开，以-1为结束。
输出：
每一行是所有灯可能的最后状态(没有重复)。每一行有N个字符，第1个字符表示1号灯，最后一个字符表示N号灯。0表示关闭，1表示亮着。这些行必须从小到大排列（看作是二进制数）。
如果没有可能的状态，则输出一行'IMPOSSIBLE'。
示例输入：
10
1
-1
7 -1
/*在这个样例中，有10盏灯，只有1个按钮被按下。最后7号灯是关着的。*/
示例输出：
0000000000
0101010101
0110110110
/*在这个样例中，有三种可能的状态：
所有灯都关着
1,4,7,10号灯关着，2,3,5,6,8,9亮着。
1,3,5,7,9号灯关着，2, 4, 6, 8, 10亮着。*/提示：
参考答案（内存最优[1268]）：
#include <iostream>
using namespace std;
#define N 101
int n,c;
int light[9][7]={
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
0,0,0,1,1,1,0,
0,0,1,0,1,0,1,
0,0,1,1,0,1,1,
0,1,0,0,1,0,0,
0,1,0,1,0,1,0,
0,1,1,0,0,0,1,
0,1,1,1,1,1,1,
};//常量表
int minnum[9]={0,1,2,1,1,2,1,2,0};//对应常量表8个状态最少摁的次数
int dat[N];
bool flag1,flag2;
int main()
{
int i,j,tmp;
cin>>n>>c;
for(i=1;i<=n;i++)
dat[i]=-1;
while(cin>>tmp&&tmp!=-1)
dat[tmp]=1;
while(cin>>tmp&&tmp!=-1)
dat[tmp]=0;
flag1=false;
for(i=1;i<9;i++)
{
flag2=true;
for(j=1;j<=n;j++)
{
if(dat[j]==-1)//如果没有确定是亮或灭
continue;
tmp=j%6;//六位循环
if(tmp==0)//如果是6的倍数
tmp=6;
if(dat[j]!=light[i][tmp])//有个灯不同说明不是这个状态，结束判断
{
flag2=false;
break;
}
}
if(flag2==true&&c>=minnum[i])
{
flag1=true;//有一个满足条件就标记
for(j=1;j<=n;j++)
{
tmp=j%6;
if(tmp==0)
tmp=6;
cout<<light[i][tmp];
}
cout<<endl;
}
}
if(flag1==false)
cout<<"IMPOSSIBLE"<<endl;
return 0;
}参考答案（时间最优[4]）：
/*
ID: zhuihun1
PROG: lamps
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define MAXSIZE 105
using namespace std;
ofstream fout ("lamps.out");
ifstream fin ("lamps.in");
int n,c,pwo_n=0,powon[MAXSIZE],pwf_n=0,powoff[MAXSIZE],re_n=0;
int visited[MAXSIZE],light[MAXSIZE];
bool state[MAXSIZE];
string res[10000];
void change(int x)
{
int i;
switch(x)
{
case 0:
for(i=0;i<n;i++)
{
if(state[i]==1) state[i]=0;
else state[i]=1;
}
break;
case 1:
for(i=0;i<n;i++)
{
if((i+1)%2==1)
{
if(state[i]==1) state[i]=0;
else state[i]=1;
}
}
break;
case 2:
for(i=0;i<n;i++)
{
if((i+1)%2==0)
{
if(state[i]==1) state[i]=0;
else state[i]=1;
}
}break;
case 3:
for(i=0;i<n;i++)
{
if(i%3==0)
{
if(state[i]==1) state[i]=0;
else state[i]=1;
}
}break;
}
}
bool manzu()
{
memset(state,1,sizeof(state));
for(int i=0;i<c;i++)
change(light[i]);
for(int i=0;i<pwo_n;i++)
if(state[powon[i]-1]!=1)
return false;
for(int i=0;i<pwf_n;i++)
if(state[powoff[i]-1]!=0)
return false;
return true;
}
bool cunzai(string str)
{
for(int i=0;i<re_n;i++)
if(res[i]==str)
return false;
return true;
}
void zuhe(int x)
{
if(x==c)
{
if(!manzu())
return;
string tmp="";char c;
for(int i=0;i<n;i++)
{
c=state[i]+'0';
tmp+=c;
}
if(cunzai(tmp))
res[re_n++]=tmp;
return;
}
for(int i=0;i<4;i++)
{
if(i>=light[x-1])
{
light[x]=i;
zuhe(x+1);
}
}
}
int main()
{
memset(visited,0,sizeof(visited));
memset(light,-1,sizeof(light));
cin>>n>>c;
if(c>4)
c=4-c%2;
int t;
while(cin>>t&&t!=-1)
powon[pwo_n++]=t;
while(cin>>t&&t!=-1)
powoff[pwf_n++]=t;
zuhe(0);
sort(res,res+re_n);
if(re_n==0)
cout<<"IMPOSSIBLE";
else
for(int i=0;i<re_n;i++)
cout<<res[i]<<endl;
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。