大意
给定(A,B)两个数组，让他们进行匹配。
我们称(A_i)与(B_j)的匹配是稳定的，当且仅当目前所剩元素不存在(A_x)或(B_y)使得
(A_ioplus B_j<A_ioplus B_y)或(A_ioplus B_j<A_xoplus B_j)成立
问所有稳定匹配的情况中(A_ioplus B_j)之和最大的是多少。
思路
考虑找到当前异或和最大的一对(A_ioplus B_j)，那么不会存在一个(A_x)或(B_y)可以使得它不稳定，所以这对(A_ioplus B_j)一定会被计入答案。
所以我们每次只用找最大的(A_ioplus B_j)就行了。
考虑如何查找出最大的(A_ioplus B_j)：
我们可以使用两颗Trie树分别维护出(A,B)的信息。
贪心地想，我们每次查找从高位开始，走完全相反的两个方向（如果可以走），一定会比不走相反的方向优。
这样查找可以满足双方面最大，即找出来的(A_i,B_j)一定是会计入答案的（尽管可能不是当前最大的(A_ioplus B_j)）。
因为如果该点对没计入到答案，那么当前一定会存在更优的某个(A_x)或(B_y)使得它不稳定，那么在查找的途中，一定就会进入另一条更优的支路。
所以这样查找依旧可以满足答案的正确性。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100005;
int K,N;
long long Ans;
struct Tree{
int Cnt,Root;
struct Node{
int val,dep;
int ch[2];
}s[MAXN*31];
void Insert(int rt,int val,int dep){
s[rt].val++;s[rt].dep=dep;
if(dep==-1)return ;
int u=(1&(val>>dep));
if(!s[rt].ch[u])s[rt].ch[u]=++Cnt;
Insert(s[rt].ch[u],val,dep-1);
}
}T1,T2;
void Clear(){
for(int i=1;i<=T1.Cnt;i++)T1.s[i].ch[0]=T1.s[i].ch[1]=T1.s[i].dep=T1.s[i].val=0;
for(int i=1;i<=T2.Cnt;i++)T2.s[i].ch[0]=T2.s[i].ch[1]=T2.s[i].dep=T2.s[i].val=0;
T1.Root=T2.Root=T1.Cnt=T2.Cnt=1;Ans=0;
}
void Query(){
int rt1=T1.Root,rt2=T2.Root;
for(int i=30;i>=0;i--){
if(T1.s[T1.s[rt1].ch[0]].val&&T2.s[T2.s[rt2].ch[1]].val)
rt1=T1.s[rt1].ch[0],rt2=T2.s[rt2].ch[1],Ans+=(1<<i);
else if(T1.s[T1.s[rt1].ch[1]].val&&T2.s[T2.s[rt2].ch[0]].val)
rt1=T1.s[rt1].ch[1],rt2=T2.s[rt2].ch[0],Ans+=(1<<i);
else if(T1.s[T1.s[rt1].ch[0]].val&&T2.s[T2.s[rt2].ch[0]].val)
rt1=T1.s[rt1].ch[0],rt2=T2.s[rt2].ch[0];
else if(T1.s[T1.s[rt1].ch[1]].val&&T2.s[T2.s[rt2].ch[1]].val)
rt1=T1.s[rt1].ch[1],rt2=T2.s[rt2].ch[1];
T1.s[rt1].val--;T2.s[rt2].val--;
}
}
int main(){
scanf("%d",&K);
while(K--){
Clear();
scanf("%d",&N);
for(int i=1,x;i<=N;i++)
scanf("%d",&x),T1.Insert(T1.Root,x,30);
for(int i=1,x;i<=N;i++)
scanf("%d",&x),T2.Insert(T2.Root,x,30);
for(int i=1;i<=N;i++)Query();
printf("%lld
",Ans);
}
}
后记
其实题意不能简单地化为让(A)，(B)两两匹配的异或和最大。
（因为要满足稳定条件，且若真的按和最大去做会被以下数据卡掉）
1
2
1 2
2 7
正解为6，手跑和最大为8。