题目大意:一排灯有n个,有４种开关,每种开关能改变一些灯现在的状态(亮的变暗,暗的变亮)现在已知一些灯的亮暗情况,问所以可能的情况是哪些
思路:同一种开关开两次显然是没效果的,那么枚举每个开关是否开就好了，还是暴力大法好
1 /*{ 2 ID:a4298442 3 PROB:lamps 4 LANG:C++ 5 } 6 */ 7 #include<iostream> 8 #include<fstream> 9 #include<cstring> 10 #include<algorithm> 11 #define maxn 109 12 using namespace std; 13 ifstream fin("lamps.in"); 14 ofstream fout("lamps.out"); 15 //#define fin cin 16 //#define fout cout 17 int lamp[maxn],temp[maxn],n1,n2,a[maxn],b[maxn]; 18 struct T 19 { 20 char ch[maxn]; 21 }ans[maxn]; 22 void but1(int n) 23 { 24 for(int i=1;i<=n;i++)lamp[i]^=1; 25 } 26 void but2(int n) 27 { 28 for(int i=1;i<=n;i+=2)lamp[i]^=1; 29 } 30 void but3(int n) 31 { 32 for(int i=2;i<=n;i+=2)lamp[i]^=1; 33 } 34 void but4(int n) 35 { 36 for(int i=0;i*3+1<=n;i++)lamp[i*3+1]^=1; 37 } 38 int check(int n,int c,int count_now) 39 { 40 for(int i=1;i<n1;i++)if(lamp[a[i]]==0)return 0; 41 for(int i=1;i<n2;i++)if(lamp[b[i]]==1)return 0; 42 if(count_now>c)return 0; 43 int u=c-count_now; 44 if(u&1)return 0; 45 return 1; 46 } 47 int cmp(T x, T y) 48 { 49 return strcmp(x.ch+1,y.ch+1)>=0?false:true; 50 } 51 int main() 52 { 53 int n,c; 54 fin>>n>>c; 55 while(fin>>a[++n1]&&a[n1]!=-1); 56 while(fin>>b[++n2]&&b[n2]!=-1); 57 for(int i=1;i<=n;i++)temp[i]=1; 58 int h=0; 59 for(int i=0;i<=(1LL<<4)-1;i++) 60 { 61 int count_now=0; 62 memcpy(lamp,temp,sizeof(lamp)); 63 for(int j=1,idx=1;j<=i;j<<=1,idx++)if((i&j)!=0 ) 64 { 65 count_now++; 66 if(idx==1)but1(n); 67 if(idx==2)but2(n); 68 if(idx==3)but3(n); 69 if(idx==4)but4(n); 70 } 71 if(check(n,c,count_now)) 72 { 73 h++; 74 for(int i=1;i<=n;i++) 75 { 76 ans[h].ch[i]=lamp[i]+'0'; 77 } 78 } 79 } 80 if(h==0)fout<<"IMPOSSIBLE"<<endl;else 81 { 82 sort(ans+1,ans+1+h,cmp); 83 for(int i=1;i<=h;i++)fout<<ans[i].ch+1<<endl; 84 } 85 return 0; 86 }