csp- 2020 动物园题解

考场代码蜜汁MLE

签到题没了。

题目描述。

考虑如何A掉此题

读完题，我们首先要意识到，要把所有动物编号二进制中出现的位数记录下来。我们用一个aa将所有动物编号或起来，就OK了

考虑第二步，如何确定可以被加入的动物编号。

因为所有的动物编号都可以用一个64位的01数组考虑（2的64次方表示），我们一位一位的想。对于当前一位的二进制编号：

　　1.如果这个位上没有绑定饲料编号，很明显选不选对答案无影响，那么它就可以对答案造成2倍的贡献（*2）。

　　2.如果绑定了饲料，但是已经饲养的动物编号中有这一位（也就是aa的这一位为1），说明这一位所代表的饲料已经出现在饲料清单中，很明显选不选对答案无影响,那么它就可以对答案造成2倍的贡献（*2）。

　　3.如果绑定了饲料，但是aa这一位为0，如果我们选了这一位，那么这一位所要选的饲料就会出现在榜单中，但是很明显当前是没有的，也就是说这种情况下选了会对清单造成影响，不能选。

　　4.如果没有绑定饲料，但是aa这一位选了，很明显选不选对答案无影响。

综上所述，只有情况3不能选。

那么我们就能得知求解答案的方式：

整一个长度为64的数组记为wei[65]，初始值为1，代表都可以选，对于出现的p,q(意思和体面中的一样),我们判断aa第p位上是否为1，如果为0，那么不能选，把wei[p]赋值为0。

这样读完p，q之后，剩下的wei中有b个为1，答案就是2^b-n

2^b-n意义也很好理解，就是可以选的动物编号的方案数减去已经出现过的动物编号数，剩下的就是还可以添加的。

为了优化时间复杂度，将wei[]数组的0和1的意义倒过来，这样就免去的开始时for一遍赋值的时间。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
int n,m,c,k,p,q,can[65];
unsigned ll aa,ans=1,aaa;
void print()
{
    for(int i=0;i<k;i++)
    {
        if(!can[i])ans*=2;
    }
    cout<<ans-n;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&c,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%llu",&aaa);
        aa|=aaa;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&p,&q);
        if(!(((unsigned ll)1<<p)&aa))can[p]=1;
    }
    if(!n)
    {
        if(!m&&k==64)
        {
            printf("18446744073709551616
");
        }
        else
        {
            print();
        }
        return 0;
    }
    else
    {
        print();
    }
    return 0;
}

祝进入noip的同学rp++！

完结撒花

csp- 2020 动物园 题解

csp- 2020 动物园题解