转载

USACO 2.2 Party Lamps 派对灯 (lamps)

题目描述

在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'。

输入输出样例

Copy

10 1 -1 7 -1

Copy

0000000000 0101010101 0110110110

提示

在这个样例中，有10盏灯，只有1个按钮被按下。最后7号灯是关着的。

在这个样例中，有三种可能的状态：

* 所有灯都关着

* 1,4,7,10号灯关着，2,3,5,6,8,9亮着。

* 1,3,5,7,9号灯关着，2, 4, 6, 8, 10亮着。

开始做的时候很没思路几欲想打dfs 然后看NOCOW("又"是Nocow) 然后发现了一个常数表的打发我相信他讲的肯定要比我讲得好所以先给个链接然而我还是说一下我的理解其实仔细看可以发现是每6个一循环的为什么呢 ? 即gcd(1,2,2,3) 其次按2按3=按1 按1按2=按3 按1按3=按2 按1按2按3=不按.......(以下省略) 这之后把所有的情况用一个常数表保存起来最后遍历一遍对他给出确定的按或不按的灯再到这个常数表里看是否吻合然后就是一些边界的考虑了再者我这个代码在usaco里是可以a的但yzoi总是有一个点过不去(什么坑爹数据......)

有图为证:

USACO 2.2 Party Lamps 派对灯 (lamps)

代码如下:

/* ID:laphets PROG:lamps LANG:C++ */ #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=10000+10; int n,c,x,tmp; int data[maxn]; int cnt1,cnt2; int light[9][7]= {  0,0,0,0,0,0,0,  0,0,0,0,0,0,0,  //push 1  0,0,0,1,1,1,0,  //push 1 and 4  0,0,1,0,1,0,1,  //push 3  0,0,1,1,0,1,1,  //push 1 and 4  0,1,0,0,1,0,0,  //push 4  0,1,0,1,0,1,0,  //push 2  0,1,1,0,0,0,1,  //push 2 and 4  0,1,1,1,1,1,1,  //no push }; int minmum[9]={0,1,2,1,2,1,1,2,0}; int main() { //  freopen("1.sb","r",stdin);  freopen("lamps.in","r",stdin);  freopen("lamps.out","w",stdout);   cin>>n>>c;  memset(data,-1,sizeof(data));  while(cin>>x&&x!=-1)   data[x]=1,cnt1++;  while(cin>>x&&x!=-1)   data[x]=0,cnt2++;  if(c==0)  {      if(cnt1==n)   {    while(n--)     cout<<0;    cout<<endl;    return 0;   }     if(cnt2==0)   {    while(n--)     cout<<1;    cout<<endl;    return 0;   }   if(cnt2!=0)   {    cout<<"IMPOSSIBLE"<<endl;      return 0;   }  }  if(cnt1==n)  {   while(n--)    cout<<0;   cout<<endl;   return 0;  }  bool flag1=false;  for(int i=1;i<=8;i++)  {   bool flag2=true;   for(int j=1;j<=n;j++)   {    if(data[j]==-1)     continue;    tmp=j%6;    if(tmp==0)     tmp=6;    if(data[j]!=light[i][tmp])    {     flag2=false;     break;    }   }   if(flag2==true&&c>minmum[i])   { //      cout<<1<<endl;    flag1=true;    for(int 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; }

正文到此结束