Codeforces Round #440 D. Something with XOR Queries(交互|异或)

原题连接：http://codeforces.com/contest/872/problem/D

题目大意：交互题，要求在2n次询问后，得出隐藏的数列

思路：2n次询问是关键点，因为我们只能获取异或相关的信息，所以就要枚举首位取值p0，然后如果根据首位推出其他pi呢，由于我们只能获取异或相关的信息，所以我们可以考虑pi = pi^p0 ^p0 ,那pi^p0怎么获得呢？这就是我们2n次询问要获得的信息的一部分，我们可以获取所有的p0^bi,以及b0^pi ，那么p0^pi = p0 ^ b0 ^ b0^pi

最后我们获得了一个数列后就要检查是否合法了,我们首先构造一个新的位置数组bb[p[i]]= i,然后检查bb[i]^p[0] 是否等于b[i]^p[0]

AC代码：

#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;

int p[MAXN], b[MAXN], n, a[MAXN], aa[MAXN], bb[MAXN], res[MAXN];

bool check(int x) {
	a[0] = x;
	for (int i = 1; i < n; i++)
		if ((a[i] = a[0] ^ p[i]) >= n)
			return false;
	for (int i = 0; i < n; i++) bb[a[i]] = i;
	for (int i = 0; i < n; i++) {
		if ((bb[i] ^ a[0]) != b[i]) {
			return false;
		}
	}
	return true;
}
int main() {
	int ans = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		printf("? 0 %d\n", i);
		fflush(stdout);
		scanf("%d", &b[i]);
	}
	for (int i = 0; i < n; i++) {
		printf("? %d 0\n", i);
		fflush(stdout);
		scanf("%d", &p[i]);
		p[i] = p[i] ^ b[0];
	}
	for (int i = 0; i < n; i++) {
		if (check(i)) {
			ans++;
			if (ans == 1) {
				for (int j = 0; j < n; j++)res[j] = a[j];
			}
		}
	}
	printf("!\n%d\n%d", ans, res[0]);
	for (int i = 1; i < n; i++) {
		printf(" %d", res[i]);
	}
	printf("\n");
	return 0;
}