找球号(三)
时间限制: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是非常有必要的!