题意: 给定两个长度为的序列
和
,改变
中的元素顺序使得序列
的字典序最小。
数据范围:,
题解: 将序列插入到
树中,然后依次查询与
异或后最小的
的值,记得用完后要将这个
给删除,即
减
。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int a[N], n;
int son[N * 32][2], idx;
int cnt[N * 32];
void insert(int x) {
int p = 0;
for(int i = 30; i >= 0; --i) {
int u = x >> i & 1;
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
++cnt[p];
}
}
int query(int x) {
int p = 0, res = 0;
for(int i = 30; i >= 0; --i) {
int u = x >> i & 1;
if(son[p][u] && cnt[son[p][u]]) res = res * 2 + u, p = son[p][u];
else res = res * 2 + !u, p = son[p][!u];
--cnt[p];
}
return res;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = 1; i <= n; ++i) {
int x; scanf("%d", &x);
insert(x);
}
for(int i = 1; i <= n; ++i) printf("%d%c", query(a[i]) ^ a[i], " \n"[i == n]);
return 0;
} 
京公网安备 11010502036488号