传送门题目描述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输入 #14 4 1000 1 0110 1 1001 1 0011 1输出 #11010说明/提示样例解释四个序列分别表示如下对话问在第一个槽中有多少个槽里有食物——答1 11个。问在第二个和第三个槽中有多少个槽里有食物——答1 11个。问在第一个和第四个槽中有多少个槽里有食物——答1 11个。问在第三个和第四个槽中有多少个槽里有食物——答1 11个。从第一个问题可以知道第一个槽是有食物的。从第三个问题可以知道第四个槽是没有食物的。从第四个问题可以知道第三个槽是有食物的。从第二个问题可以知道第二个槽是没有食物的。思路暴力出奇迹。因为1 ≤ n ≤ 20 1\le n\le201≤n≤20 所以直接使用 DFS。尝试枚举所有槽的情况枚举到n nn之后检查是否合法即可。代码#includebits/stdc.husingnamespacestd;intn,m,tot,a[1500001],sum;string ans[1500001],s[100];boolcheck(string ss){boolflag0;for(inti1;im;i){intcnt0;for(intj0;jn;j)if((ss[j]1)(s[i][j]1))cnt;if(cnt!a[i])returnfalse;}returntrue;}voiddfs(intx,string s){if(xn1){if(check(s))//检查是否合法{if(tot1){coutNOT UNIQUE;exit(0);}ans[tot]s;}return;}dfs(x1,s0);dfs(x1,s1);}intmain(){cinnm;for(inti1;im;i)cins[i]a[i];dfs(1,);if(tot0)coutIMPOSSIBLE;elsefor(inti0;in;i)coutans[1][i];return0;}