HDU 2095 find your present (2)
解法一：使用set
利用set，由于只有一个为奇数次，对一个数进行查询，不在集合中则插入，在集合中则删除，最后剩下的就是结果
/* HDU 2095 find your present (2) --- 水题 */
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std; int main()
{
#ifdef _LOCAL
freopen("D:\\input.txt","r", stdin);
#endif
int n,tmp; set<int> s;
while (scanf("%d", &n) == && n != ){
s.clear();
for (int i = ; i < n; ++i){
scanf("%d", &tmp);
if (s.find(tmp) == s.end())
s.insert(tmp);
else
s.erase(tmp);
}
printf("%d\n", *s.begin());
} return ;
}
解法二：位异或
有离散数学可知，异或运算具有以下性质：
1.a^b = b^a; //交换律
2.(a^b)^c = a^(b^c); //结合律
3.a^b^a = b; a^b^b = a;
4.0^n = n;
5.n^n=0;
因此将这n个数对0进行n次异或得到的结果即为想要的结果。
/* HDU 2095 find your present (2) --- 位异或 */
#include <cstdio> int main()
{
#ifdef _LOCAL
freopen("D:\\input.txt", "r", stdin);
#endif
int n, tmp;
while (scanf("%d", &n) == && n){
int ans = ;
for (int i = ; i < n; ++i){
scanf("%d", &tmp);
ans ^= tmp;
}
printf("%d\n", ans);
} return ;
}