西部数码个人网站wordpress单栏简洁

题目链接：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,3int 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();}
}

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