专栏首页wym2019 HDU多校第五场 1002.three arrays(01字典树)

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P1972 [SDOI2009]HH的项链 离线树状数组计数

    对询问按照右端点排序,然后 计算按照树状数组求和计算 l,r = sum(r) - sum(l-1)

    用户2965768
  • 2019HDU多校赛第二场 HDU 6601 Keen On Everything But Triangle( 主席树求区间第k大)

    用户2965768
  • Codeforces Round #561 (Div. 2)

    C. 求min(|X-Y|,|X+Y|) <= min(X,Y) <= max(X,Y) <= max(|X-Y|,|X+Y|)

    用户2965768
  • C++上机考试试题解析

    慕白
  • 创造新世界

    众所周知计算机代码底层计算都是0和1的计算,牛牛知道这点之后就想使用0和1创造一个新世界!牛牛现在手里有n个0和m个1,给出牛牛可以创造的x种物品,每种物品都由...

    AI那点小事
  • two Pass方法连通域检测

    原理: Two-Pass方法检测连通域的原理可参见这篇博客:http://blog.csdn.net/lichengyu/article/details/139...

    一棹烟波
  • BZOJ 1022: [SHOI2008]小约翰的游戏John (Anti-nim)

    Description   小约翰经常和他的哥哥玩一个非常有趣的游戏:桌子上有n堆石子,小约翰和他的哥哥轮流取石子,每个人取 的时候,可以随意选择一堆石子,在...

    attack
  • HDU 6629 (2019杭电第五场 1006) string matching (扩展kmp)

    题意: 求字符串 s[i…len−1] and s[0…len−1] i>0 最长公共前缀长度求解过程的比较次数

    用户2965768
  • 算法细节系列(19):广度搜索优先

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 基础知识 | 每日一练(179)

    士人有百折不回之真心,才有万变不穷之妙用。立业建功,事事要从实地着脚,若少慕声闻,便成伪果;讲道修德,念念要从虚处立基,若稍计功效,便落尘情。 ...

    闫小林

扫码关注云+社区

领取腾讯云代金券