阅读题目，有这句话：这些筷子中只有一只筷子是落单的，其余都成双。因此我们由这句话可以受到一些启发。再看题目的内存限制，只有 4MB，所以对空间有了很大的要求。
根据题意，我们需要找到落单的筷子，那么如何进行成双的配对呢？很简单，就是异或。两个相同的数 x^x 的值一定为 $0$。所以我们只需要从 $1$ 至 $n$ 扫一遍，进行异或 ans ^= x。若第 $x$ 个数的长度已经配对，那么这个数将与之前的某个数得到 $0$ 的结果，则最后 ans 的值也就是落单的筷子的长度了。
注意：数据读入对程序效率造成的影响！ 因此我们在程序设计时使用快读，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <iostream>
#include <cstdio>
using namespace std;
inline int read();
int main()
{
int n,x,ans = 0;
n = read();
for(register int i = 1;i <= n;++i) x = read(),ans ^= x;
printf("%d\n",ans);
return 0;
}
inline int read()
{
long long s = 0,f = 1;
char ch = getchar();
while((ch < '0' || ch > '9') && ch != EOF)
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
|
