首页 > 代码库 > usaco 2.2.4 生日派对灯（最近写题碰到的，虽然知道现在写这个有点晚了）
usaco 2.2.4 生日派对灯（最近写题碰到的，虽然知道现在写这个有点晚了）
经过分析，他看似很多的开灯的方法其实合并起来就只有八个。
首先，一个开关在执行的时候只能按一次（因为你就算按了两次就相当于一次也没有按）。
当一个都不按的时候 当然就只有一种：不按。
当按一下的时候：很明显（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 生日派对灯（最近写题碰到的，虽然知道现在写这个有点晚了）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。