P3005 [USACO10DEC] The Trough Game S

传送门

题目描述

Farmer John 和 Bessie 在玩一个游戏。

Farmer John 准备了n nn个槽（1 ≤ n ≤ 20 1\le n \le201≤n≤20），其中一些槽中藏有食物。Bessie 为了知道哪些槽中有食物，会询问m mm个形如“第x 1 ⋯ x k x_1\cdots x_kx1​⋯xk​号槽中是否有食物？”的问题（1 ≤ m ≤ 100 , 1 ≤ k ≤ n 1\le m\le100,1\le k\le n1≤m≤100,1≤k≤n）。

请你帮忙求出哪几个槽中有食物。

输入格式

第一行包含两个整数n , m n,mn,m，分别表示槽的个数和 Bessie 询问的问题数。

接下来m mm行每行包含一个长度为n nn的01 0101序列和一个整数t tt，其中01 0101序列中的1 11表示询问中提到了这个位置的槽，t tt表示这些槽中有t tt份食物。

输出格式

输出共一行。

若无解，则输出IMPOSSIBLE。

若不止一个解，则输出NOT UNIQUE。

若有唯一解，则输出一个01 0101序列，其中1 11表示这个位置的槽中有食物。

输入输出样例 #1

输入 #1

4 4 1000 1 0110 1 1001 1 0011 1

输出 #1

1010

说明/提示

样例解释

四个序列分别表示如下对话：

1. 问：在第一个槽中有多少个槽里有食物？——答：1 11个。
2. 问：在第二个和第三个槽中有多少个槽里有食物？——答：1 11个。
3. 问：在第一个和第四个槽中有多少个槽里有食物？——答：1 11个。
4. 问：在第三个和第四个槽中有多少个槽里有食物？——答：1 11个。

从第一个问题可以知道，第一个槽是有食物的。

从第三个问题可以知道，第四个槽是没有食物的。

从第四个问题可以知道，第三个槽是有食物的。

从第二个问题可以知道，第二个槽是没有食物的。

思路

暴力出奇迹，（）。

因为1 ≤ n ≤ 20 1\le n\le201≤n≤20， 所以直接使用 DFS。

尝试枚举所有槽的情况，枚举到n nn之后检查是否合法即可。

代码

#include<bits/stdc++.h>usingnamespacestd;intn,m,tot,a[1500001],sum;string ans[1500001],s[100];boolcheck(string ss){boolflag=0;for(inti=1;i<=m;i++){intcnt=0;for(intj=0;j<n;j++)if((ss[j]=='1')&&(s[i][j]=='1'))cnt++;if(cnt!=a[i])returnfalse;}returntrue;}voiddfs(intx,string s){if(x>=n+1){if(check(s))//检查是否合法{if(tot==1){cout<<"NOT UNIQUE";exit(0);}ans[++tot]=s;}return;}dfs(x+1,s+'0');dfs(x+1,s+'1');}intmain(){cin>>n>>m;for(inti=1;i<=m;i++)cin>>s[i]>>a[i];dfs(1,"");if(tot==0)cout<<"IMPOSSIBLE";elsefor(inti=0;i<n;i++)cout<<ans[1][i];return0;}