http://uoj.ac/problem/2
题意：有 n 个关卡，主角手里有一个数 k 未定，且 k≤m ，每关都有一种操作，与/或/异或 t 。问最终主角手里的数最大是多少。
bitset
每一位只会是0或1，而每一位经过的操作是已知的，所以只要把0和1经过一系列操作后的结果模拟出来，就能判断初始时这一位应该是0还是1.
如果0最终变成1，则显然这一位是要加入答案里的，而原始的k也只要在这一位取0即可。
如果1变成1，为了答案最大，也是要取的，但是这时要判断是否会使得原始的k超过m，因此要从高向低位遍历，这样遇到能加的就直接加上。
如果最终变成了0，显然不需要处理了。
由于bitset位运算能快64倍，所以用bitset优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
ll n, m, t;
bitset<40>no, all;
char op[maxn];
ll ans;
int main() {
cin >> n >> m;
no.reset(); all.set();
while (n--) {
scanf("%s%lld", op, &t);
if (op[0] == 'A')
no &= t, all &= t;
else if (op[0] == 'O')
no |= t, all |= t;
else
no ^= t, all ^= t;
}
for (int i = 31; i >= 0; i--) {
if (no[i])ans |= (1ll << i);
else if (all[i] && m >= (1ll << i)) {
ans |= (1ll << i);
m -= (1 << i);
}
}
cout << ans << endl;
return 0;
}
|
