65021 - [CSP-S2020] 动物园 zoo

解题思路

先找出所有被至少一个动物编号覆盖的二进制位。 如果某个二进制位对应一种饲料，但这个位没有被现有的动物覆盖，则新增的动物编号不能覆盖该位，否则会出现新饲料类型。

假如最后有 x 位可以被覆盖，最终答案为 2^x−n。

特别注意：需要考虑部分边界情况

参考代码

#include <bits/stdc++.h>
using namespace std;
const string str = "18446744073709551616"; const int N = 65;
bool vis[N], flag[N];
int main() {
	int n, m, c, k; cin >> n >> m >> c >> k;
 	for (int i = 1; i <= n; ++i) {
    	unsigned long long x; cin >> x;
    	for (int j = k - 1; j >= 0; --j) {
			vis[j] |= (x >> j) & 1;
		} 
  	}
  	for (int i = 1; i <= m; ++i) {
    	int p, q; cin >> p >> q;
    	if (!vis[p]) {
			flag[p] = true;
		}
  	}
  	int sum = 0;
  	for (int i = 0; i < k; ++i) {
  		if (flag[i]) {
  			++sum;
		}
	} 
  	if (k - sum == 64) {
    	if (n) { 
      		cout << (unsigned long long) -n << '\n';
      	} else { 
      		cout << str << '\n';
      	}
  	} else { 
  	  	cout << (1ull << (k - sum)) - n << '\n';
  	}
  	return 0;
}