2019 HDU多校第五场 1002.three arrays（01字典树）

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int maxn = 1e5+10;
struct Trie{
	int next[maxn*30][2];
	bool end[maxn*30];
	int cnt[maxn*30],sz,root;
	int newNode(){
		++sz;
		memset(next[sz],0,sizeof(next[sz]));
		cnt[sz] = 0;
		end[sz] = 0;
		return sz;
	}
	void init(){
		sz = 0;
		root = newNode();
	}
	void add(int x){
		int p = root;
		for(int i=29,c;i>=0;i--){
			c = (x>>i)&1;
			if(!next[p][c]){
				next[p][c] = newNode();
			}
			p = next[p][c];
			++cnt[p];
		}
		end[p] = 1;
	}
}A,B;
int _,a[maxn],b[maxn],n;
vector<pair<int,int> > ans;
void dfs(int p1,int p2,int x){
	int e = min(A.cnt[p1],B.cnt[p2]);
	A.cnt[p1]-=e;	B.cnt[p2]-=e;
	if(A.end[p1]){
		ans.push_back(make_pair(x,e));
		return ; 
	}
	if(A.cnt[A.next[p1][0]]&&B.cnt[B.next[p2][0]]){
		dfs(A.next[p1][0],B.next[p2][0],x<<1);
	}
	if(A.cnt[A.next[p1][1]]&&B.cnt[B.next[p2][1]]){
		dfs(A.next[p1][1],B.next[p2][1],x<<1);
	}
	if(A.cnt[A.next[p1][0]]&&B.cnt[B.next[p2][1]]){
		dfs(A.next[p1][0],B.next[p2][1],(x<<1)+1);
	}
	if(A.cnt[A.next[p1][1]]&&B.cnt[B.next[p2][0]]){
		dfs(A.next[p1][1],B.next[p2][0],(x<<1)+1);
	}
}
int main()
{
	for(scanf("%d",&_);_;_--){
		scanf("%d",&n);
		A.init();	B.init();
		ans.clear();
		rep(i,1,n){
			scanf("%d",&a[i]);
			A.add(a[i]);
		}
		rep(i,1,n){
			scanf("%d",&b[i]);
			B.add(b[i]);
		}
		dfs(A.root,B.root,0);
		sort(ans.begin(),ans.end());
		for(int i=0;i<ans.size();++i){
			for(int j=0;j<ans[i].second;++j){	
				printf("%d",ans[i].first);
				if(j!=ans[i].second-1)printf(" ");
			}
			if(i!=ans.size()-1)printf(" ");
		}
		printf("\n");
	}
	return 0;
}