又是来回2次等于没按,一个结构体 no3odd,speodd,no3even,speeven代表非-1%3 奇数偶数,普通奇数偶数。
然后当按1-4次时,归纳出1次对应4种情况,2次对应0次和2种各一次(1+6),3次对应(1,3)(4+4),4次对应(0,2,4)(1+6+4)
超过4以后的偶数情况等同于4,偶数等同于3
随后根据C取值枚举便可
/* ID: hubiao cave PROG: lamps LANG: C++ */ #include<iostream> #include<fstream> #include<string> #include<set> using namespace std; struct Bu { bool no3even; bool speeven; bool no3odd; bool speodd; Bu(){} Bu(int _noev,int _spee,int _no,int _sp):no3even(_noev),speeven(_spee),no3odd(_no),speodd(_sp){;} }; Bu buf[4][6]={{Bu(0,0,0,0),Bu(1,1,0,0),Bu(0,0,1,1),Bu(1,0,1,0)} ,{Bu(0,0,1,1),Bu(1,1,0,0),Bu(0,1,0,1),Bu(0,0,0,0),Bu(1,0,0,1),Bu(0,1,1,0)} ,{Bu(1,1,1,1),Bu(0,1,1,0),Bu(1,0,0,1),Bu(0,1,0,1)} ,{Bu(1,0,1,0)}}; /* 只按1次，4种 只按2次 可能是两种灯6，也可能是1种灯重复相当没按0 只按3次 同理相当于1种等，或者3种灯 只按4次 相当0，2，4 往后奇数次 与只按3相同，偶数次与4相同 */ set<string> ss; int main() { ifstream fin("lamps.in"); ofstream fout("lamps.out"); int no3even=-1,speeven=-1,no3odd=-1,speodd=-1; int N,C; fin>>N>>C; int lampOn,lampOff; while(fin>>lampOn,lampOn!=-1) { if(lampOn%2==0) { if((lampOn-1)%3==0) { speeven=1; continue; } else { no3even=1; continue; } } else { if((lampOn-1)%3==0) { speodd=1; continue; } else { no3odd=1; continue; } } } while(fin>>lampOff,lampOff!=-1) { if(lampOff%2==0) { if((lampOff-1)%3==0) { if(speeven==1) { fout<<"IMPOSSIBLE"<<endl; return 0; } speeven=0; continue; } else { if(no3even==1) { fout<<"IMPOSSIBLE"<<endl; return 0; } no3even=0; continue; } } else { if((lampOff-1)%3==0) { if(speodd==1) { fout<<"IMPOSSIBLE"<<endl; return 0; } speodd=0; continue; } else { no3odd=0; if(no3odd==1) { fout<<"IMPOSSIBLE"<<endl; return 0; } continue; } } } if(C==0) { if(no3even==0||no3odd==0||speodd==0||speeven==0) { fout<<"IMPOSSIBLE"<<endl; return 0; } string str; for(int i=1;i<=N;++i) { str+='1'; } fout<<str<<endl; return 0; } if(C<=4) { switch(C%4) { case 1: { for(int i=0;i<=3;i++) { if(buf[0][i].no3even!=no3even) { if(no3even!=-1) continue; } if(buf[0][i].speeven!=speeven) { if(speeven!=-1) continue; } if(buf[0][i].no3odd!=no3odd) { if(no3odd!=-1) continue; } if(buf[0][i].speodd!=speodd) { if(speodd!=-1) continue; } string str; for(int i=1;i<=N;i++) { if(i%2==0) { if((i-1)%3==0) str+='0'+buf[0][i].speeven; else str+='0'+buf[0][i].no3even; } else { if((i-1)%3==0) str+='0'+buf[0][i].speodd; else str+='0'+buf[0][i].no3odd; } } ss.insert(str); } break; } case 2: { string str; for(int i=1;i<=N;i++) { str+='1'; if(i==N) ss.insert(str); } for(int i=0;i<=5;i++) { if(buf[1][i].no3even!=no3even) { if(no3even!=-1) continue; } if(buf[1][i].speeven!=speeven) { if(speeven!=-1) continue; } if(buf[1][i].no3odd!=no3odd) { if(no3odd!=-1) continue; } if(buf[1][i].speodd!=speodd) { if(speodd!=-1) continue; } string str; for(int i=1;i<=N;i++) { if(i%2==0) { if((i-1)%3==0) str+='0'+buf[1][i].speeven; else str+='0'+buf[1][i].no3even; } else { if((i-1)%3==0) str+='0'+buf[1][i].speodd; else str+='0'+buf[1][i].no3odd; } } ss.insert(str); } break; } case 3: { for(int i=0;i<=3;i++) { if(buf[0][i].no3even!=no3even) { if(no3even!=-1) continue; } if(buf[0][i].speeven!=speeven) { if(speeven!=-1) continue; } if(buf[0][i].no3odd!=no3odd) { if(no3odd!=-1) continue; } if(buf[0][i].speodd!=speodd) { if(speodd!=-1) continue; } string str; for(int j=1;j<=N;j++) { if(j%2==0) { if((j-1)%3==0) str+='0'+buf[0][i].speeven; else str+='0'+buf[0][i].no3even; } else { if((j-1)%3==0) str+='0'+buf[0][i].speodd; else str+='0'+buf[0][i].no3odd; } } ss.insert(str); } for(int i=0;i<=3;i++) { if(buf[2][i].no3even!=no3even) { if(no3even!=-1) continue; } if(buf[2][i].speeven!=speeven) { if(speeven!=-1) continue; } if(buf[2][i].no3odd!=no3odd) { if(no3odd!=-1) continue; } if(buf[2][i].speodd!=speodd) { if(speodd!=-1) continue; } string str; for(int j=1;j<=N;j++) { if(j%2==0) { if((j-1)%3==0) str+='0'+buf[2][i].speeven; else str+='0'+buf[2][i].no3even; } else { if((j-1)%3==0) str+='0'+buf[2][i].speodd; else str+='0'+buf[2][i].no3odd; } } ss.insert(str); } break; } case 0: { string str; for(int i=1;i<=N;i++) { str+='1'; if(i==N) ss.insert(str); } for(int i=0;i<=5;i++) { if(buf[1][i].no3even!=no3even) { if(no3even!=-1) continue; } if(buf[1][i].speeven!=speeven) { if(speeven!=-1) continue; } if(buf[1][i].no3odd!=no3odd) { if(no3odd!=-1) continue; } if(buf[1][i].speodd!=speodd) { if(speodd!=-1) continue; } string str; for(int j=1;j<=N;j++) { if(j%2==0) { if((j-1)%3==0) str+='0'+buf[1][i].speeven; else str+='0'+buf[1][i].no3even; } else { if((j-1)%3==0) str+='0'+buf[1][i].speodd; else str+='0'+buf[1][i].no3odd; } } ss.insert(str); } for(int i=0;i<1;i++) { if(buf[3][i].no3even!=no3even) { if(no3even!=-1) continue; } if(buf[3][i].speeven!=speeven) { if(speeven!=-1) continue; } if(buf[3][i].no3odd!=no3odd) { if(no3odd!=-1) continue; } if(buf[3][i].speodd!=speodd) { if(speodd!=-1) continue; } string str; for(int j=1;j<=N;j++) { if(j%2==0) { if((j-1)%3==0) str+='0'+buf[3][i].speeven; else str+='0'+buf[3][i].no3even; } else { if((j-1)%3==0) str+='0'+buf[3][i].speodd; else str+='0'+buf[3][i].no3odd; } } ss.insert(str); } } break; } } else { if(C%2) { for(int i=0;i<=3;i++) { if(buf[0][i].no3even!=no3even) { if(no3even!=-1) continue; } if(buf[0][i].speeven!=speeven) { if(speeven!=-1) continue; } if(buf[0][i].no3odd!=no3odd) { if(no3odd!=-1) continue; } if(buf[0][i].speodd!=speodd) { if(speodd!=-1) continue; } string str; for(int j=1;j<=N;j++) { if(j%2==0) { if((j-1)%3==0) str+='0'+buf[0][i].speeven; else str+='0'+buf[0][i].no3even; } else { if((j-1)%3==0) str+='0'+buf[0][i].speodd; else str+='0'+buf[0][i].no3odd; } } ss.insert(str); } for(int i=0;i<=3;i++) { if(buf[2][i].no3even!=no3even) { if(no3even!=-1) continue; } if(buf[2][i].speeven!=speeven) { if(speeven!=-1) continue; } if(buf[2][i].no3odd!=no3odd) { if(no3odd!=-1) continue; } if(buf[2][i].speodd!=speodd) { if(speodd!=-1) continue; } string str; for(int i=1;i<=N;i++) { if(i%2==0) { if((i-1)%3==0) str+='0'+buf[2][i].speeven; else str+='0'+buf[2][i].no3even; } else { if((i-1)%3==0) str+='0'+buf[2][i].speodd; else str+='0'+buf[2][i].no3odd; } } ss.insert(str); } } else { if(no3even==0||no3odd==0||speodd==0||speeven==0) { ; } else{ string str; for(int i=1;i<=N;i++) { str+='1'; if(i==N) ss.insert(str); } } for(int i=0;i<=5;i++) { if(buf[1][i].no3even!=no3even) { if(no3even!=-1) continue; } if(buf[1][i].speeven!=speeven) { if(speeven!=-1) continue; } if(buf[1][i].no3odd!=no3odd) { if(no3odd!=-1) continue; } if(buf[1][i].speodd!=speodd) { if(speodd!=-1) continue; } string str; for(int j=1;j<=N;j++) { if(j%2==0) { if((j-1)%3==0) str+='0'+buf[1][i].speeven; else str+='0'+buf[1][i].no3even; } else { if((j-1)%3==0) str+='0'+buf[1][i].speodd; else str+='0'+buf[1][i].no3odd; } } ss.insert(str); } for(int i=0;i<1;i++) { if(buf[3][i].no3even!=no3even) { if(no3even!=-1) continue; } if(buf[3][i].speeven!=speeven) { if(speeven!=-1) continue; } if(buf[3][i].no3odd!=no3odd) { if(no3odd!=-1) continue; } if(buf[3][i].speodd!=speodd) { if(speodd!=-1) continue; } string str; for(int j=1;j<=N;j++) { if(j%2==0) { if((j-1)%3==0) str+='0'+buf[3][i].speeven; else str+='0'+buf[3][i].no3even; } else { if((j-1)%3==0) str+='0'+buf[3][i].speodd; else str+='0'+buf[3][i].no3odd; } } ss.insert(str); } } } if(ss.empty()) { fout<<"IMPOSSIBLE"<<endl; return 0; } for(set<string>::iterator it=ss.begin();it!=ss.end();it++) { fout<<*it<<endl; } return 0; }