题解 P7076 【动物园】
囧仙
2020-11-11 09:55:46
## 题目大意
- 有 $n$ 种动物,编号的范围是 $[0,2^{k})$ 。现在有 $c$ 种饲料。
- 有 $m$ 个限制条件。如果存在一个编号的第 $p_i$ 位为 $1$ ,则必须选第 $q_i$ 种饲料。
- 现在告诉你这些动物的编号,询问最多增加多少种动物,使得饲料的情况不变。
- 保证每种动物的编号以及每个限制条件的 $p_i$ 不同。
## 题解
这是本场 $\text{CSP}$ 的实质签到题。~~可见出题人的恶意~~。
显然,对于已有的信息,我们可以将动物的编号进行“或”操作,这样就可以判定有哪些位存在数字 $1$ 了。这时,我们可以知道哪些限制条件被达成,那些限制条件没有被达成。
现在考虑我们可以选择的动物编号的第 $i$ 位。
- 如果已经存在一个动物的编号的第 $i$ 位是 $1$ ,那么可选择的动物编号的第 $i$ 位可以是 $0$ 或 $1$ 。
- 如果不存在一个动物的编号的第 $i$ 位是 $1$ ,并且存在某个限制条件,使得第 $i$ 位是 $1$ 后会增加新的饲料,那么第 $i$ 位只能是 $0$ 。
这样子做比较麻烦,因为复杂度是 $\mathcal O(k\times m)$ 的。我们不妨从限制的角度来看待问题。我们考虑第 $i$ 个限制。
- 如果第 $i$ 个限制已经被达成,那么第 $p_i$ 位可以是 $0$ 或 $1$ 。
- 如果第 $i$ 个限制未达成,并且目前我们没有选择第 $q_i$ 个饲料,那么第 $p_i$ 位只能是 $0$ 。
这样做的复杂度是 $\mathcal O(m)$ 。
我们现在知道了一个合法的动物序号每一位可选择的数字个数,不妨设为 $w$ 。由于我们还要减去已经选择的 $n$ 个动物,因此最终答案为:
$$2^w-n$$
这题有一个小细节要考虑。当 $n=0,w=64$ 时,答案达到了 $2^{64}$ ,会炸 $\text{unsigned long long}$ 。需要特判。
这题还有一个小细节要考虑:如果用 $\text{map}$ 进行总复杂度为 $\mathcal O(n\log n)$ 的判断操作,可能会超时。我们需要更快的做法。
- 该题 $c\le 10^8$ ,空间限制 $128\text{MB}$ 。事实上,如果我们开一个 $10^8$ 大小的 $\text{bool}$ 数组并不会超空间(只会使用 $100\text{MB}$) 。
- 如果我们用 $\text{bitset}$ ,或者单纯地压位,也可以压缩空间为 $\frac{100}{8} \text{MB}$ 。
- 此外,还可以使用哈希表(拉链法或者探查法都可以)。这样做的空间复杂度是 $\mathcal O(s+n)$ ,其中 $s$ 是哈希表大小;单次操作的复杂度近似为 $\mathcal O(1)$ ,可以通过本题。
## 参考代码
```cpp
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
u64 qread(){
u64 r=0,w=1,c=0;
for(c=getchar();!isdigit(c);c=getchar()) w=(c=='-'?-1:1); r=c-'0';
for(c=getchar(); isdigit(c);c=getchar()) r=r*10+c-'0';
return r*w;
}
const int MAXN =1e6+3;
u64 s,ss,n,m,c,k,f=0,A[MAXN],B[MAXN],ans=1;
const int SIZ =999997;
int ver[MAXN],nxt[MAXN],head[SIZ],tot;
void add(int a,int b){
ver[++tot]=b,nxt[tot]=head[a],head[a]=tot;
}
bool fnd(int a){
for(int p=head[a%SIZ];p;p=nxt[p])
if(ver[p]==a) return true; return false;
}
int main(){
n=qread(),m=qread(),c=qread(),k=qread();
up(1,n,i){u64 w=qread(); s|=w;}
up(1,m,i) A[i]=qread(),B[i]=qread();
up(1,m,i){
u64 a=A[i],b=B[i]; if(s&(1ull<<a)) add(b%SIZ,b);
}
up(1,k,i) ss|=1<<i-1;
up(1,m,i){
u64 a=A[i],b=B[i]; if(!fnd(b)) ss&=~(1ull<<a);
}
up(1,k,i) if(ss&(1ull<<i-1)) ans<<=1,++f;
if(f==64&&n==0) puts("18446744073709551616");
else printf("%llu\n",ans-n);
return 0;
}
```