解：m = 0的部分分，直接模拟。有and 0的部分分，直接模拟。<=1000的部分分，枚举攻击力之后模拟。所有操作相同的部分分，可以合并成只有一个操作。然后枚举m或者逐位贪心。
正解是逐位贪心，内层跑一遍1~n个操作。然后后面这个1~n其实可以优化，在外层用00000...0和11111...1来一次性搞完即可。
1 #include <bits/stdc++.h> 2 3 const int N = 100010; 4 5 int a[N], opt[N], n, m; 6 char str[5]; /// 0 AND & 1 OR | 2 XOR ^ 7 8 namespace m0 { 9 inline void solve() { 10 int ans = 0; 11 for(int i = 1; i <= n; i++) { 12 if(opt[i] == 0) { 13 ans = ans & a[i]; 14 } 15 else if(opt[i] == 1) { 16 ans = ans | a[i]; 17 } 18 else if(opt[i] == 2) { 19 ans = ans ^ a[i]; 20 } 21 } 22 printf("%d ", ans); 23 return; 24 } 25 } 26 27 namespace bf { 28 inline void solve() { 29 int ans = 0; 30 for(int i = 0; i <= m; i++) { 31 int x = i; 32 for(int j = 1; j <= n; j++) { 33 if(opt[j] == 0) { 34 x = x & a[j]; 35 } 36 else if(opt[j] == 1) { 37 x = x | a[j]; 38 } 39 else { 40 x = x ^ a[j]; 41 } 42 } 43 ans = std::max(ans, x); 44 } 45 printf("%d ", ans); 46 return; 47 } 48 } 49 50 namespace same { 51 inline void solve() { 52 int x = a[1]; 53 for(int i = 2; i <= n; i++) { 54 if(opt[i] == 0) { 55 x = x & a[i]; 56 } 57 else if(opt[i] == 1) { 58 x = x | a[i]; 59 } 60 else { 61 x = x ^ a[i]; 62 } 63 } 64 int ans = 0; 65 if(m <= 100000) { 66 for(int i = 0; i <= m; i++) { 67 if(opt[1] == 0) { 68 ans = std::max(ans, i & x); 69 } 70 else if(opt[1] == 1) { 71 ans = std::max(ans, i | x); 72 } 73 else if(opt[1] == 2) { 74 ans = std::max(ans, i ^ x); 75 } 76 } 77 } 78 else { 79 int now = 0; 80 for(int i = 29; i >= 0; i--) { 81 if(opt[1] == 0) { 82 if(((x >> i) & 1) && (now | (1 << i)) <= m) { 83 now |= (1 << i); 84 } 85 } 86 else if(opt[1] == 1) { 87 if(((x >> i) & 1) == 0 && (now | (1 << i)) <= m) { 88 now |= (1 << i); 89 } 90 } 91 else { 92 if(((x >> i) & 1) == 0 && (now | (1 << i)) <= m) { 93 now |= (1 << i); 94 } 95 } 96 } 97 if(opt[1] == 0) { 98 ans = x & now; 99 } 100 else if(opt[1] == 1) { 101 ans = x | now; 102 } 103 else { 104 ans = x ^ now; 105 } 106 } 107 printf("%d ", ans); 108 return; 109 } 110 } 111 112 int main() { 113 bool flag1 = false, flag2 = true; 114 scanf("%d%d", &n, &m); 115 for(int i = 1; i <= n; i++) { 116 scanf("%s%d", str, &a[i]); 117 if(str[0] == 'O') opt[i] = 1; 118 else if(str[0] == 'X') opt[i] = 2; 119 else if(a[i] == 0) { 120 flag1 = true; 121 } 122 if(i > 1 && opt[i] != opt[i - 1]) { 123 flag2 = false; 124 } 125 } 126 127 if(!m || flag1) { 128 m0::solve(); 129 return 0; 130 } 131 if(n <= 1000 && m <= 1000) { 132 bf::solve(); 133 return 0; 134 } 135 if(flag2) { 136 same::solve(); 137 return 0; 138 } 139 140 int ans = 0, now = 0; 141 for(int i = 29; i >= 0; i--) { 142 int t1 = 1, t0 = 0; 143 for(int j = 1; j <= n; j++) { 144 if(opt[j] == 0) { 145 t0 &= (a[j] >> i) & 1; 146 t1 &= (a[j] >> i) & 1; 147 } 148 else if(opt[j] == 1) { 149 t0 |= (a[j] >> i) & 1; 150 t1 |= (a[j] >> i) & 1; 151 } 152 else { 153 t0 ^= (a[j] >> i) & 1; 154 t1 ^= (a[j] >> i) & 1; 155 } 156 } 157 if(t0) { 158 ans |= (1 << i); 159 } 160 else if(t1 && (now | (1 << i)) <= m) { 161 now |= (1 << i); 162 ans |= (1 << i); 163 } 164 } 165 printf("%d ", ans); 166 return 0; 167 }