USACO2.24 Party Lamps

it2022-05-06  9

题意:初始化,所有灯都是亮的,

之后总共只有四种操作

1)所有的灯情况都取反

2)编号为奇数的灯取反

3)编号为偶数的灯取反

4)编号为3*x+1 的灯取反

现在,问,执行了C步操作之后,某些灯的亮的,某些灯的关的,求出所有的灯的可能组合。

题意:

每个按钮按2次和没按效果是一样的。所以每个按钮或者按或者不按,一共有2^4=16种状态。枚举每个按钮是否按下,然后生成结果,排序输出即可(注意判重)。

/* ID: nanke691 LANG: C++ TASK: lamps */ #include<iostream> #include<fstream> #include<string> #include<algorithm> #include<set> using namespace std; int N,C,t1,t2; int on[110]={0},off[110]={0}; set<string> s; void judge(int a,int b,int c,int d) { string str=""; for(int i=1;i<=N;i++) { int t=a; if((i-1)%3==0) t+=d; if(i%2==0) t+=c; else t+=b; if(t%2==0) str+="1"; else str+="0"; } for(int i=0;i<t1;i++) { //cout<<"on"<<' '<<on[i]<<endl; if(str[on[i]-1]=='0') return; } for(int i=0;i<t2;i++) { //cout<<"off"<<' '<<off[i]<<endl; if(str[off[i]-1]=='1') return; } s.insert(str); } int main() { freopen("lamps.in","r",stdin); freopen("lamps.out","w",stdout); int a; cin>>N>>C; cin>>a; t1=0,t2=0; while(a!=-1) { on[t1++]=a; cin>>a; } cin>>a; while(a!=-1) { off[t2++]=a; cin>>a; } for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) for(int l=0;l<2;l++) { int c=i+j+k+l; if(c%2==C%2 && c<=C) judge(i,j,k,l); } set<string>::iterator it=s.begin(); if(s.size()!=0) { for(;it!=s.end();it++) cout<<*it<<endl; } else cout<<"IMPOSSIBLE"<<endl; }

 

转载于:https://www.cnblogs.com/nanke/archive/2011/10/29/2228506.html

相关资源:数据结构—成绩单生成器

最新回复(0)