P8
二进制下没有进位,所以每一位的操作都是独立的。
所以,我们从高到低枚举每一位填0还是1,分别计算填0和1的答案,如果填1的答案小于等于填0的答案,那么这一位填0就是最优的,否则就填1。同时要保证该位填1后的值要小于等于m。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e5+5;
pair<string, int> op[maxn];
int n, m;
int cal(int bit, int now) {
int res = now;
for (int i = 1; i <= n; i++) {
int x = (op[i].second >> bit) & 1;
if (op[i].first == "AND") res &= x;
else if (op[i].first == "OR") res |= x;
else res ^= x;
}
return res;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
string s;
int x;
cin >> s >> x;
op[i] = {s, x};
}
int ans = 0;
int val = 0;
for (int i = 29; i >= 0; i--) {
int res0 = cal(i, 0);
int res1 = cal(i, 1);
if (val + (1 << i) <= m && res0 < res1) {
ans += res1 << i;
val += 1 << i;
} else {
ans += res0 << i;
}
}
cout << ans << "\n";
}