题目大意:
给你两个序列a,b,要你从b中找一个排列,使得bi oxr ai 最小,并且字典序最小。
思路:
先把要排列的b插入字典树中去,然后枚举a,一个一个去贪心的找最小值就行了。
每次找的都是最小的xor值就保证了字典序最小。
因为每个数只能被找一次,所以这个题难度在于,从字典树找最小异或值,并且每个数只能被找一次。
最小异或值比较简单,贪心找,当前二进制为0就往0子树走,为1就往1走,实在走不了就计算异或值。
每个数只能走一次,可以用一个数组记录每个节点被插入的次数,然后这题就没了。
代码:

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 2e7 + 10;
typedef long long int ll;
int trie[maxn][2],tot;
int a[300100];
int cnt[maxn];
void insert(int x){
    int p = 0;
    for(int i = 30; i >= 0; i--){
        int c = (x >> i) & 1;
        if(!trie[p][c])trie[p][c] = ++tot;
        p = trie[p][c];cnt[p]++;
    }
}
int query(int x){
    int p = 0,res = 0;
    for(int i = 30; i >= 0; i--){
        int c = (x >> i) & 1;
        if(trie[p][c] && cnt[trie[p][c]] >= 1)p = trie[p][c];
        else p = trie[p][c ^ 1],res |= (1 << i);
        cnt[p]--;
    }
    return res;
}
void solved(){
    int n;cin>>n;
    for(int i = 1; i <= n; i++)cin>>a[i];
    for(int i = 1; i <= n; i++){
        int p;cin>>p;insert(p);
    }
    for(int i = 1; i <= n; i++){
        printf("%d ",query(a[i]));
    }
}
int main(){
    solved();
    return 0;
}