题解 P1469 【找筷子】

这题对于初学OI的人是一道很有趣的题，让我们来看看吧！

解法1

• $n \le 10^5+1$

直接sort搞掉，看哪个数出现奇数次。

期望得分 $60$ 分。

解法2

• $n \le 10^7+1$

前置知识：位运算里的异或运算。

异或运算有一个性质，$a \operatorname{xor} a = 0$。

那么，我们可以把所有数都异或起来，这样子的结果即为出现奇数次的数。

期望得分 $ 80 \sim 100$ 分。

注意使用scanf以获得 $100$ 分。

代码

cpp

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;++i){
		int tmp;
//		cin>>tmp;
		scanf("%d",&tmp);
		ans^=tmp;
	}
//	cout<<ans;
	printf("%d",ans);
	return 0;
}