# 01 字典树

01 字典树：解决最大异或问题

和字典树一样，只不过每一个节点的值不再是字符而是 01，一个数从高位到低位对应于字典树从根到叶子，一个数二进制有多少位，就应该建几层树，包含根节点的那个编号 0

树上的每一个点都有各自的编号，节点有两条边，分别是 0 和 1，开空间时应该多开 40 倍左右

# HDU4825 Xor Sum

题目链接

这道题数据有点水，说是不超过 2³²，其实连 int 都没有爆，应该开 33 层 (包含根节点)，但是实际上 32 层就可以，代码是开了 33 层

	#include <bits/stdc++.h>
	//#pragma G++ optimize(2)
	//#pragma G++ optimize(3,"Ofast","inline")
	#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
	#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
	using namespace std;
	typedef long long ll;
	typedef unsigned long long ull;
	const ll MAXN=1e5+100;
	const ll MOD=1e9+7;
	const ll INF=0x3f3f3f3f;
	const ll SUB=-0x3f3f3f3f;
	const double eps=1e-4;
	const double E=exp(1);
	const double pi=acos(-1);
	int ch[30*MAXN][2];
	int val[30*MAXN];
	int tot,t,n,m;
	void init(){
	memset(val,0,sizeof val);
	memset(ch,0,sizeof ch);
	tot=0;
	}
	void insert(int v){
	int u=0;
	for(int i=31;i>=0;i--){
	int now=(v>>i)&1;
	if(!ch[u][now]) ch[u][now]=++tot;
	u=ch[u][now];
	}
	val[u]=v;
	}
	int query(int x){
	int u=0;
	for(int i=31;i>=0;i--){
	int now=(x>>i)&1;
	if(ch[u][now^1]) u=ch[u][now^1];
	else u=ch[u][now];
	}
	return val[u];
	}
	int main(){
	ios;
	cin>>t;
	int js=0;
	while(t--){
	cin>>n>>m;
	init();
	for(int i=1;i<=n;i++){
	int tmp;
	cin>>tmp;
	insert(tmp);
	}
	cout<<"Case #"<<++js<<":\n";
	while(m--){
	int tmp;
	cin>>tmp;
	cout<<query(tmp)<<'\n';
	}
	}

	return 0;
	}

	/*

	*/

题目链接

在一个数组中找出 (s [i]+s [j])^s [k] 最大的值，其中 i、j、k 各不相同。

可以找出任意两个数的和，然后把这两个数从字典树中删除，之后查询最大异或，再添加上，再找，如此往复，输出最大值即可

	#include <bits/stdc++.h>
	#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
	#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
	using namespace std;
	const int MAXN=1010;
	int t,n,tot;
	int ch[MAXN40][2],arr[MAXN],val[MAXN40];
	int num[MAXN*40];
	void insert(int x){
	int u=0;
	for(int i=31;i>=0;i--){
	int now=(x>>i)&1;
	if(!ch[u][now]) ch[u][now]=++tot;
	u=ch[u][now];
	num[u]++;
	}
	val[u]=x;
	}
	int query(int x){
	int u=0;
	for(int i=31;i>=0;i--){
	int now=(x>>i)&1;
	if(ch[u][now^1] && num[ch[u][now^1]]) u=ch[u][now^1];
	else u=ch[u][now];
	}
	return val[u]^x;
	}
	void update(int x,int c){
	int u=0;
	for(int i=31;i>=0;i--){
	int now=(x>>i)&1;
	num[ch[u][now]]+=c;
	u=ch[u][now];
	}
	}
	void init(){
	tot=0;
	memset(val,0,sizeof val);
	memset(num,0,sizeof num);
	memset(ch,0,sizeof ch);
	}
	int main()
	{
	ios;
	cin>>t;
	while(t--){
	init();
	cin>>n;
	for(int i=1;i<=n;i++){
	cin>>arr[i];
	insert(arr[i]);
	}
	int ans=-1;
	for(int i=1;i<n;i++){
	for(int j=i+1;j<=n;j++){
	int cur=arr[i]+arr[j];
	update(arr[i],-1);
	update(arr[j],-1);
	ans=max(ans,query(cur));
	update(arr[i],1);
	update(arr[j],1);
	}
	}
	cout<<ans<<'\n';
	}
	return 0;
	}

题目链接

在树上找一段路径（连续）使得边权相异或的结果最大。

	#include <iostream>
	#include <cstdio>
	#include <algorithm>
	#include <cstdlib>
	#include <cstring>
	#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
	#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
	using namespace std;
	typedef long long ll;
	const int MAXN=110010;
	struct edge{
	int to,w,next;
	}e[MAXN*2];
	int t,n,tot,cnt,root,ans;
	int val[MAXN*32];
	int ch[MAXN*32][2];
	int head[MAXN];
	void add(int u,int v,int c){
	e[cnt]={v,c,head[u]};
	head[u]=cnt++;
	}
	void insert(int x){
	int u=0;
	for(int i=31;i>=0;i--){
	int now=(x>>i)&1;
	if(!ch[u][now]) ch[u][now]=++tot;
	u=ch[u][now];
	}
	val[u]=x;
	}
	int query(int x){
	int u=0;
	for(int i=31;i>=0;i--){
	int now=(x>>i)&1;
	if(ch[u][now^1]) u=ch[u][now^1];
	else u=ch[u][now];
	}
	return val[u]^x;
	}
	void dfs(int x,int f,int pre){
	for(int i=head[x];~i;i=e[i].next){
	int v=e[i].to,w=e[i].w;
	if(v==f) continue;
	ans=max(ans,query(pre^w));
	insert(pre^w);
	dfs(v,x,pre^w);
	}
	}
	void init(){
	memset(val,0,sizeof val);
	memset(ch,0,sizeof ch);
	memset(head,-1,sizeof head);
	ans=0; cnt=0; tot=0;
	}
	int main()
	{
	ios;
	while(scanf("%d",&n)!=EOF){
	init();
	for(int i=0;i<n-1;i++){
	int u,v,w;
	scanf("%d%d%d",&u,&v,&w);
	add(u,v,w);
	add(v,u,w);
	}
	insert(0);
	dfs(root,-1,0);
	printf("%d\n",ans);
	}
	return 0;
	}
	/*
	4
	0 1 3
	1 2 4
	1 3 6
	*/