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) == 1 && n != 0){ s.clear(); for (int i = 0; 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 0; }
解法二：位异或
有离散数学可知，异或运算具有以下性质：
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) == 1 && n){ int ans = 0; for (int i = 0; i < n; ++i){ scanf("%d", &tmp); ans ^= tmp; } printf("%d\n", ans); } return 0; }
HDU 2095 find your present (2)
原文：http://www.cnblogs.com/tommychok/p/5154082.html
