题目链接：USACO - Party Lamps
观察后可以发现所有数字都与前4个数字有关。 1：所有 3k+1 的奇数 2：所有非 3k+1 的偶数 3：所有非 3k+1 的奇数 4：所有 3k+1 的偶数
而这四个灯只有16种状态，所以直接搜索然后判断即可。
/* ID: xdujlx1 PROG: lamps LANG: C++ */ #include<bits/stdc++.h> using namespace std; int b[4]={10,5,9,15}; bool vis[16]; int ini[107]; int c,n; void ioinit() { freopen("lamps.in","r",stdin); freopen("lamps.out","w",stdout); } void bfs() { queue<pair<int,int> > q; q.push(make_pair(15,0)); int cur=0; vis[15]=true; while(!q.empty()) { pair<int,int> p=q.front();q.pop(); if(p.second>=c) break; if(p.second>cur) { cur=p.second; memset(vis,0,sizeof(vis)); } for(int i=0;i<4;i++) { int t=p.first^b[i]; if(!vis[t]) { q.push(make_pair(t,p.second+1)); vis[t]=true; } } } } vector<int> get_ans(int k) { vector<int> a; for(int i=0;i<107;i++) a.push_back(0); a[1]=k&1;a[2]=(k>>1)&1;a[3]=(k>>2)&1;a[4]=(k>>3)&1; for(int i=5;i<=n;i+=2) if(i%3!=1) a[i]=a[3]; else a[i]=a[1]; for(int i=6;i<=n;i+=2) if(i%3!=1) a[i]=a[2]; else a[i]=a[4]; return a; } bool check(vector<int> & ans) { for(int i=1;i<=n;i++) { if(ini[i]==-1) continue; if(ini[i]^ans[i]) return false; } return true; } bool operator < (const vector<int> & a, const vector<int> & b) { for(int i=1;i<=n;i++) if(a[i]!=b[i]) return a[i]<b[i]; return false; } int main() { ioinit(); int t; scanf("%d%d",&n,&c); memset(ini,-1,sizeof(ini)); while(scanf("%d",&t)) { if(t==-1) break; ini[t]=1; } while(scanf("%d",&t)) { if(t==-1) break; ini[t]=0; } bfs(); vector<vector<int> > aans; for(int i=0;i<16;i++) { if(vis[i]) { vector<int> ans=get_ans(i); if(check(ans)) aans.push_back(ans); } } sort(aans.begin(),aans.end()); for(int i=0;i<aans.size();i++) { vector<int> & ans=aans[i]; for(int j=1;j<=n;j++) printf("%d",ans[j]); puts(""); } if(aans.size()==0) puts("IMPOSSIBLE"); return 0; }