NYOJ528 找球号(三)位运算

时间:2021-12-02 07:09:59

找球号(三)

时间限制: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是非常有必要的!