题解 CF1971G XOUR

传送门

Solution

注意到若 $a_i \oplus a_j < 4$，则 $a_i>>2=a_j>>2$。我们将除以四后结果相同的元素分到同一组。显然，若 $a_i$，$a_j$ 可交换，$a_j$，$a_k$ 可交换，则 $a_i$，$a_k$ 可交换。所以同一组内的所有元素可相互交换，即每一组均可内部排序。

将每一组排好序后，倒序枚举原数组，将每个元素替换成所在组内的最后一个元素，并将其从组内弹出。替换完成的新数组即为答案。

code

在 C++11 及以上版本，可用 auto 枚举 map。

#include <bits/stdc++.h>
#define N 200010
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x)
{
    x = 0; T f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    x *= f;
}

int T, n, a[N], ans[N];

void WORK()
{
    map<int, vector<int> > mp;
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        mp[a[i] >> 2].push_back(a[i]);
    }
    for (auto &[num, vec] : mp)
        sort(vec.begin(), vec.end());
    for (int i = n; i; i--) {
        ans[i] = mp[a[i] >> 2].back();
        mp[a[i] >> 2].pop_back();
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    putchar('\n');
}

int main()
{
    read(T);
    while (T--) WORK();
    return 0;
}