CF1698A XOR Mixup 题解

题意简述

给定 $n-1$ 个数，其中有 $n-1$ 个数属于数列 $a$，剩下一个数为 $x$。

$x$ 为 $a_1 \oplus a_2 \oplus \cdot \cdot \cdot \oplus a_{n-1}$（$\oplus $ 表示异或）。

请求出 $x$ 的值（输出其中一个）。

解题思路

我们根据题意可以按如下推导：

$a_1 \oplus a_2 \oplus \cdot \cdot \cdot \oplus a_{n-1} \oplus x$

$(a_1 \oplus a_2 \oplus \cdot \cdot \cdot \oplus a_{n-1}) \oplus x$

$(a_1 \oplus a_2 \oplus \cdot \cdot \cdot \oplus a_{n-1}) \oplus (a_1 \oplus a_2 \oplus \cdot \cdot \cdot \oplus a_{n-1})$

$\therefore a_1 \oplus a_2 \oplus \cdot \cdot \cdot \oplus a_{n-1} \oplus x = 0$

所以这 $n$ 个数中间任意一个数都可以是 $x$。这里我用了 rand() 来做，所以要用 srand(time(NULL)) 初始化一下。

代码实现

#include<bits/stdc++.h>
using namespace std;
int t,n,a[1000005];
int main() {
	scanf("%d",&t);
	while(t--) {
		scanf("%d",&n); srand(time(NULL));
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		printf("%d\n",a[rand()%n]);
	}
	return 0;
}
//code by TheCedar