题解：P7076 [CSP-S2020] 动物园

GSQ0829 · 2024-12-27 12:20:23 · 题解

题目传送门

思路：

水题中的水题。这题如果放在普及组，可能也就是第二三题。

这题是一道关系进制的问题。

先找出所有被至少一个动物编号覆盖的二进制位。

如果某个二进制位对应一种饲料，但该位没有被现有的动物覆盖，则新增的动物编号不能覆盖该位（否则会导致出现新的饲料类型）。

代码讲解：

这题有以下几个需要注意的地方。

• 数据范围，需要开到 unsigned 才行。

  unsigned long long n, m, c, k, a, p, q, ans = 0, cnt = 1, g = 0;

• 特判程序。这样防止溢出。

  if (!n && !m && k == 64) {
  printf("18446744073709551616");
  return 0;
  } 

• 主程序

  for (int i = 0; i < m; i++) {
      cin >> p >> q;
      if (!((g >> p) & 1) && !v[p]) {
          ans--;
          v[p] = 1;
      } 
  }

code：

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

unsigned long long n, m, c, k, a, p, q, ans = 0, cnt = 1, g = 0;
bool v[65];

int main() {
    cin >> n >> m >> c >> k; 
    ans = k;
    if (!n && !m && k == 64) {
        printf("18446744073709551616");
        return 0;
    } 
    for (int i = 1; i <= n; i++) {
        cin >> a;
        g |= a;
    }
    for (int i = 0; i < m; i++) {
        cin >> p >> q;
        if (!((g >> p) & 1) && !v[p]) {
            ans--;
            v[p] = 1;
        } 
    }
    for (int i = 1; i <= ans; i++) cnt *= 2;
    printf("%llu\n", cnt - n);
    return 0;
}