CF1451E - Codeforces Round 685 (Div. 2) E. Bitwise Queries

题目链接：E. Bitwise Queries

题意

这是一道交互题，分为两个版本 Easy 和 Hard 两者只在询问次数上不同。

给出一个长度为 $n$ 的非负整数序列 $a_1, a_2, \cdots, a_n$，并保证 $a_i \in [0, n-1]$ 和 $n=2^t$，你可以进行一下三种询问操作：

• AND i j：表示询问 $a_i \& a_j$（“与”操作）

• OR i j：表示询问 $a_i | a_j$（“或”操作）

• XOR i j：表示询问 $a_i \oplus a_j$（“异或”操作）

通过若干次询问，求出该序列。

本题分为两种难度 Easy 版允许询问 $n+2$ 次， Hard 版允许询问 $n+1$ 次。

数据范围：$n = 2^t, 2\leqslant t \leqslant 16$。

思路

有关位运算的恒等式请见 与位运算有关的恒等式，下文中的恒等式出自于此。

Easy版本

核心是使用恒等式：$a+b=(a\oplus b) + 2(a\& b)$。

先通过 $n-1$ 次询问，求出 $a_1\oplus a_2, a_1\oplus a_3, \cdots, a_1\oplus a_n$，然后再通过3次询问，求出 $a_1\& a_2, a_1\& a_3, a_2\& a_3$，一共 $n+2$ 次询问。

通过后三次询问和上面的恒等式，求出 $a+b, b+c, a+c$，进一步 $a=\frac{(a+b)+(a+c)-(b+c)}{2}$，于是可以求出 $a_1$，再通过异或运算求出其他所有元素。

时间复杂度 $O(n)$。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	int n;
	cin >> n;
	vi Xor(n+1);
	for (int i = 2; i <= n; i++) {
		cout << "XOR " << 1 << ' ' << i << '\n';
		cout.flush();
		cin >> Xor[i];
	}
	cout << "AND " << 1 << ' ' << 2 << '\n';
	cout << "AND " << 1 << ' ' << 3 << '\n';
	cout << "AND " << 2 << ' ' << 3 << '\n';
	cout.flush();
	int a, b, c;
	cin >> a >> b >> c;
	a = Xor[2] + 2 * a;
	b = Xor[3] + 2 * b;
	c = (Xor[2] ^ Xor[3]) + 2 * c;
	a = (a + b - c) / 2;
	cout << "! " << a << ' ';
	for (int i = 2; i <= n; i++) {
		cout << (Xor[i] ^ a) << ' ';
	}
	return 0;
}

Hard版本

第一步还是先通过 $n-1$ 次询问，求出来 $a_1\oplus a_2, a_1\oplus a_3, \cdots, a_1\oplus a_n$。

可以发现，easy版本连 $n=2^t$ 和 $a_i\in[0,n-1]$ 这俩条件都没有使用过。

于是我们通过分类思想来想如何使用第二个条件：

• 如果存在 $a_j=a_k$，则 $a_1\oplus a_j=a_1\oplus a_k$，于是 $a_j\& a_k = a_j = a_k$，所以可以通过1次询问求出来 $a_j$，于是通过异或我们又可以求出来 $a_1$，进一步求出其他所有数，总询问次数 $n-1+1=n$ 次。

• 如果不存在 $a_j=a_k$，则 $a_1\sim a_n$ 一定是均与分布在 $[0, n-1]$ 中，且两两不同，这时第一个条件就起作用了，那么一定存在 $a_1+a_j=n-1=2^k-1$，再细想 $2^k-1$ 是什么，它的二进制全部是1，于是 $a_1$ 和 $a_j$ 的二进制数位一定是错开的，也就是 $a_1 \& a_j = 0$，这不就正好凑成了 easy 版本的一个与条件么，于是在找到第三个值 $a_k$，通过询问两次 $a_1 \& a_k, a_j\& a_k$ 即可求出 $a_1$ 了！总询问次数 $n-1+2=n+1$。

第一种情况的 $a_1\oplus a_j=a_1\oplus a_k$ 可以通过 map 查找得到，时间复杂度 $O(n\log n)$。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	int n, zero;
	cin >> n;
	pii pi(-1, -1);
	vi Xor(n+1), ans(n+1);
	map<int, int> mp;
	for (int i = 2; i <= n; i++) {
		cout << "XOR " << 1 << ' ' << i << '\n';
		cout.flush();
		cin >> Xor[i];
		if (Xor[i] == n-1) zero = i;
		if (!mp.count(Xor[i])) mp[Xor[i]] = i;
		else {
			pi = mkp(i, mp[Xor[i]]);
		}
	}
	if (pi.first != -1) {
		int i = pi.first, j = pi.second;
		cout << "AND " << i << ' ' << j << '\n';
		cin >> ans[i];
		ans[1] = Xor[i] ^ ans[i];
	} else {
		int i = (2 == zero) ? 3 : 2;
		int a, b = 0, c;
		cout << "AND " << 1 << ' ' << i << '\n';
		cout << "AND " << i << ' ' << zero << '\n';
		cin >> a >> c;
		a = Xor[i] + 2 * a;
		b = Xor[zero];
		c = (Xor[i] ^ Xor[zero]) + 2 * c;
		a = (a + b - c) / 2;
		ans[1] = a;
	}
	cout << "! " << ans[1] << ' ';
	for (int i = 2; i <= n; i++) {
		ans[i] = ans[1] ^ Xor[i];
		cout << ans[i] << ' ';
	}
	return 0;
}