Codeforces 1451E1 Bitwise Queries (Easy Version) 题解

题目链接：Codeforces 1451E1 Bitwise Queries (Easy Version)

---

第五题 Bitwise Queries (Easy Version) 题解

第 7 组 - 2020 年 4 月 28 日

题目大意

题目有一个长度为 \(n\,(n\leq 2 ^ {16})\) 的隐藏数组，每次可以向题目询问任意两个位置 \(i\) 和 \(j\) （但 \(i\neq j\) ）的两个数的位与、位或和异或，最多问 \(n+2\) 次。

题解

自然的思路一定是尽可能确定下一个数 \(a\) ，假设已经确定了 \(a\) ，则其他的数都可以通过一次异或询问得到：\(a \text{ ^ } (a \text{ ^ } b) = b\) .

在此有补充的公式：\[a+b=a \text{ ^ } b + 2\times(a \text{ & } b)\]

于是我们实际上可以得到其中任意三个数的值：

1. 询问 \(a \text{ & } b\)，\(b \text{ & } c\)，\(a \text{ & } c\)
2. 询问 \(a \text{ ^ } b\)，\(b \text{ ^ } c\)，然后本地计算得到 \(a \text{ ^ } c\)
3. 利用上面的公式得到 \(a+b\)，\(b+c\)，\(a+c\)，之后得到 \(a+b+c\)，自然可以得到每个数的值

得到这三个数的值后，便可由异或询问得到所有值了，一共询问了\(n+2\)次。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 16) + 5;

int n, _xor[N], A[N];
int a, b, c;
int ab, bc, ac;
int xab, xbc, xac;
int _ab, _bc, _ac;

int main() {
	scanf("%d", &n);
	printf("AND 1 2\n"), fflush(stdout), scanf("%d", &_ab);
	printf("AND 2 3\n"), fflush(stdout), scanf("%d", &_bc);
	printf("AND 1 3\n"), fflush(stdout), scanf("%d", &_ac);
	printf("XOR 1 2\n"), fflush(stdout), scanf("%d", &xab);
	printf("XOR 2 3\n"), fflush(stdout), scanf("%d", &xbc);
	xac = xab ^ xbc;
	ab = xab + (_ab << 1);
	bc = xbc + (_bc << 1);
	ac = xac + (_ac << 1);
	int s = (ab + bc + ac) / 2;
	a = s - bc,  b = s - ac, c = s - ab;
	A[1] = a, A[2] = b, A[3] = c;
	for (int i = 4; i <= n; i++) {
		printf("XOR 1 %d\n", i), fflush(stdout), scanf("%d", &_xor[i]);
		A[i] = _xor[i] ^ a;
	}
	printf("! ");
	for (int i = 1; i <= n; i++) printf("%d ", A[i]);
	printf("\n"), fflush(stdout);
	return 0;
}