题解 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;
}