问题:
Description
There
is N pairs of balls in a small box. That means the number for each
pair is the same. However, for some reason, a ball is lost. Now, you
will get the number of the rest. Can you find the number of the lost
ball as fast as possible?
Input
The
input consists of several test cases. For each case, the first line
contains an integer N(1<= N <= 500000), the total number of
toys in the field. Then a line follow, which contains 2*N-1 numbers,
which will is positive and not exceed 2*10^9. The input is terminated
by N=0.
Output
For
each test case, print in one line the number of the lost ball.
Sample
Input
3
2
4 5 4 5
5
199
342 199 341 332 340 332 342 340
0
Sample
Output
2
341
思路:
对于如此多的输入数据(500000×2-1),进行全部存储是不可行的,部分存储也不现实,因为输入数据是随机顺序的。因此采用另一种思路,假设一种操作f,使得待求数xi = f(x1,x2,……xn)。加减乘除肯定不行,逻辑运算也不行,那么只剩下位运算,我们知道a^a(按位异或操作)=0,0^b=b,且按位异或满足交换律,那么,将所有输入数据按位进行异或操作,最后将得到待求数xi
代码:
#include <stdio.h>
int main(){
unsigned long int n,p,q;
while(1){
scanf("%d", &n);
if(n==0)
break;
p=0;
for(int i=0;i<2*n-1;i++){
scanf("%d",&q);
p=p^q;
}
printf("%d\n",p);
}
return 0;
}
分享到:
相关推荐
BOJ的题目1023. Ancient Keyboard解法 源代码
BOJ问题解决 week1:堆栈 第二周:基本BFS 第3周:BFS提前 第4周:DFS 第5周:回溯
boj 上08 09 年复试模拟题的答案
JAVA_BOJ
boj:算法
BOJ
Algorithm-BOJ.zip,BekJon在线法官(Java,Kotlin,SWIFT)和PS路线图,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-BOJ-PSJ.zip,Baykon在线判断JAVA问题解决方法(第二章),算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-BOJ-AutoCommit.zip,当您解决baekjoon online judge的问题时,它会自动提交并推送到远程存储库。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-boj-auto-submit.zip,日本央行cli提交脚本,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
资源分类:Python库 所属语言:Python 资源全名:boj-0.0.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
解决问题 Boj.kr
通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的,全数字化且可重复使用的着色书,可用于 通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的全数字可重复使用的图画书,专为孩子,父母...
BOJ:日本央行
boj:算法求解