USACO 2.2 Party Lamps 派对灯 (lamps)

10
1
-1
7 -1

0000000000
0101010101
0110110110

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

    有图为证:

  代码如下:

/*
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;
}