题解 P3005 【[USACO10DEC]槽的游戏The Trough Game】

对不起我拉低了这题的通过率qnq。。。 开始想打一个高斯消元，，然后细节好多啊 就开心的去打爆搜了 ```cpp #include<bits/stdc++.h> using namespace std; int n,m,f[2000000],a[1000],b[1000],sum; bool kk; char c; bool pd(int y){ bool ff=true,fk=true; for (int i=1;i<=m;i++){ ff&=(f[a[i]&y]==b[i]); fk&=(f[a[i]&y]<=b[i]); }if (ff){ if (sum!=y&&kk){cout<<"NOT UNIQUE"<<endl;exit(0);}//搜到两个的话，， kk=true;sum=y; } if (fk)return true;else return false; } inline void dfs(int x,int y){ if (x==n){pd(y);return;} dfs(x+1,y); if (pd(y+(1<<x)))dfs(x+1,y+(1<<x)); } int main(){ ios::sync_with_stdio(false); cin>>n>>m;for (int i=1;i<=1<<20;i++)f[i]=f[i-(i&(-i))]+1; for (int i=1;i<=m;i++){ for (int j=1;j<=n;j++)cin>>c,a[i]=a[i]*2+c-'0';//状压 cin>>b[i]; }dfs(0,0);if (!kk){cout<<"IMPOSSIBLE"<<endl;return 0;}//搜不到。。 for (int i=n-1;i>=0;i--) if (sum&(1<<i))cout<<'1';else cout<<'0'; } ```