位运算的主要特点之一是在二进制表示下不进位，正因如此，在 $_math_inline$x_0$math_inline_$ 可以任意选择的情况下，参与位运算的各个位(bit)之间是独立无关的。对于任意的 $_math_inline$k(0\leq k \leq 30)$math_inline_$ ，“ans 的 k 位是几” 只与 “ $_math_inline$x_0$math_inline_$ 的第 k 位是几” 有关，与其他位无关，所以我们可以从高位到低位，依次考虑 $_math_inline$x_0$math_inline_$ 的每一位填 0 还是填 1。
$_math_inline$x_0$math_inline_$ 的第 k 位填 1，当且仅当同时满足以下两个条件：
- 已经填好的更高位构成的数值加上
1 << k以后不超过 m。 - 用每个参数的第 k 位参与位运算。若初值为 1，则 n 次运算后结果为 1，若初值为 0， 则 n 次运算后结果为 0。（若不管初值为 1 或 0，运算后的结果同时为 0 或 1，则填 0 更优，因为可以给后面的位留更大的选择空间）。
Code
Code my
1#include <bits/stdc++.h>
2
3using namespace std;
4
5typedef enum{
6 AND = 1, OR = 2, XOR = 3
7} Bit;
8
9vector<pair<Bit, int>> ops;
10
11Bit get(const string& s){
12 if(s[0] == 'A') return AND;
13 else if(s[0] == 'O') return OR;
14 else return XOR;
15}
16
17bool sol(int k, bool set){
18 for(auto &i : ops){
19 switch(i.first){
20 case AND:
21 set &= i.second >> k & 1;
22 break;
23 case OR:
24 set |= i.second >> k & 1;
25 break;
26 case XOR:
27 set ^= i.second >> k & 1;
28 }
29 }
30 return set;
31}
32
33int main(){
34 int n, m;
35 cin >> n >> m;
36 string op;
37 int opi;
38 for(int i = 0; i < n; ++i){
39 cin >> op >> opi;
40 ops.emplace_back(get(op), opi);
41 }
42 unsigned int num = 0, res = 0;
43 for(int i = 30; i >= 0; --i){
44 if(sol(i, 0)) res |= 1<<i;
45 else if((num | (1 << i)) <= m && sol(i, 1)) res |= (1 << i), num |= (1 << i);
46 }
47 cout << res << endl;
48}
Code 1
1#include<iostream>
2#include<cstdio>
3#include<cstring>
4#include<algorithm>
5#include<string>
6using namespace std;
7int n, m;
8pair<string, int> a[100005];
9
10int calc(int bit, int now) {
11 for (int i = 1; i <= n; i++) {
12 int x = a[i].second >> bit & 1;
13 if (a[i].first == "AND") now &= x;
14 else if (a[i].first == "OR") now |= x;
15 else now ^= x;
16 }
17 return now;
18}
19
20int main() {
21 cin >> n >> m;
22 for (int i = 1; i <= n; i++) {
23 char str[5];
24 int x;
25 scanf("%s%d", str, &x);
26 a[i] = make_pair(str, x);
27 }
28 int val = 0, ans = 0;
29 for (int bit = 29; bit >= 0; bit--) {
30 int res0 = calc(bit, 0);
31 int res1 = calc(bit, 1);
32 if (val + (1 << bit) <= m && res0 < res1)
33 val += 1 << bit, ans += res1 << bit;
34 else
35 ans += res0 << bit;
36 }
37 cout << ans << endl;
38}
Code 2
1#include <cstdio>
2
3const int MAXN = 100000;
4const int MAXM = 1e9;
5
6enum OperatorType {
7 And = 0, Or = 1, Xor = 2
8};
9
10struct BitwiseOperator {
11 OperatorType type;
12 bool bits[32];
13} ops[MAXN];
14
15int n;
16unsigned int m;
17
18inline bool check(const int k, const bool value) {
19 bool flag = value;
20 for (int i = 0; i < n; i++) {
21 if (ops[i].type == And) flag &= ops[i].bits[k];
22 else if (ops[i].type == Or) flag |= ops[i].bits[k];
23 else if (ops[i].type == Xor) flag ^= ops[i].bits[k];
24 }
25
26 return flag;
27}
28
29inline unsigned int solve() {
30 unsigned int num = 0, ans = 0;
31 for (int i = 32 - 1; i >= 0; i--) {
32 if (check(i, 0)) ans |= (1 << i);
33 else if ((num | (1 << i)) <= m && check(i, 1)) ans |= (1 << i), num |= (1 << i);
34 }
35
36 return ans;
37}
38
39int main() {
40 // freopen("sleep.in", "r", stdin);
41 // freopen("sleep.out", "w", stdout);
42
43 scanf("%d %u", &n, &m);
44
45 for (int i = 0; i < n; i++) {
46 BitwiseOperator &op = ops[i];
47 char str[sizeof("AND")];
48 int x;
49 scanf("%s %d", str, &x);
50 if (str[0] == 'A') op.type = And;
51 else if (str[0] == 'O') op.type = Or;
52 else if (str[0] == 'X') op.type = Xor;
53
54 for (int i = 0; i < 32; i++) op.bits[i] = ((x & (1 << i)) == 0) ? false : true;
55 // for (int i = 0; i < 32; i++) putchar(op.bits[i] ? '1' : '0');
56 // putchar('\n');
57 }
58
59 printf("%u\n", solve());
60
61
62 return 0;
63}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。