题解

Difficulty：3.9 / Easy

Tag：-

5min 秒的。

首先回顾经典问题，如果只有一个出现恰好一次可以怎么做？

注意到异或可以完美解决这个问题。因为在任何时候，异或两次相同的数答案都会不变。所以最后的结果就是只出现一次的数。

现在考虑这个问题。显然把所有异或的结果是 $x\oplus y$，怎么通过这个求出 $x$ 和 $y$ 呢？

考虑第 $3\sim 5$ 个点这个部分分。

我们发现，如果把奇数分为一组，偶数分为一组，那么两组就分别有 $x$ 或 $y$ 出现一次，其它的数也在这两组之一出现两次。此时将两组分别取异或，得到的结果就分别是 $x,y$。

然后注意到若 $x,y$ 某一位不同，将这一位当成个位，就可以按照 $3\sim 5$ 点的解法解决。而这些位一定满足 $x\oplus y$ 的该位为 $1$。

所以我们再分别存储所有第 $i$ 位为 $1$ 的数的异或和，再找到 $x\oplus y$ 其中为 $1$ 的位，就能求出 $x$ 与 $y$ 的值了。

实现时尽量避开 iostream 等空间消耗大的头文件，节省空间；$2\times 10^6$ 个整数输入量还是很大的，建议使用快读快写。其实是我忘了 scanf 和 printf 这俩玩意了

#include <cstdio>
namespace cjdst{
	typedef long long ll;
	typedef unsigned long long ull;
	
	inline bool isdigit(char c){
		return ('0' <= c && c <= '9');
	}
	
    inline ll read(){
        char c = getchar();
        ll x = 0;
        while(!isdigit(c)) c = getchar();
        while(isdigit(c)){
            x = x * 10 + c - '0';
            c = getchar();
        }
        return x;
    }
    
    char buf[30];
    
    inline void write(ll n){
    	int ct = 0;
    	while(n){
    		buf[++ct] = n % 10 + '0';
    		n /= 10;
		}
		for(int i = ct; i; i--) putchar(buf[i]);
	}

    const int N = 63;
    ll tmp[N + 5];
    
    inline void swap(ll &x, ll &y){
    	x ^= y ^= x ^= y;
	}

	void solve(){
		for(int i = 0; i <= N; i++){
			tmp[i] = 0;
		}
        int n = read(), d = read();
        ll cur = 0;
        for(int i = 1; i <= n; i++){
            ll val = read();
            cur ^= val;
            for(int j = 0; j <= N; j++){
                if(val >> j & 1) tmp[j] ^= val;
            }
        }
        if(d == 2){
            for(int i = 1; i <= n; i++){
                ll val = read();
            }
        }
        for(int i = 0; i <= N; i++){
            if(cur >> i & 1){
            	ll x = tmp[i], y = cur ^ tmp[i];
            	if(x > y) swap(x, y);
            	write(x), putchar(' '), write(y), putchar('\n');
            	return;
            }
        }
	}
}

int main(){
	int c = cjdst::read(), T = cjdst::read();
	for(int _ = 1; _ <= T; _++){
		cjdst::solve();
	}

	return 0;
}

时间复杂度：$O(\sum n\log V)$。

空间复杂度：$O(\log V)$。

最大空间 1.39MB。