题解 P1469 【找筷子】

t162 · 2020-05-16 21:27:03 · 题解

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

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);
}