csp-s2020 T2 动物园

题目简述：

共有n个动物，m条要求，每条要求描述了第x位上是1的话，必须购买y饲料，动物园里已有的动物必须的饲料已经购买了，问题是：在不要求增加购买饲料的基础上，还能放进去多少种动物？共有k个二进制，数据保证输入的动物编号各不相同，给出的饲料种类各不相同，n和m的范围都是100万，饲料的范围是1亿，k的范围是64（k表示有多少个二进制）

题解：

1、暴力：

枚举动物，枚举m条要求，如果ai&&1<<xi==1的话，说明动物编号中满足这一条要求，b[i]=true;

暴力枚举i，范围在1<<k-1，枚举m条要求，如果b[j]==false，但是i&&1<<xi==true，则这个不满足

最终满足的是2的k次方减去n减去不满足要求的

2、正解

如果能找到有多少个位置符合要求，那么这些位置无论是0还是1都可以，1表示有这种饲料，0表示没这种饲料也行，最后符合要求的动物数量为1<<cnt个，去掉动物园的n个，就是最后的答案。这里面有个重要的条件是饲料各不相同，也就是说不可能不同的二进制位对应相同的饲料，如果是这样的话，可能比较难处理，但是这里去掉了这个条件

我们可以把所有的动物编号都或起来，或之后的值为F，之后枚举m个要求，如果F｜（1<<xi）!=F,那么说明这一个二进制没有，k--，同时设置这个值被访问过

最后，k表示哪些位置合法

3、改进

当然，如果这道题修改一下，不同的二进制位置可以对应相同的饲料，这样的话，此题的解法就完全不同，举个例子，1 4 5三个动物编号，0和2的二进制位有值，如果1和2都对应相同的饲料，那么其实相当于1也是合法的位置，这里就需要特殊的处理，杨宸骁的代码适合这种情况

这里，附上他的代码：

#include<bits/stdc++.h>

using namespace std;

int n,m,c,k,x[1000005],y[1000005],lsh[1000005],cnt;

unsigned long long xx;

bool f[1000005],flag[1000005],ff[1000005],fff[1000005];

int main(){

//	freopen("zoo.in","r",stdin);

//	freopen("zoo.out","w",stdout);

	cin>>n>>m>>c>>k;

	if(n==0&&k==64){

		cout<<"18446744073709551616";

		return 0;

	}

	for(int i=1;i<=n;i++){

		cin>>xx;

		int j=1;

		while(xx){

			if(xx&1)f[j-1]=true;

			xx/=2;

			j++;

		}

	}

	for(int i=1;i<=m;i++){

		cin>>x[i]>>y[i];

		lsh[i]=y[i];

	}

	sort(lsh+1,lsh+m+1);

	int tot=unique(lsh+1,lsh+m+1)-lsh-1;

	for(int i=1;i<=m;i++){

		y[i]=lower_bound(lsh+1,lsh+tot+1,y[i])-lsh;

		fff[x[i]]=true;

		if(f[x[i]]==true)flag[y[i]]=true;

	}

	for(int i=1;i<=m;i++){

		if(flag[y[i]]==true)ff[x[i]]=true;

	}

	for(int j=0;j<=k-1;j++){

		if(ff[j]||!fff[j])cnt++;

	}

	cout<<(1ull<<cnt)-n<<endl;

	return 0;

}

巴特西

csp-s2020 T2 动物园

最新文章

热门文章