CF467B Fedor and New Game

前言

传送门

本题思维难度：橙。

本题代码难度：橙或红。

综合难度：橙。

本人代码码量位居第二，但是呢，我的空格多，所以，还不来看一下？

题意

根据题目，若两人一人有 $j$，一人没 $j$，则异或后，第 $j$ 位为 $1$。

那么，题目转化为：已知有 $m + 1$ 个数，求出满足 $a_i$ 异或 $a_{m + 1}$ 结果的 $1$ 的个数小于等于 $k$ 这样的 $i$ 的个数。其中 $1 \le i < m + 1$。

分析

题意转化的差不多了。简单模拟即可。

我们并不需要使用 std::bitset。

这里，我们引入一个函数 __builtin_popcount()，可以计算一个整数二进制下有多少个 $1$。

Code

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

const int N = 5005;
int n, m, k, a[N], ans;

int main() {
	cin >> n >> m >> k;
	m++;
	for (int i = 1; i <= m; i++) cin >> a[i];
	for (int i = 1; i < m; i++) 
		if (__builtin_popcount(a[i] ^ a[m]) <= k)
			ans++;
	cout << ans;
	return 0;
}