题解 P7076 【动物园（洛谷民间数据）】

· · 题解

考场思路

看到题目的限制条件，我们容易想到先把每一种动物的编号的二进制都表示出来，把每种动物的编号全部或起来，然后枚举每条限制，如果或的结果第 p_i 位为1，即有其中一种动物的编号二进制第 p_i 位为1，就说明第i条限制就会被满足，第 q_i 种饲料必须购买。

再分析数据规模，发现 c\le10^8，而 \text{256MB} 内存是可以存的下大小为 10^8 的 \text{bool} 型数组的。

于是我们直接开一个 \text{bool} 型数组一个数组记录饲料是否需要购买。

如果第 i 种饲料需要购买，那么所有 q_k=i 的第 k 条限制都可以不需要考虑了（因为新加入的动物的编号二进制的第 p_k 位不会对“第 q_k 种饲料一定要被购买”产生影响）。

反之，则所有 q_k=i 的第 k 条限制中的 p_k 都需要满足：新加入的动物的编号二进制的第 p_k 位都必须为0（否则就会影响饲料清单），我们这样的第 p_i 位标记起来。

那么，在可以新加入动物的编号的二进制中，没有被标记的二进制位都可以取0或1两个值。

然后把遍历所有二进制位求有多少种动物可以在动物园里，算出2的次幂，减去已有的n种动物，即为答案。

最后，由于 1\le k\le64 ，所以记得开 \text{unsigned long long} 。

另外，在 k=64 且 n=0 时，ans=2^{64} 会爆 \text{unsigned long long} 记得特判。

考场上我好像又没特判，又把读入ull写错了，沦为70pts。。。

具体参见代码。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e6+6;
int n,m,k,c,ans;
unsigned long long a[maxn],sum,ani,mi;  
struct rues{int p,q;}fg[maxn];
bool vis[100000007];
int main(){
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&c,&k);
    for(int i=1;i<=n;i++){
        scanf("%llu",&a[i]);
        sum|=a[i];
    }
    for(int i=1;i<=m;i++)
        scanf("%d%d",&fg[i].p,&fg[i].q);                              
    for(int i=1;i<=m;i++)                                                         
        if(sum&(1ull<<fg[i].p))                                     
            vis[fg[i].q]=1;                                                                                            
    for(int i=1;i<=m;i++)                                                       
        if(vis[fg[i].q]==0)                                          
            ani|=(1ull<<fg[i].p);                                       
    for(int i=0;i<k;i++)                                                                                           
        if((ani&(1ull<<i))==0)ans++;           //2的几次幂 
    if(ans==64)cout<<18446744073<<709551616-n;        //特判很重要 
    else{
        mi=1; 
        for(int i=1;i<=ans;i++)mi*=2;                                                       
        printf("%llu",mi-1ull*n);
    }
    return 0;
}

多说几句

考完后发现题目中有这么句话：

数据保证所有 a_i 互不相同，所有的 q_i 互不相同。

那么可能有更加简便的方法，欢迎指正。