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

2017-10-06 14:47:32


对不起我拉低了这题的通过率qnq。。。

开始想打一个高斯消元,,然后细节好多啊

就开心的去打爆搜了

#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';
}