Codeforces Gym101503E：XOR-omania（构造+思维）

题目链接

题意

给出m个数b，这些数是由n个数a两两异或组成的，问初始的那n个数分别是多少。

思路

存在多组解的情况...原来是个构造题。

考虑这样一种情况：b1 = a1 ^ a2，b2 = a2 ^ a3，b3 = a1 ^ a3。那么只要确定了a1，就可以求出a2和a3了。那么可以假设a1=0，自然就可以求出a3，再可以求出a2了。但是对于某个ai，如果ai加入了答案，那么存在一些bj就是不合法的，例如我们选了的b1 = a1 ^ a2，如果我们把a1和a2都加入了答案里面，那么对于其他的能两两异或得到b1的数，都是不合法的，而且我们要判断a1和a2能加入答案，当且仅当a1 ^ a2存在于b集合里面。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 11;
int a[N], ans[N];
map<int, int> mp;

int main() {
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), mp[a[i]]++;
    ans[1] = 0; int cnt = 1;
    for(int i = 1; i <= n; i++) {
        bool flag = true;
        for(int j = 1; j <= cnt; j++) { // 判断是否异或得到的数是否存在于集合里面(合法)
            if(!mp[ans[j]^a[i]]) {
                flag = false; break;
            }
        }
        if(flag) {
            for(int j = 1; j <= cnt; j++) // 删除加入a[i]后不合法的情况
                mp[ans[j]^a[i]]--;
            ans[++cnt] = a[i];
        }
    }
    for(int i = 1; i <= cnt; i++)
        printf("%d%c", ans[i], i == cnt ? '
' : ' ');
    return 0;
}