题面

https://www.luogu.com.cn/problem/P7076

题解

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

饲料共有$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。。。需要特判

感觉会在2处挂5pts。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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;
}

评论