USACO 2.2 Party Lamps 派对灯 (lamps)

时间：2024-01-02 14:43:20

题目描述

在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;

}

相关文章