首页 > 代码库 > usaco 2.2.4 生日派对灯（最近写题碰到的，虽然知道现在写这个有点晚了）

usaco 2.2.4 生日派对灯（最近写题碰到的，虽然知道现在写这个有点晚了）

2024-08-19 21:29:07   216人阅读

经过分析，他看似很多的开灯的方法其实合并起来就只有八个。

首先，一个开关在执行的时候只能按一次（因为你就算按了两次就相当于一次也没有按）。

当一个都不按的时候  当然就只有一种：不按。

当按一下的时候：很明显（1）（2）（3）（4）四种。

当按两下的时候：（1,2）（1,3）（1,4）（2,3）（2,4）（3,4）。 然而（1,2）就相当于是3；（1,3）=2；（2,3）=1；所以按两下的就只有（1,4）（2,4）（3,4）。

当按三下的时候：（1,2,3）（1,2,4）（1,3,4）（2,3,4）....。然而都可以相当于 空（3,4）（2,4）（1,4）也就是什么都没有了 QWQ；

按四下：应该就可以发现其实也是能和前面的合并；

所以所有的策略中就只有8中了：空 （1）（2）（3）（4）（1,4）（2,4）（3,4）。

这就已经把按灯的套路合并完了。

-----------------------------接下来是计数器c的情况的分析----------------------------------------------------

当c==0的时候，很明显：不按。

当c==1的时候，也很明显：（1）（2）（3）（4） 四种。

当c==2的时候，就有七种情况了：（1）[按2和3合并为1（(2)(3)的情况一样）]（2）（3）（1,4）（2,4）（3,4）不按（这里没有（4），因为无论如何按两下都不可能把（4）给按出来）。

当c==3的时候，所有情况都可以了（你问我为什么？？像第二步一样了）。

 

所以这道题很容易的就搞定了。

#include<iostream>
#include<cstdio>
#include<ctime>
#include<algorithm>
using namespace std;
int n,c,x;
int a[150],b[150],d[150];
long long q[150];
int t=0;
void init()
{
    cin>>n>>c;
    while((cin>>x)&&(x!=-1))
        a[x]=1;
    while((cin>>x)&&(x!=-1))
        b[x]=1;
}
void haha()
{
    for(int i=1;i<=n;i++)
        d[i]=1;
}
bool check()
{
    for(int i=1;i<=n;i++)
    {
        if((a[i])&&(!d[i])) return 0;
        if((b[i])&&(d[i]))  return 0;
    }
    return 1;
}
void print()
{
    for(int i=1;i<=n;i++)
        cout<<d[i];
    cout<<endl; t++;
}
void doit1()
{
    for(int i=1;i<=n;i++)
        d[i]=(d[i])?0:1;
}
void doit2()
{
    for(int i=1;i<=n;i+=2)
        d[i]=(d[i])?0:1;
}
void doit3()
{
    for(int i=2;i<=n;i+=2)
        d[i]=(d[i])?0:1;
}
void doit4()
{
    for(int i=1;i<=n;i+=3)
        d[i]=(d[i])?0:1;
}
int main()
{
        freopen("add.in","r",stdin);
    freopen("add.out","w",stdout);
    init();
    haha();
    switch(c)
    {
        case 0:
            if(check()) print();
            break;
        case 1:
            haha(); doit1();
            if(check()) print();
            haha(); doit2();
            if(check()) print();
            haha(); doit3();
            if(check()) print();
            haha(); doit4();
            if(check()) print();
            break;
        case 2:
            haha(); doit1();
            if(check()) print();
            haha(); doit3(); doit4();
            if(check()) print();
            haha(); doit2();
            if(check()) print();
            haha(); doit1(); doit4();
            if(check()) print();
            haha(); doit3();
            if(check()) print();
            haha(); doit2(); doit4();
            if(check()) print();
            haha();
            if(check()) print();
            break;
        default:
            haha(); doit1();
            if(check()) print();
            haha(); doit3(); doit4();
            if(check()) print();
            haha(); doit2();
            if(check()) print();
            haha();doit4();
            if(check()) print();
            haha(); doit1(); doit4();
            if(check()) print();
            haha(); doit3();
            if(check()) print();
            haha(); doit2(); doit4();
            if(check()) print();
            haha();
            if(check()) print();
            break;
    }
    if(t==0){ 
        cout<<"IMPOSSIBLE"<<endl;
    }
    return 0;
}

usaco 2.2.4 生日派对灯（最近写题碰到的，虽然知道现在写这个有点晚了）


联系
我们