G. XOUR

题目链接：Problem - G - Codeforces

题目大意：给你一个n长的序列， 其中你可以将a[i]  XOR a[j] 的值 严格小于4的数对进行交换。 你可以操作任何几次， 让最后的数列最小。如果在 x 和 y 不同的第一个位置， xi<yi ，那么数组 x 在词法上比数组 y 小。  具体题目见链接。

输入：

第一行包含一个整数 t ( 1≤t≤1e4 ) - 测试用例数。

每个测试用例的第一行包含一个整数 n (1≤n≤2⋅1e5 ) - 数组的长度。

每个测试用例的第二行包含 n 个整数 ai ( 0≤ai≤1e9 ) - 数组的元素。

保证所有测试用例中 n 的总和不超过 2⋅1e5 

考察知识点：                     并查集， 容器map的使用，位运算（a^b==c   c^b==a）。

1.首先可以交换的条件可以看出， 我们可以将 可以交换的数字放在一起，有此功能的算法，不难想到并查集， 然后为了方便使用 并 可以方便取出数据， 采用map, 收集。

2.可以合并的条件：两数 XOR < 4 , 此处， 暴力枚举 0，1，2，3 XOR回取在map里查找是否出现了该数， 如果出现，将该数的下标与次数合并。  最后在到map里标记次数，记录下标。

3. 在并查集使用完过后， 又采用 map<int, multiset<int>> q； 收集每一个下标上的值， 方便在于最后的重新赋值。 利用了multiset的自动排序不去重。 q的键实质上就是每个联通块的根。

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128;

const int N = 2e5+9;
int tr[N];
int n;
void innt(){
    for(int i=0; i<n; i++) 
        tr[i] = i;
}//并查集
int find(int x) {
    if(tr[x] != x) {
        tr[x] = find(tr[x]);
    }
    return tr[x];
}
void mger_(int a, int b){
    a = find(a);
    b = find(b);
    if(a==b)return;
    tr[b] = a;
}
map<int,int> mp;
map<int, multiset<int>> q;
void solve(){
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++) {
        cin >> a[i];
    }

    innt();
    mp.clear();//初始化
    q.clear();
    
    for(int i=0; i<n; i++) {
        for(int k=0; k<4; k++) { //枚举0,1,2,3
            int u = a[i] ^ k;
            if(mp.count(u)) {
                mger_(i, mp[u]);
            }//有就连起来
        }
        mp[a[i]] = i;//标记
    } 
    for(int i=0; i<n; i++) {
        q[find(i)].insert(a[i]); //分组到q
    }

    for(int i=0; i<n; i++) {
        int u = find(i);
        a[i] = *q[u].begin();
        q[u].erase(q[u].begin());//使用过后删除
    }
    for(int i=0; i<n; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

感谢收看与点赞， 欢迎大佬指正。