欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 会展 > 洛谷 P7076 [CSP-S2020] 动物园(位运算)

洛谷 P7076 [CSP-S2020] 动物园(位运算)

2024/10/31 19:12:06 来源:https://blog.csdn.net/2403_87021226/article/details/142858029  浏览:    关键词:洛谷 P7076 [CSP-S2020] 动物园(位运算)

题目传送门

解题思路

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

然后对于每一个 p_i 和 q_i,我们可以判断一下这个饲料是否需要购买(对于原来有的动物)。

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

最后,统计第 1 到 k 的数位,如果这个数位没有被标记,那么我们的 ans 就要 \times 2(自己可以手推一下)。

注意,

k \leq 64,要开 unsigned long long,否则会溢出;

还有一种情况,就是 k=64,n=0 时,ans 会溢出,所以特判一下这种情况即可。

代码

#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;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com