题目链接:http://acm.zzuli.edu.cn/problem.php?id=1519
时间限制: 2 Sec  内存限制: 16 MB

题目描述

小P最近人生得意，去参加了一次相亲大会，相亲大会上每个人有一个密码牌（密码牌上的密码是一个正整数m，m<231 ），相互之间在交流之前先交换密码牌，密码牌上的密码可能相同，也可能不同，如果相同，两人牵手离开，如果不保同，各自再寻找下一位，保证最后只有1个人或2个人留下来。

输入

第一行两个数 n,k (n≤3000000,1≤k≤2)，n表示参加相亲大会的人数，接下来 n行每行一个正整数表示相亲大会上每一个人的密码，k表示最后留在相亲大会的人数。

输出

从小到大输出一行 k个数，表示相亲不成功留在相亲大会人的密码，中间用空格分隔。

样例输入

3 1
2
2
2

样例输出

2

提示

对于40%的数据，保证 k=1。
对于20%的数据，保证n≤100
对于100%的数据，保证 n≤3000000，ai<2^31。

解题思路

因为数据太大我们不能用一般的方法，这道题其实就是在一堆数中找出k个出现奇数次的数，其余都出现偶数次。解析详见https://blog.csdn.net/lzyws739307453/article/details/88133245

#include <iostream>
int n, arr[3000005];
void FindNum(int len, int k) {
    int s = 0;
    for (int i = 0; i < len; i++)
        s ^= arr[i];
    if (k == 1) {
        printf("%d\n", s);
        return ;
    }
    int s1 = s, s2 = s, m = 0;
    while (!(s1 & 1)) {
        s1 >>= 1;
        m++;
    }
    for (int i = 0; i < len; i++)
        if ((arr[i] >> m) & 1)
            s ^= arr[i];
    if (s < s ^ s2)
        printf("%d %d\n", s, s ^ s2);
    else printf("%d %d\n", s ^ s2, s);
}
int main() {
    int n, k;
    while (~scanf("%d%d", &n, &k)) {
        for (int i = 0; i < n; i++)
            scanf("%d", &arr[i]);
        FindNum(n, k);
    }
    return 0;
}