首页 > 其他 > 详细

bzoj3668[Noi2014]起床困难综合症

时间:2016-07-30 14:44:56      阅读:309      评论:0      收藏:0      [点我收藏+]

bzoj3668[Noi2014]起床困难综合症

题意:

求0到m的一个数,使它被n次操作后最大。操作三种:&t、|t、^t,t为操作中给定的数。n≤100000,m,t≤1000000000

题解:

先求出0经过n次操作后得到的数,然后对于小于等于m的每个二进制位从大到小考虑一下当这位为1时是否比0好,如果好的话令这位为1并让m减去这个二进制位。因为n次操作后为1的二进制位越大越好,所以从大到小考虑是正确的。

代码:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 200000
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 using namespace std;
 7 
 8 inline int read(){
 9     char ch=getchar(); int f=1,x=0;
10     while(ch<0||ch>9){if(ch==-)f=-1; ch=getchar();}
11     while(ch>=0&&ch<=9)x=x*10+ch-0,ch=getchar();
12     return f*x;
13 }
14 char s[5]; int opt[maxn],p[maxn],ans,n,m;
15 int main(){
16     n=read(); m=read(); ans=0;
17     inc(i,1,n){
18         scanf("%s",s); if(s[0]==A)opt[i]=0; if(s[0]==O)opt[i]=1; if(s[0]==X)opt[i]=2; p[i]=read();
19     }
20     inc(i,1,n){
21         if(opt[i]==0)ans&=p[i]; if(opt[i]==1)ans|=p[i]; if(opt[i]==2)ans^=p[i];
22     }
23     for(int i=30;i>=0;i--){
24         int k=1<<i; if(k>m)continue;
25         inc(j,1,n){
26             if(opt[j]==0)k&=p[j]; if(opt[j]==1)k|=p[j]; if(opt[j]==2)k^=p[j];
27         }
28         if(!(ans&(1<<i))&&(k&(1<<i)))ans|=(1<<i),m-=(1<<i);
29     }
30     printf("%d",ans);
31 }

 

20160629

bzoj3668[Noi2014]起床困难综合症

原文:http://www.cnblogs.com/YuanZiming/p/5720779.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!