洛谷P2114 起床困难综合症【位运算】【贪心】

题目：https://www.luogu.org/problemnew/show/P2114

题意：有n个操作，每个可以是与、或、异或一个数。

初始值是0~m之间的一个数，问经过n个运算之后，可以得到的最大值是多少。

思路：

这个数的某一位不是0就是1，所以我们可以用一个全为1的数和一个全为0的数做n次操作。然后判断这个数的每个位应该是0还是1就行了。

从高位到低位开始贪心。如果0和1都可以得到1的话，就选0，因为这样数比较小之后贪心的选择比较多。

如果只有1可以得到1的话，看看选1的时候这个数会不会超过m了。不超过答案的这一位就可以是1.

 //#include<bits/stdc++>

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<stdlib.h>

 #include<queue>

 #include<map>

 #include<stack>

 #include<set>

 //#define LL __int128

 #define ull unsigned long long

 #define inf 0x7f7f7f7f 

 typedef long long LL;

 using namespace std;

 int n, m;

 int main()

 {

     scanf("%d%d", &n, &m);

     int allone = 0x7fffffff, allzero = ;

     for(int i = ; i < n; i++){

         char op[];

         int t;

         getchar();

         scanf("%s %d", op, &t);

         if(strcmp(op, "AND") == ){

             allone &= t;

             allzero &= t;

         }

         else if(strcmp(op, "OR") == ){

             allone |= t;

             allzero |= t;

         }

         else{

             allone ^= t;

             allzero ^= t;

         }

     }

     int ans = , t = ;

     for(int i = ; i >= ; i--){

         if(allzero & ( << i)){

             ans |= ( << i);

         }

         else if(allone & ( << i) && m >= (t | ( << i))){

             ans |= ( << i);

             t |= ( << i);

         }

     }

     printf("%d\n", ans);

     return ;

 }

巴特西

洛谷P2114 起床困难综合症【位运算】【贪心】

最新文章

热门文章