做法：01字典树+贪心

题意：

有长度为n的两个a,b数组，改变b中元素的顺序,使数组c (c[i]=a[i]^b[i])的字典序最小，并输出数组c

思路：

  • 这题思路和前两题很相似，唯一不同点是求最小而已
  • 每次a[i]上异或上一个b数组中任意元素（不能重复使用），使得c[i]最小即可
  • 记录每个节点经过多少次，每一次插入的时候将出现次数的标记加1，每一次查询的时候将经过的点的标记减1，如果这点标志为0，那么这条路就不能走。

代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=300010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;

int ans,x,temp;
int a[N],b[N];


struct Trie {
    int nex[N*32][2],cnt=0;
     int cntp[N*32];

    void insert(int x) { 
        int p = 0;//下标 
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if (!nex[p][c]) nex[p][c] = ++cnt; 
            p = nex[p][c];
            cntp[p]++; //前缀出现次数 
        }
    }
    int find(int x) {
        int p = 0,res = 0;
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if(nex[p][c]&&cntp[nex[p][c]]) p=nex[p][c];
            else p=nex[p][c^1],res|=(1<<i);
            cntp[p]--;
        }
        return res;
    }
} t;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
    freopen("F:/laji/1.in", "r", stdin);
//    freopen("F:/laji/2.out", "w", stdout);
#endif
    int n;
    cin>>n;
    _for(i,n){
        cin>>a[i];
    }
    _for(i,n){
        cin>>b[i];
        t.insert(b[i]);
    }
    _for(i,n){
        cout<<t.find(a[i])<<" ";
    }
    return 0;
}