關鍵在于發(fā)現幾個規(guī)律：
某一按鈕，按偶數次等同于沒按。
按鈕的先后次序不影響結果。
燈的狀態(tài)6位一組不變(解題時沒發(fā)現這個規(guī)律，開了個100大小的bool數組)
剩下就是幾個操作的排列組合了。代碼寫得很繁...
#include?<iostream>
#include?<fstream>
#include?<vector>
#include?<algorithm>
using?namespace?std;
ifstream?fin("lamps.in");
ofstream?fout("lamps.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
struct?state_node{
????bool?states[101];
????int?len;
????bool?operator<(const?state_node?&?n1)?const{
????????for(int?i=1;i<=len;++i){
????????????if(states[i]!=n1.states[i])
????????????????return?states[i]<n1.states[i];
????????}
????????return?false;
????}
????bool?operator==(const?state_node?&?n1)?const{
????????for(int?i=1;i<=len;++i){
????????????if(states[i]!=n1.states[i])
????????????????return?false;
????????}
????????return?true;
????}
};
state_node?node;
int?n,c;
vector<int>finalon,finaloff;
vector<state_node>?result;
void?op(int?kind)
{
????switch(kind){
????????case?1:
????????????for(int?i=1;i<=n;++i)
?????????????????node.states[i]=!node.states[i];
????????????break;
????????case?2:
????????????for(int?i=1;i<=n;++i){
????????????????if(i&1)
????????????????????node.states[i]=!node.states[i];
????????????}
????????????break;
????????case?3:
????????????for(int?i=1;i<=n;++i){
????????????????if(!(i&1))
????????????????????node.states[i]=!node.states[i];
????????????}
????????????break;
????????case?4:
????????????for(int?i=1;i<=n;++i){
????????????????if(i%3==1){
????????????????????node.states[i]=!node.states[i];
????????????????}
????????????}
????????????break;
????}
}
bool?isok()
{
????for(int?i=0;i<finalon.size();++i){
????????if(!node.states[finalon[i]])
????????????return?false;
????}
????for(int?i=0;i<finaloff.size();++i){
????????if(node.states[finaloff[i]])
????????????return?false;
????}
????return?true;
}
void?do0()
{
????if(isok())
????????result.push_back(node);
}
void?do1()
{
????for(int?i=1;i<=4;++i){
????????op(i);
????????if(isok()){
????????????result.push_back(node);
????????}
????????op(i);
????}
}
void?do2()
{
????for(int?i=1;i<=3;++i){
????????for(int?j=i+1;j<=4;++j){
????????????op(i);
????????????op(j);
????????????if(isok()){
????????????????result.push_back(node);
????????????}
????????????op(i);
????????????op(j);
????????}
????}
}
void?do3()
{
????//操作1,2,3,4各執(zhí)行一次，前三個操作抵消
????op(4);
????do1();
}
void?do4()
{
????op(4);
????if(isok()){
????????result.push_back(node);
????}
????op(4);
}
void?action(int?i)
{
????switch(i){
????????case?0:?do0();break;
????????case?1:?do1();break;
????????case?2:?do2();break;
????????case?3:?do3();break;
????????case?4:?do4();break;
????}
}
void?solve()
{
????in>>n>>c;
????node.len?=?n;
????for(int?i=1;i<=n;++i)?
????????node.states[i]?=?true;
????int?t;
????do{
????????in>>t;
????????if(t!=-1)
????????????finalon.push_back(t);
????}while(t!=-1);
?????do{
????????in>>t;
????????if(t!=-1)
????????????finaloff.push_back(t);
????}while(t!=-1);
????bool?has_result?=?false;
????for(int?i=0;i<=4;++i){
????????if(c>=i&&(c-i)%2==0){
????????????action(i);
????????}
????}
????sort(result.begin(),result.end());
????vector<state_node>::iterator?end?=?
????????unique(result.begin(),result.end());
????for(vector<state_node>::iterator?i?=?result.begin();
????????????i!=end;?++i){
????????has_result?=?true;
????????for(int?j=1;j<=n;++j){
????????????out<<i->states[j];
????????}
????????out<<endl;
????}
????if(!has_result){
????????out<<"IMPOSSIBLE"<<endl;
????}
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}