首页 > 代码库 > 【贪心】BZOJ3668-[NOI2014]起床困难综合症
【贪心】BZOJ3668-[NOI2014]起床困难综合症
【题目大意】
给定n次操作(与,或,异或),在0~m中选择一个数,使这个数经过n次操作后得到的值最大。
【思路】
水题orz
枚举这个数每一位的取值是0还是1,然后根据它经过n次操作后的结果判断:
(1)如果取0时,最后结果为1,那么必定取0。
(2)如果取1时,最后结果为1,且当前和小于等于m,那么取1。
(3)在上述两种情况均不满足的情况下,只能取0。
所以一开始取a=0,b=(111111111……1)2预处理下直接操作就好了^ ^
1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 int a,b,n,m; 8 9 void init()10 {11 scanf("%d%d",&n,&m);12 a=0,b=1073741823;13 for (int i=0;i<n;i++)14 {15 char str[3];16 int x;17 scanf("%s%d",str,&x);18 if (str[0]==‘A‘) a&=x,b&=x;19 else if (str[0]==‘O‘) a|=x,b|=x;20 else if (str[0]==‘X‘) a^=x,b^=x;21 }22 }23 24 void solve()25 {26 int attack=0,ans=0;27 for (int i=30;i>=1;i--)28 {29 if ((a>>(i-1))&1) ans+=1<<(i-1);30 else if (((b>>(i-1))&1) && attack+(1<<(i-1))<=m) ans+=1<<(i-1),attack+=(1<<(i-1));31 }32 printf("%d",ans);33 }34 35 int main()36 {37 init();38 solve();39 return 0;40 }
【贪心】BZOJ3668-[NOI2014]起床困难综合症
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。