题意：给定两个长均为n的序列a和b，要求两两配对，a[i]和b[j]配对的值为a[i]^b[j]，求配对后的值之和的最大值
n<=1e5，a[i]，b[i]<=1e9
思路：和字典序最大的策略是等价的
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned int uint; 5 typedef unsigned long long ull; 6 typedef pair<int,int> PII; 7 typedef pair<ll,ll> Pll; 8 typedef vector<int> VI; 9 typedef vector<PII> VII; 10 //typedef pair<ll,ll>P; 11 #define N 200010 12 #define M 200010 13 #define fi first 14 #define se second 15 #define MP make_pair 16 #define pb push_back 17 #define pi acos(-1) 18 #define mem(a,b) memset(a,b,sizeof(a)) 19 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) 20 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--) 21 #define lowbit(x) x&(-x) 22 #define Rand (rand()*(1<<16)+rand()) 23 #define id(x) ((x)<=B?(x):m-n/(x)+1) 24 #define ls p<<1 25 #define rs p<<1|1 26 27 const ll MOD=1e9+7,inv2=(MOD+1)/2; 28 double eps=1e-6; 29 ll INF=1e15; 30 int dx[4]={-1,1,0,0}; 31 int dy[4]={0,0,-1,1}; 32 33 int t[N*32][2],s[N*32][2],a[N],b[N],m,cnt; 34 ll ans; 35 36 int read() 37 { 38 int v=0,f=1; 39 char c=getchar(); 40 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 41 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 42 return v*f; 43 } 44 45 void update(int x,int y,int op) 46 { 47 int u=1; 48 per(i,30,0) 49 { 50 int now=(x>>i)&1; 51 if(!t[u][now]) t[u][now]=++cnt; 52 u=t[u][now]; 53 s[u][op]+=y; 54 } 55 } 56 57 int query(int x,int op) 58 { 59 int u=1,res=0; 60 per(i,30,0) 61 { 62 int now=(x>>i)&1; 63 if(t[u][now^1]&&s[t[u][now^1]][op]) 64 { 65 if(now^1) res+=1<<i; 66 u=t[u][now^1]; 67 } 68 else 69 { 70 if(now) res+=1<<i; 71 u=t[u][now]; 72 } 73 74 } 75 return res; 76 } 77 78 int find(int op) 79 { 80 int u=1,res=0; 81 per(i,30,0) 82 { 83 if(t[u][0]&&s[t[u][0]][op]) u=t[u][0]; 84 else 85 { 86 res+=1<<i; 87 u=t[u][1]; 88 } 89 } 90 return res; 91 } 92 93 int dfs(int x,int op,int pre) 94 { 95 while(1) 96 { 97 int y=query(x,op^1); 98 if(y==pre) 99 { 100 m++; 101 ans+=(x^y); 102 update(x,-1,op); 103 update(y,-1,op^1); 104 return 1; 105 } 106 if(dfs(y,op^1,x)) return 0; 107 } 108 } 109 110 void solve() 111 { 112 int n=read(); 113 cnt=1; 114 rep(i,1,n) 115 { 116 a[i]=read(); 117 update(a[i],1,0); 118 } 119 rep(i,1,n) 120 { 121 b[i]=read(); 122 update(b[i],1,1); 123 } 124 ans=0; 125 m=0; 126 while(m<n) 127 { 128 int x=find(0); 129 dfs(x,0,-1); 130 } 131 printf("%I64d\n",ans); 132 rep(i,1,cnt) 133 rep(j,0,1) t[i][j]=s[i][j]=0; 134 } 135 136 int main() 137 { 138 //freopen("1.in","r",stdin); 139 int cas=read(); 140 while(cas--) solve(); 141 return 0; 142 }