原题：http://www.fjutacm.com/Problem.jsp?pid=3678
这个题有两种情况一种是只有一个出现了奇数次很简单直接异或就可以了，另一种是两个出现了奇数次，重点就说这个。
就先按照只有一个的思路全部异或然后剩下的那个数字是a,b（两个出现了奇数次的数）异或的值x，找到其中一个就能找到另外一个，所以就找不同就行了，他俩不同的地方就在于，他俩的二进制一定存在一位不同，这一位异或的值一定是一，所以找到这一位就可以了，我是从最低位开始找，找到这一位就标记一下，然后把输入的数，只要这一位是1的全部跟这个x再异或一次，出现偶数次的会抵消，没有抵消的一定是出现了奇数次的而且这一位是1的，那么剩下的那个值就是出现了奇数次且这一位是0的，答案就出来了。
代码：
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<stdio.h>
#include<algorithm>
using namespace std;
int a[3000010];
int main(){
int n,m,x,ans=0,ans1=0,ans2=0;
while(~scanf("%d %d",&n,&m)){
ans=0,ans1=0,ans2=0;
int vis;
if(m==1){
while(n--){
scanf("%d",&x);
ans^=x;
}
printf("%d\n",ans);
}
else{
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
ans^=a[i];
}
for(int i=0;i<40;i++){
if(ans&(1<<i)){
vis=i;
break;
}
}
ans1=ans;
for(int i=0;i<n;i++){
if(a[i]&(1<<vis)){
ans^=a[i];
}
}
ans2=ans;
ans1=ans1^ans2;
if(ans1>ans2)swap(ans1,ans2);
printf("%d %d\n",ans1,ans2);
}
}
return 0;
}
|
