Codeforces 879C(Xor+构造)

Codeforces 879C
题意:给出一些位运算操作,求简化位运算。
可以发现所有操作都可以用三大操作完成。
那么假设输入二进制数全是0($a$代表的数)或者全是1($b$代表的数)
那么根据题目模拟一次,最后得到了处理的结果
那么可以得到,原二进制数上如果是0或者1,之后的结果有几种情况考虑:
1、这一位原来为0时变成了0,原来为1时变成了0:进行$and 1$可以完成
2、这一位原来为0时变成了1,原来为1时变成了0:进行$xor 1$可以完成
3、这一位原来为0时变成了0,原来为1时变成了1:不用进行
4、这一位原来为0时变成了1,原来为1时变成了1:进行$or 1$可以完成
(代码注释有对应情况,可以参照)
之后再一起操作就行了

Codeforces Submission

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
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
int n;
void clean() {}
void solve() {
clean();
int a = 0, b = 1023;
for (int x, i = 1; i <= n; i++) {
char s[5]; scanf("%s %d", s, &x);
switch (s[0]) {
case '^' : a ^= x, b ^= x; break;
case '|' : a |= x, b |= x; break;
case '&' : a &= x, b &= x; break;
}
}
int A = 1023, X = 0, O = 0, bs = 1;
for (int i = 0; i < 10; i++) {
int taki = a & 1, mitsuha = b & 1;
if (taki == 0) {
if (mitsuha == 0) A -= bs;//1
if (mitsuha == 1) ;//3
} else if (taki == 1) {
if (mitsuha == 0) X += bs;//2
if (mitsuha == 1) O += bs;//4
}
a >>= 1, b >>= 1, bs <<= 1;
}
printf("3\n| %d\n^ %d\n& %d\n", O, X, A);
}
int main() {
scanf("%d", &n), solve();
return 0;
}

------ 本文结束 ------