CF948D Perfect Security Trie
题目中p数组的数的顺序是可以打乱的，所以将每一个pi的二进制形式插入01Trie里
然后枚举每一个ai在字典树中贪心的匹配，尽量走与当前二进制位的数字相同的边
如10010在走到第2位时，在字典树中走1边，因此能得到最小的数，进而字典序最小
在走完一个pi时，要在字典树中把pi删去
所以在加入数时，将经过的每一个Trie上的节点的sum累加1
在匹配ai时将遍历到的节点sum减1，因此可删除被匹配到的数
枚举时只要不遍历sum=0的节点即可
#include <bits/stdc++.h> using namespace std; const int MAXN=300010; int n,a[MAXN],p[MAXN]; int tot,kwh,last; struct node { int ch[2]; int fa,which,sum; bool end; }sh[MAXN*20]; void get(int x) { int now; now=1; sh[now].sum--; for (int j=31;j>=0;j--) { int num; num=(x>>j)&1; if (sh[now].ch[num] && sh[sh[now].ch[num]].sum>0) now=sh[now].ch[num]; else now=sh[now].ch[num^1]; sh[now].sum--; } kwh=sh[now].which; last=now; } void insert(int x,int wh) { int now=1; ++sh[now].sum; for (int j=31;j>=0;--j) { int num; num=(x>>j)&1; if (!sh[now].ch[num]) { tot++; sh[now].ch[num]=tot; sh[tot].fa=now; now=sh[now].ch[num]; } else { now=sh[now].ch[num]; } if (j==0) sh[now].end=1,sh[now].which=wh; sh[now].sum++; } } int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]); for (int i=1;i<=n;++i) scanf("%d",&p[i]); tot=1; for (int i=1;i<=n;++i) insert(p[i],i); for (int i=1;i<=n;++i) { get(a[i]); printf("%d ",a[i]^p[kwh]); } printf(" "); }