动物园[CSP2020]

· · 题解

题解

这应该是最签到的一题了吧

饲料共有 c 种，1e8存不下，先对饲料编号进行重新标号

注意这里并不需要进行离散化(排序去重)，由于 q_i 互不相同，所以只需要把第 i 种饲料的编号看作 i 即可

首先对于已有的动物，先处理出 K 位中哪些位有动物是 1

然后扫一遍所有要求找出哪些饲料必买

最后再扫一遍所有要求算出 K 位中哪些位可以是 1

假设有 x 位可以是 1，那答案就是 2^x-n

注意点：

  1. 答案可能爆 long long ，需要 unsigned long long
  2. 如果 n=m=0,k=64，那么答案为 2^{64}，会爆 unsigned long long 。。。需要特判
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
typedef unsigned long long ull;

template <typename T>
inline void read(T &num) {
    T x = 0; char ch = getchar();
    for (; ch > '9' || ch < '0'; ch = getchar());
    for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
    num = x; 
}

int n, m, c, k, p[N];
ull a[N], S, ans, fst;
bool buy[N], ok[N];

void solvebuy() {
    for (int i = 1; i <= m; i++) {
        if ((S>>p[i])&1) buy[i] = 1;
    }
}
void solveans() {
    for (int i = 0; i < k; i++) ok[i] = 1;
    for (int i = 1; i <= m; i++) {
        if (!buy[i]) ok[p[i]] = 0;
    }
    int cnt = 0;
    for (int i = 0; i < k; i++) if (ok[i]) cnt++;
    if (cnt == 64) {
        ans = (1ull << 63) - n + (1ull << 63);
    } else ans = (1ull << cnt) - n;
} 

int main() {
    read(n); read(m); read(c); read(k);
    if (!n && !m && k == 64) {
        puts("18446744073709551616");
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        read(a[i]); S |= a[i];
    }
    for (int i = 1; i <= m; i++) {
        read(p[i]); read(fst);
    }
    solvebuy();
    solveans();
    cout << ans << endl; //%lld好像不太行 
    return 0;
}