找球号（三）
时间限制：2000 ms | 内存限制：3000 KB难度：2
- 描述
xiaod现在正在某个球场负责网球的管理工作。为了方便管理，他把每个球都编了号，且每个编号的球的总个数都是偶数。有一天，xiaod发现少了一个球，你能帮他找出丢的那个球的球号吗？
- 输入
-
有多组测试数据。每组数据包括两行。第一行是一个整数N(0<N<1000000),表示现在所剩的球数。随后的一行是N个数，表示所剩的各个球的编号M(0<M<10^9)。
- 输出
-
对于每组数据，输出弄丢的那个球的球号。
- 样例输入
-
5
1 1 3 6 6
3
1 2 1 - 样例输出
-
3
2
这个题用位运算就非常简单了，前提是首先熟悉位运算，这里用到一个异或运算，也就是 ^ 这个符号，他的运算规则是：相同为0，不同为1。知道了这个之后，就容易想到相同的两个数异或之后为0，所以下面很关键的一步，也是我想了好久也没想起来的一步，就是把所有的数都异或一遍，那么最后剩下的一定是那个一个的，还有一点需要注意就是任何数和0进行异或运算都还是他本身。下面是代码：
#include <iostream>
#include <cstdio> using namespace std; int main()
{
int n;
while (~scanf("%d", &n))
{
int ans = ;//初始化条件
int t;
for (int i = ; i < n; i++)
{
scanf("%d", &t);
ans ^= t;//异或运算
}
printf("%d\n", ans); }
return ;
}
还有一个从网上看的STL的代码如下：
#include <iostream>
#include <cstdio>
#include <set>
using namespace std; int main()
{
int n;
while (~scanf("%d", &n))
{
set<int> S;
int t;
for (int i = ; i < n; i++)
{
scanf("%d", &t);
if (S.find(t) == S.end())
S.insert(t);
else
S.erase(t);
}
printf("%d\n", *S.begin());
}
return ;
}
虽然是STL代码时间比较长，但是这也是一种不错的方法，灵活运用STL对ACM是非常有必要的！