CSUSTOJ-辉夜大小姐想被猜中（简单暴力）

题目连接：http://acm.csust.edu.cn/problem/4049
CSDN食用链接：https://blog.csdn.net/qq_43906000/article/details/109454875

Description

这天辉夜和白银两个人在学生会里工作，辉夜突然想测试一下白银有多了解自己，于是向白银发起了 (q) 提问这个游戏。

(q) 提问的规则如下：辉夜给出 (m) 个对某个物品的描述，每个描述用一个长度为 (n) 的 (01) 串表示，之后辉夜会列举 (q) 个物品，每个物品也用一个长度为 (n) 的 (01) 串表示，每个物品都会符合 (m) 个描述中的 (s_i) 个(可能是 (0) 个)。

符合描述的条件是：我们把每个 (01) 串看成一个二进制整数，假设某个描述的 (01) 串为 (x) ，某个物品的的 (01) 串为 (y) ，当 ((x~xor~y) < k) 时，那么该物品就符合这个描述。

(xor) 表示两个数的异或，异或的运算法则为 (0~xor~1 = 1, 1~xor~1 = 0, 1~xor~0 = 1, 0~xor~0 = 0) ,

比如 ((010)~xor~(110) = 100) 。

白银认为 (s_i) 值最大的物品就是答案，于是他要计算出每个物品符合的描述的数量

注：

C/C++、Java、Python 中的异或运算符为 (wedge) (如：(c=a wedge b), (c) 为 (a)与(b)的异或值)

input

第1行输入两个整数(m,n) ((1 leq m leq 2e5, 1 leq n leq 12))

第2行起的(m)行，每行输入一个长度为(n)的01串

下一行输入两个整数(q,k) ((1 leq q,k leq 2e5))

下面q行，每行输入一个长度为(n)的01串，代表一次询问

output

输出(q)行，第(i)行代表第(i)次询问的答案

Sample Input 1
3 2
01
11
01
3 2
11
10
01
Sample Output 1
1
1
2

Sample Input 2
5 5
00110
00101
10101
01100
01001
5 15
01001
01000
10111
01010
00100
Sample Output 2
3
4
1
3
4

样例一：

第一次询问符合条件的01串有 “11”

第二次询问符合条件的01串有 "10"

第三次询问符合条件的01串有 "01", "01"

emmm，本来看到这题还有点虚的，毕竟我是个辣鸡，但看到(n<=12)的时候emmm，算了一下，总共也就(0 ightarrow 2^{12}-1)个数字，也不大，就4000+个数，那么我们直接暴力(n^2)统计对于每个数字有多少个数字和它异或小于k就完事了。

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

const int mac=1e5+10;

int nb[mac],ans[mac];
vector<pair<int,int>>ys;

int main(int argc, char const *argv[])
{
	int n,m;
	scanf ("%d%d",&m,&n);
	for (int i=1; i<=m; i++){
		int x,val=0;
		for (int j=0; j<n; j++)
			scanf ("%1d",&x),val|=x<<(n-j-1);
		nb[val]++;
	}
	for (int i=0; i<(1<<n); i++)
		if (nb[i]) ys.push_back({i,nb[i]});
	
	int q,k;
	scanf ("%d%d",&q,&k);
	for (int i=0; i<(1<<n); i++){
		for (auto x:ys){
			int id=x.first,num=x.second;
			if ((i^id)<k) ans[i]+=num;
		}
	}
	while (q--){
		int x,val=0;
		for (int i=0; i<n; i++)
			scanf ("%1d",&x),val|=x<<(n-i-1);
		printf ("%d
",ans[val]);
	}
	return 0;
}