Perfect Security

题意

给你两个序列 ，让你求的一种排列，使得得到的序列字典序最小

思路

贪心的选择与匹配，使得最优。我们将,拆分后 , 贪心就可以方便地进行。枚举两串上,每一位上的数尽量使各位相异或后为即可选择出最合适的 。

实现

还是要用到我们的树来实现。先建立一棵基于 的二进制数的字典树,并记录各节点代表的元素出现的个数。然后传入每一个进行查找，从字典树的根部向下查找每一位，尽可能使得异或和为。若最优值在此位置个数为,选择另一值,使此位置选择的值数量,并进入下一层 , 继续进行查找。

代码

#include<bits/stdc++.h>
#define ll long long
const int N=1e7+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,num=1,py;
int a[N];
struct node
{
    int cnt,son[2];
}t[N];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

void insert(int x)
{
    int now=1;
    t[1].cnt++;
    for(int i=30;i>=0;i--)
    {
        int nxt=(x>>i)&1;
        if(!t[now].son[nxt]) t[now].son[nxt]=++num;
        now=t[now].son[nxt];
        t[now].cnt++;
    }
}

int query(int x)
{
    int now=1,ans=0;
    for(int i=30;i>=0;i--) 
    {
        int nxt=(x>>i)&1;
        if(!t[t[now].son[nxt]].cnt) nxt=!nxt; 
        ans=(ans<<1)+nxt;
        now=t[now].son[nxt];
        t[now].cnt--;
    }
    return ans^x;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)    a[i]=read();
    for(int i=1;i<=n;i++)    py=read(),insert(py);    
    for(int i=1;i<=n;i++)    printf("%d ",query(a[i])); 
    return 0;
}