a^b

知识点：快速幂

64位整数乘法

知识点：快速加

最短Hamilton路径

知识点：二进制状态压缩

起床困难综合征

知识点：二进制位运算的独立性，贪心

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
  4. #define per(i,j,k) for(int i=int(j);i>=int(k);i--)
  5. typedef long long ll;
  6. const int N = 100010;
  7. int n, m;
  8. char op[N][5];
  9. int t[N];
  10. int get(int pos, int val) {
  11.     rep(i,1,n) {
  12.         switch (op[i][0])
  13.         {
  14.         case 'A':
  15.             val &= t[i] >> pos & 1; break;
  16.         case 'O':
  17.             val |= t[i] >> pos & 1; break;
  18.         case 'X':
  19.             val ^= t[i] >> pos & 1; break;
  20.         }
  21.     }
  22.     return val;
  23. }
  24. int main(){
  25.     scanf("%d%d", &n, &m);
  26.     rep(i,1,n) scanf("%s%d", op[i], &t[i]);
  27.     int rs = 0, x = 0;
  28.     per(i,30,0) {
  29.         int r0 = get(i, 0), r1 = get(i, 1);
  30.         if(r0 == 1) {
  31.             rs += 1 << i;
  32.         } else if(r1 == 1 && x + (1 << i) <= m) {
  33.             rs += 1 << i;
  34.             x += 1 << i;
  35.         }
  36.     }
  37.     printf("%d\n", rs);
  38. }