题解 P1468 【派对灯 Party Lamps】
其实这道题掌握了规律就很简单。
规律如下：
规律一：对于任意c，总能转化为c≤2时的某种状态。
首先，给出公理。
公理1：按钮的顺序不决定状态。打个例子，12和21得到的状态是相同的。
公理2：同一个按钮按两次等于没按。打个例子，121与2得到的状态是相同的。
公理3：按钮123满足任意两个等于第三个。打个例子，12得到的状态与3是相同的。
通过以上三个公理，可以得到如下推论：
推论1：对于任意c＞4，所得到的状态总是与c≤4中的某种不重复序列的状态相同。证明：对于c＞4的按钮序列中，由抽屉原理得必然有一个按钮至少按了两次，就可以抵消掉。打个例子，12343→124。
推论2：对于任意2＜c≤4的不重复序列，所得到的状态总是与c≤2中的某种状态相同。证明：对于2＜c≤4的不重复序列，4出现的次数总是小于等于1，即至少有2个123中的按钮。由公理2与公理3得，任意2＜c≤4的不重复序列总是与c≤2的某种序列等效。打个例子，1234→114→4。
至此，我们可以得出最终的结论，即规律一：对于任意c，总能转化为c≤2时的某种状态。
规律二：当c≤2时，分别出现如下状态。
当c=0时，0；
当c=1时，1，2，3，4；
当c=2时，0，1(23)，2(13)，3(12)，14，24，34；
另外，由规律一，当c＞2时，有可能取到c≤2时的所有情况，即0，1，2，3，4，14，24，34。
规律三：无论哪种状态，循环节总为6。
因此，根据这三个规律，就可以用常量表存出所有c的情况，只需要挨个检验即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int h[9][7]= {{},
{0,0,0,0,0,0}, //1
{0,0,0,1,1,1}, //34
{1,0,1,0,1,0}, //2
{1,0,1,1,0,1}, //4
{0,1,0,0,1,0}, //14
{0,1,0,1,0,1}, //3
{1,1,1,0,0,0}, //24
{1,1,1,1,1,1} //0
};
int n,c,on[101],off[101];
inline void work(int w[9])
{
int flag=1;
for(int k=1; k<=w[0]; k++)
{
int tag=0;
for(int i=1; i<=on[0]; i++)
if(!h[w[k]][on[i]%6])
{tag=1;break;}
if(tag) continue;
for(int i=1; i<=off[0]; i++)
if(h[w[k]][off[i]%6])
{tag=1;break;}
if(tag) continue;
flag=0;
for(int i=1; i<=n; i++)
printf("%d",h[w[k]][i%6]);
printf("\n");
}
if(flag) printf("IMPOSSIBLE");
exit(0);
}
int main()
{
int tmp;
scanf("%d%d",&n,&c);
while(1)
{
scanf("%d",&tmp);
if(tmp==-1) break;
on[++on[0]]=tmp;
}
while(1)
{
scanf("%d",&tmp);
if(tmp==-1) break;
off[++off[0]]=tmp;
}
if(c==0)
{int w[9]={1,8};work(w);}
if(c==1)
{int w[9]= {4,1,3,4,6};work(w);}
if(c==2)
{int w[9]= {7,1,2,3,5,6,7,8};work(w);}
if(c>2)
{int w[9]= {8,1,2,3,4,5,6,7,8};work(w);}
return 0;
}