自动搬运

查看原文

来自洛谷，原作者为

	t162 No more memories, no more silent tears. No more gazing across the wasted years.

搬运于2025-08-24 21:25:26，当前版本为作者最后更新于2020-05-16 21:27:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们考虑异或的两个小小的性质：

1. $k$ 个相同的数的异或和，当 $k$ 为奇数时，结果是这个数本身，否则结果是 $0$。
2. 任何数与 $0$ 的异或值是它本身。

然后注意到题目。题目需要求 $n$ 个数中出现奇数次的那个数，且保证这个数存在且只有一个。于是我们根据上面两个性质得出，答案就是这 $n$ 个数的异或和。

原理：

根据性质1，成对的筷子异或后就变成 $0$ 了，只剩下落单的那一根。把这些 $0$ 和落单的那一根的长度异或起来，根据性质2，结果显然就是落单的那一根的长度。

代码如下：

#include<cstdio>
int x,n,ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&x),ans^=x;
    printf("%d\n",ans);
}