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

NOI2014 Day1_T1 起床困难综合症

2024-07-14 11:20:03   220人阅读

题目不附了。。

做法：这题真是比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 }

 


联系
我们