【LOJ6087】毒瘤题 题解

题目大意

  n 个数的数组，其中恰好有 k 个数出现了奇数次。把他们找出来。
  n<=3e6， k<=2
  空间 2M

这真是个有趣的问题

题解

  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] 肯定就是其中一个数。

代码

#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;
			}
		}
}