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

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

阅读量：4701 次

发布时间：2019-06-09

本文共 1277 字，大约阅读时间需要 4 分钟。

题目：

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

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

思路：

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

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

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

1 //#include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
             9 #include
             
              10 #include
              
               11 12 //#define LL __int12813 #define ull unsigned long long14 #define inf 0x7f7f7f7f 15 16 typedef long long LL;17 using namespace std;18 19 int n, m;20 21 22 int main()23 {24 scanf("%d%d", &n, &m);25 int allone = 0x7fffffff, allzero = 0; 26 for(int i = 0; i < n; i++){27 char op[10];28 int t;29 getchar();30 scanf("%s %d", op, &t);31 if(strcmp(op, "AND") == 0){32 allone &= t;33 allzero &= t;34 }35 else if(strcmp(op, "OR") == 0){36 allone |= t;37 allzero |= t;38 }39 else{40 allone ^= t;41 allzero ^= t;42 }43 } 44 int ans = 0, t = 0;45 for(int i = 30; i >= 0; i--){46 if(allzero & (1 << i)){47 ans |= (1 << i);48 }49 else if(allone & (1 << i) && m >= (t | (1 << i))){50 ans |= (1 << i);51 t |= (1 << i);52 }53 }54 printf("%d\n", ans);55 return 0; 56 }