首页 > 代码库 > USACO 2.2 Party Lamps 【高能等效+规律枚举】

USACO 2.2 Party Lamps 【高能等效+规律枚举】

题在这:https://www.luogu.org/problem/show?pid=1468#sub

按钮1:当按下此按钮,将改变所有的灯:本来亮着的灯就熄灭,本来是关着的灯被点亮。

按钮2:当按下此按钮,将改变所有奇数号的灯。

按钮3:当按下此按钮,将改变所有偶数号的灯。

按钮4:当按下此按钮,将改变所有序号是3*K+1(K>=0)的灯。例如:1,4,7...

此题关键:找到4个按钮之间的关系,可发现最终状态只有少数(可枚举的)几种,又:四个操作的影响周期取最小公倍数后,发现   6个灯为一个变化周期,不管如何按按钮,最终N个灯的状态均是以6个灯为基本单位,N/6为循环次数的循环序列

一、首先,从基本操作入手,随意搭配四个按钮,且每种按钮只能使用一次,可发现:(只考虑6个灯,0表示灯灭,1表示灯亮)

1        2         3          4

按1 ====》0 0 0 0 0 0

按2 ====》0 1 0 1 0 1 

按3 ====》1 0 1 0 1 0

按4 ====》0 1 1 0 1 1

按1和2====》1 0 1 0 1 0 ====》相当于按3

按1和3 ====》0 1 0 1 0 1 ====》相当于按2

按1和4 ====》1 0 0 1 0 0

按2和3 ====》0 0 0 0 0 0 ====》相当于按1

按2和4 ====》1 1 0 0 0 1

按3和4 ====》0 0 1 1 1 0

按1、2、3====》相当于按2遍三 ====》不变

按1、2、4====》相当于按3和4 

按1、3、4====》相当于按2和4
 
再加上不按 ====》1 1 1 1 1 1
共计8种最终状态(红色),故以后所有的状态都是由这8个中的一个为基本循环得到的
完成它们的最少操作次数分别为:1,1,1,3,2,2,2
就是按4这种情况,按4 可以一步,也可以三步或者三步以上(224)但是就是不能两步达到,故设为3,把按一次的情况特判
二、又由:
按1和按2相当于按3;
按2和按3相当于按1;
按1和按3相当于按2;
按1按2和按3相当于不按;
 
 
由(一)和(二)得,c 等于任意操作次数时,我们均可以用(一)搭出规律骨架,用(二)扩充(一)中的操作使凑齐c个操作,以这8个结果为基础,构造答案(只是为了证明正确性,不必输出),最后,只输出最终状态,完毕。
 
 
 
下面为参考代码(借鉴了“ly59782的博客”中的代码):
 
技术分享
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int state[9][7]={
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},//press 1
{0,0,0,1,1,1,0},//press 3 & 4
{0,0,1,0,1,0,1},//press 2
{0,0,1,1,0,1,1},//press 4
{0,1,0,0,1,0,0},//press 1 & 4
{0,1,0,1,0,1,0},//press 3
{0,1,1,0,0,0,1},//press 2 & 4
{0,1,1,1,1,1,1} //not pressing
};
int c,n,x,a[8];
int minn[9]={0,1,2,1,3,2,1,2};
bool flag=0;

int main()
{
    freopen("lamps.in","r",stdin);
    freopen("lamps.out","w",stdout);
    for(int i=1;i<=6;i++)
        a[i]=-1;
    cin>>n>>c;
    while(cin>>x,x!=-1)
    {
        int v=x%6;
        if(v==0) v=6;
        a[v]=1;        
    }
    while(cin>>x,x!=-1)
    {
        int v=x%6;
        if(v==0) v=6;
        a[v]=0;        
    }
    for(int i=1;i<=8;i++)
    {
        int f=1;
        for(int j=1;j<=6;j++)    
        {
            if(a[j]==-1)
                continue;
            if(a[j]!=state[i][j])
            {
                f=0;
                break;
            }
        }
        if(f==1&&(c>=minn[i]||(c==1&&i==4)))
        {
            for(int p=1;p<=n;p++)
            {
                int v=p%6;
                if(v==0) v=6;
                cout<<state[i][v];
                flag=1;
            }
            cout<<endl;
        }
    }
    if(!flag)
        cout<<"IMPOSSIBLE"<<endl;
    return 0;
}
View Code

 

USACO 2.2 Party Lamps 【高能等效+规律枚举】