写在前面

挂了。
noip 还是要打的。
先来补题了，补游记看心情。

A

出题人（1582/10/4 ~ 1582/10/15）

先考虑

B

给定的要求，实际上是对动物编号二进制中某一位 01 情况的限制。
若某条件满足，则 存在 一种动物的二进制该位为 1。
一种原来不存在的动物 不能 加入动物园的条件是该动物满足了 原来不满足 的一条要求，即其某二进制位上为 1。

可以通过位运算简单得到多少位上可以为 1，设有 \(k‘\) 位，答案即为 \(2^{k‘} - n\)。

注意特判答案为 \(2^{64}\) 的情况。\(2^{64}-1\) 可以通过 ull 溢出得到。

//知识点：瞎搞
/*
By:Luckyblock
*/
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#define ULL unsigned long long
const int N = 1e6 + 10;
//==================================================
int n, m, c, k, num, noneed[N];
ULL havea, havec, ans;
//==================================================
int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == ‘-‘) f = -1;
  for (; isdigit(ch); ch = getchar()) w = 10 * w + ch - ‘0‘;
  return f * w;
}
//==================================================
int main() {
  n = read(), m = read(), c = read(), k = read();
  for (int i = 1; i <= n; ++ i) {
    ULL a;
    std::cin >> a;
    havea |= a;
  }
  for (int i = 1; i <= m; ++ i) {
    int p = read(), q = read();
    if (! ((1ull << (1ull * p)) & havea)) { //所有q 不相同 
      num += ! noneed[p];
      noneed[p] = true; //第 p 位上为 1 是不合法的，会加入新饲料 
    }
  }
  if ((k - num) == 64) {
    if (! n) {
      printf("18446744073709551616\n");
      return 0;
    } else {
      ans = 0 - n; 
    }
  } else {
    ans = (1ull << (1ull * k -num)) - 1ull * n; 
  }
  std::cout << ans;
  return 0;
}

暴力

#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cstring>
#define LL long long
#define ULL unsigned long long
const int N = 2e6 + 10;
//==================================================
int n, m, c, k, ans, a[N];
int p[N], q[N];
bool visa[N], visc[N];
//==================================================
int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == ‘-‘) f = -1;
  for (; isdigit(ch); ch = getchar()) w = 10 * w + ch - ‘0‘;
  return f * w;
}
//==================================================
int main() {
  n = read(), m = read(), c = read(), k = read();
  for (int i = 1; i <= n; ++ i) {
    a[i] = read();
    visa[a[i]] = true;
  }
  for (int i = 1; i <= m; ++ i) {
    p[i] = read(), q[i] = read();
    for (int j = 1; j <= n; ++ j) {
      if ((a[j] >> p[i]) & 1) {
        visc[q[i]] = true;
        break;
      }
    }
  }
  
  for (int i = 0, lim = (1 << k) - 1; i <= lim; ++ i) {
    if (visa[i]) continue ;
    int flag = 1;
    for (int j = 1; j <= m; ++ j) {
      if ((i >> p[j]) & (! visc[q[j]])) {
        flag = 0;
        break;
      }
    }
    ans += flag;
  }
  printf("%d\n", ans);
  return 0;
}

C

D

CSP2020-S 题解

原文：https://www.cnblogs.com/luckyblock/p/13945486.html