警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「Codeforces 879C」Short Program - 位运算

题意

传送门:Codeforces 879C

给一串位运算操作(包含| & ^,每个操作数均落在\(。\)中),将其简化到5次运算以内并输出。

解法

过程

考虑交换律和结合律。显然1|1^1$$1^1|1。所以要换一种思路。

我们可以将\(1023\)\(0\)同时进行运算。

再考虑将& | ^三种运算转化为| ^两种。

如将\(1023\)\(0\)带入以下运算:

1
2
3
4
5
6
7
8
9
10
11
10     1111111111 0000000000
^ 218 0011011010 1100100101
& 150 0010010010 0000000100
| 935 1110110111 1110100111
& 61 0000110101 0000100101
| 588 1001111101 1001101101
& 897 1000000001 1000000001
| 411 1110011011 1110011011
| 584 1111011011 1111011011
^ 800 0011111011 0011111011
| 704 1011111011 1011111011

使用| ^代替& | ^的方法:

  • 置零,使用|1^1
  • 置一,使用|1^0
  • 不变,使用|0^0
  • 反转,使用|0^1

\(1023\ or\ x\ xor\ y=a=763\)\(0\ or\ x\ xor\ y=b=763\)

即如果\(a\)\(b\)某一位一样,\(x\)的那一位就是1,\(y\)的那一位就是\(b\)那一位的反码。

如果不一样,\(x\)的那一位就是\(0\)\(y\)的那一位也是\(b\)那一位的反码。

两数每一位相同得\(1\),不同得\(0\),就是\(a\ xor\ b\ xor\ 1023\)的值。

\(b\)的反码即\(b\ xor\ 1023\)

结论

\(x = a\ xor\ b\ xor\ 1023\)

\(y = b\ xor\ 1023\)

\(O(n)\)边读边算\(a\)\(b\),最后\(O(1)\)\(x\)\(y\)即可。

代码

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
#include <bits/stdc++.h>
#define p(q) ((q) && (q) != X)
#define X 0x3f3f3f3f
using namespace std;

int a = 0, b = 1023;
char op[1];
int n, t;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s%d", op, &t);
switch (*op) {
case '&':
a &= t;
b &= t;
break;
case '|':
a |= t;
b |= t;
break;
case '^':
a ^= t;
b ^= t;
break;
}
}
printf("2\n| %d\n^ %d", a ^ b ^ 1023, b ^ 1023);
}

拓展

位运算+构造算法(bitmasks+constructive algorithms)的题目的几种思考方式:

  • 对每一位考虑(位运算都是隔离每位的,不存在借位进位这种影响其它位的运算)
  • 对逆运算考虑(如1216-D,前缀和转为差分)
  • 对结果考虑(结果反向构造过程)