- 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);
- }
来源: http://www.bubuko.com/infodetail-2905158.html