首页 > 代码库 > [NOI2014]起床困难综合症

[NOI2014]起床困难综合症

2024-11-10 17:38:02   203人阅读

题目：UOJ#2、BZOJ3668、洛谷P2114、codevs3311、Vijos P1864。

题目大意：一个人能释放0~m伤害值的能量，但能量穿过防御门时伤害值会经过一些运算（AND，OR，XOR）而改变，问你最终能对Boss造成多少伤害。

解题思路：贪心，我们枚举释放出的伤害值的每一个二进制位，如果该位为1时能造成更多的伤害，则让这位为1，否则让它为0。最后得到的结果经过防御门后就是答案。简单的位运算即可。

C++ Code：

 

#include<cstdio>int n,m,ans=0;int op[100005],a[100005];int main(){	scanf("%d%d",&n,&m);	for(int i=1;i<=n;++i){		char s[5];		scanf("%s%d",s,&a[i]);		if(s[0]==‘A‘)op[i]=0;else		if(s[0]==‘O‘)op[i]=1;else		op[i]=2;	}	for(int i=30;i>=0;--i){		if(ans+(1<<i)>m)continue;		int x=ans,y=ans+(1<<i);		for(int j=1;j<=n;++j)		if(op[j]==0){			x&=a[j];			y&=a[j];		}else		if(op[j]==1){			x|=a[j];			y|=a[j];		}else{			x^=a[j];			y^=a[j];		}		if(x<y)ans+=(1<<i);	}	for(int i=1;i<=n;++i)	if(op[i]==0)ans&=a[i];else	if(op[i]==1)ans|=a[i];else	ans^=a[i];	printf("%d\n",ans);	return 0;}

 

[NOI2014]起床困难综合症


联系
我们