题目大意
n 个数的数组,其中恰好有 k 个数出现了奇数次。把他们找出来。
n<=3e6, k<=2
空间 2M
这真是个有趣的问题
![](/images/huaji.png)
题解
k=1 直接全部异或起来。
k=2 ,假设出现奇数次的是 a 和 b,那么把所有数异或起来得到的就是 s=a^b。
对每个二进制位维护一个数 w[i],当读入一个 x,x 的第 j 位为 1 的时候,就把 w[j]^=x。
对于 s 的最高位的 1,那么一定是 a 和 b 之中,一个这一位为 1,一个这一位为 0。假设是第 j 位,那么 w[j] 肯定就是其中一个数。
代码
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
| #include<cstdio> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std;
int n,k,xsum,xw[35];
int main() { scanf("%d %d",&n,&k); fo(i,1,n) { int x; scanf("%d",&x); xsum^=x; fo(j,0,31) if (x&(1<<j)) xw[j]^=x; } if (k==1) printf("%d\n",xsum); else { fd(j,31,0) if (xsum&(1<<j)) { int x=xw[j], y=xsum^xw[j]; if (x>y) swap(x,y); printf("%d %d\n",x,y); break; } } }
|