题意
给定一个由 \(n\) 个非负整数组成的数组 \(a\)。
如果 \(a_i \oplus a_j < 4\)，那么你就可以交换 \(a_i、a_j\)，其中，\(\oplus\) 是按位异或。
求出操作若干次后，字典序最小的序列。
数据范围：\(1 \le n \le 2 \times 10^5\)，\(0 \le a_i \le 10^9\)。
题解
性质：$ a_i \oplus a_j < 4 $ 的充分必要条件是：如果不考虑 \(a_i、a_j\) 二进制下的最低两位，那么\(a_i、a_j\) 相等。
我们可以将 \(a_1 \sim a_n\) 划分为若干个集合，每个集合内部实现升序排序，然后放回对应的位置。由于值域很大，因此这个操作可以用 std::map 实现。
时间复杂度为 \(\mathcal{O}(nlogn)\)。
点击查看代码
#include <bits/stdc++.h>
using i64 = int64_t;
inline int read() {
bool sym = false; int res = 0; char ch = getchar();
while (ch < '0' or ch > '9') sym |= (ch == '-'), ch = getchar();
while (ch >= '0' and ch <= '9') res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
void solve() {
int n = read();
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
a[i] = read();
}
std::map<int, std::priority_queue<int>> f;
for (int i = 1; i <= n; i++) {
f[a[i] ^ (a[i] & 3)].push(-a[i]);
}
for (int i = 1; i <= n; i++) {
printf("%d%s", -f[a[i] ^ (a[i] & 3)].top(), i == n ? "\n" : " ");
f[a[i] ^ (a[i] & 3)].pop();
}
}
int main() {
int T = read();
while (T--) {
solve();
}
return 0;
}