首页 > 代码库 > 【贪心】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]起床困难综合症