挂了。
noip 还是要打的。
先来补题了,补游记看心情。
出题人(1582/10/4 ~ 1582/10/15)
先考虑
给定的要求,实际上是对动物编号二进制中某一位 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;
}
原文:https://www.cnblogs.com/luckyblock/p/13945486.html