首页 > 代码库 > NOI2014 Day1_T1 起床困难综合症
NOI2014 Day1_T1 起床困难综合症
题目不附了。。
做法:这题真是比NOI2011的内题还要水。。不过蒟蒻我只能想到nlom的做法,据说有o(n)的做法,真是神。。
统计每个数的每一位的二进制位,然后对每一位用0或1试,如果答案都是1,则保留0(尽量小)
一次AC。
Codes:
1 #include<set> 2 #include<queue> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<iostream> 7 #include<algorithm> 8 using namespace std; 9 const int N = 100100;10 #define For(i,n) for(int i=1;i<=n;i++)11 #define Rep(i,l,r) for(int i=l;i<=r;i++)12 #define Down(i,r,l) for(int i=r;i>=l;i--)13 struct ope{14 int kind,v;15 }A[32][N];16 char op[5];17 int pows[32],Yuan,n,m,val;18 19 void doit(int kth,int v){20 int tot = 0 , kind;21 if(op[0]==‘A‘) kind = 1;22 if(op[0]==‘O‘) kind = 2;23 if(op[0]==‘X‘) kind = 3;24 while(v){25 A[tot][kth].kind = kind;A[tot][kth].v = v % 2;26 v/=2;tot++;27 }28 Rep(i,tot,30) A[i][kth].kind = kind;29 }30 31 void init(){32 scanf("%d%d",&n,&m);33 pows[0] = 1;34 For(i,30) pows[i] = pows[i-1] * 2;35 For(i,n){36 scanf("\n");37 scanf("%s %d",&op,&val);38 doit(i,val);39 }40 }41 42 int Check(int kth,int M){43 For(i,n){44 if(A[kth][i].kind==1) M = M & A[kth][i].v;45 if(A[kth][i].kind==2) M = M | A[kth][i].v;46 if(A[kth][i].kind==3) M = M ^ A[kth][i].v;47 }48 return M;49 }50 51 void Work(){52 int ans = 0;53 Down(i,30,0){54 if(Check(i,0)==1) {55 ans+=pows[i];56 }57 else{58 if(Yuan+pows[i]<=m){59 if(Check(i,1)==1){60 ans+=pows[i];61 Yuan+=pows[i];62 }63 }64 }65 }66 printf("%d\n",ans);67 }68 69 int main(){70 freopen("sleep.in","r",stdin);71 freopen("sleep.out","w",stdout);72 init();73 Work();74 return 0;75 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。