题解 P7076 【动物园】

## 题目大意 - 有 $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; } ```