洛谷 P7076 [CSP-S2020] 动物园（位运算）

题目传送门

解题思路

可以先开一个  把所有动物的编号或起来。

然后对于每一个  和 ，我们可以判断一下这个饲料是否需要购买（对于原来有的动物）。

如果它原本是不需要购买的，我们可以开一个  来标记这一位。

最后，统计第  到  的数位，如果这个数位没有被标记，那么我们的  就要 （自己可以手推一下）。

注意，

，要开 unsigned long long，否则会溢出；

还有一种情况，就是  时， 会溢出，所以特判一下这种情况即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
unsigned long long n,m,c,k;int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>c>>k;unsigned long long sum=0;unsigned long long x;for(int i=1;i<=n;i++){cin>>x;sum|=x;}unsigned long long p,q;ull g=0;for(int i=1;i<=m;i++){cin>>p>>q;if((sum&(1ull<<p))==0){g|=1ull<<p;}}ull ans=1;for(int i=0;i<k;i++){if((g&(1ull<<i))==0){ans=ans<<1;}}if(ans==0&&n==0){cout<<"18446744073709551616";return 0;}ans-=n;cout<<ans;return 0;
}