BZOJ2102: [Usaco2010 Dec]The Trough Game

BZOJ2102: [Usaco2010 Dec]The Trough Game

https://lydsy.com/JudgeOnline/problem.php?id=2102

分析:

• 暴力枚举验证答案。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <set>
#include <vector>
#include <cmath>
using namespace std;
#define N 1500
typedef long long ll;
/*int n,K,a[N];
int main() {
    scanf("%d%d",&n,&K);
    int i;
    ll ans=0;
    for(i=1;i<=K;i++) scanf("%d",&a[i]);
    sort(a+1,a+K+1);
    reverse(a+1,a+K+1);
    for(i=1;i<=n/2&&i<=K;i++) {
        ans+=(n-(2*i-1))*a[i];
    }
    printf("%lld\n",ans);
}*/
int n,m,a[N],b[N],cnt[1<<20];
char w[N];
void print(int x,int dep) {
    if(!dep) return ;
    print(x>>1,dep-1);
    printf("%d",x&1);   
}
int main() {
    scanf("%d%d",&n,&m);
    int i,j;
    for(i=1;i<=m;i++) {
        scanf("%s%d",w+1,&b[i]);
        for(j=1;j<=n;j++) {
            a[i]=a[i]*2+w[j]-'0';
        }
    }
    int mask=(1<<n)-1;
    for(i=0;i<=mask;i++) cnt[i]=cnt[i>>1]+(i&1);
    int ans=0,tot=0;
    for(i=0;i<=mask;i++) {
        int flg=1;
        for(j=1;j<=m;j++) if(cnt[i&a[j]]!=b[j]) {
            flg=0; break;
        }
        if(flg) {
            ans=i; tot++;
        }
    }
    if(!tot) puts("IMPOSSIBLE");
    else if(tot>1) puts("NOT UNIQUE");
    else print(ans,n);
}

BZOJ2102: [Usaco2010 Dec]The Trough Game

原文：https://www.cnblogs.com/suika/p/10205638.html