1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 100010; 4 typedef pair<string, int> PSI; 5 PSI a[N]; //存储n扇门的两个属性，first是操作方式，second是操作数 6 int n, m; 7 int cal(int bit, int now) { //返回用now和参数的第bit位进行n次运算之后的结果 8 for (int i = 0; i < n; i++) { 9 int x = a[i].second >> bit & 1; //x等于第i扇门操作数的第bit位上的数 10 //然后根据操作方式进行操作 11 if (a[i].first == "AND") { 12 now &= x; 13 } else if (a[i].first == "OR") { 14 now |= x; 15 } else { 16 now ^= x; 17 } 18 } 19 return now; 20 } 21 int main() { 22 cin >> n >> m; 23 for (int i = 0; i < n; i++) { //输入 24 string op; 25 int x; 26 cin >> op >> x; 27 a[i].first = op; 28 a[i].second = x; 29 } 30 int val = 0; //val用于判定该位放了1后是否超出了m 31 int ans = 0; //ans为最终答案 32 for (int bit = 29; bit >= 0; bit--) { //从高位到低位依次判断该位是放1还是放0 33 int res0 = cal(bit, 0); //res0存储第bit位填0后，又经过n次运算后的结果 34 int res1 = cal(bit, 1); //res1存储第bit位填1后，又经过n次运算后的结果 35 if (res0 >= res1) { //该位放0 36 ans += res0 << bit; 37 } else if ((res0 < res1) && (val + (1 << bit) <= m)) { //该位放1 38 ans += res1 << bit; 39 val += res1 << bit; 40 } 41 } 42 cout << ans << endl; 43 return 0; 44 }
注解：因为本题中 m 最大是 10 ^ 9，log2(10 ^ 9) = 3log2(10 ^ 3) < 3 * 10 = 30，所以每次 i 从 29 往后枚举就可以了