题解 P1469 【找筷子】
t162
2020-05-16 21:27:03
我们考虑异或的两个小小的性质:
1. $k$ 个相同的数的异或和,当 $k$ 为奇数时,结果是这个数本身,否则结果是 $0$。
2. 任何数与 $0$ 的异或值是它本身。
然后注意到题目。题目需要求 $n$ 个数中出现奇数次的那个数,且保证这个数存在且只有一个。于是我们根据上面两个性质得出,答案就是这 $n$ 个数的异或和。
原理:
根据性质1,成对的筷子异或后就变成 $0$ 了,只剩下落单的那一根。把这些 $0$ 和落单的那一根的长度异或起来,根据性质2,结果显然就是落单的那一根的长度。
代码如下:
```cpp
#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);
}
```