Trie字典树习题（一本通）

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1e5+10;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
/*
int t,n,tot;
int tri[maxn][12];
int isend[maxn];
char a[11];
bool  insr(char *s){
	int now=0,len=strlen(s);
	bool xx=0;
	for(int i=0;i<len;i++){
		int x=s[i]-‘0‘;
		if(!tri[now][x]) tri[now][x]=++tot;
		now=tri[now][x];
		//cout<<now<<" ";
		if(isend[now]) xx=1;
	}
	isend[now]++;
//	cout<<endl;
	if(xx) return 1;
	return 0;
}
bool flag;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		memset(tri,0,sizeof(tri));
		memset(isend,0,sizeof(isend));
		flag=0;
		while(n--){
			scanf("%s",a);
			if(insr(a)) flag=1;
		}	
		if(flag) printf("NO\n");
		else printf("YES\n");
	}
return 0;
}

*/

//我的字典树为什么运行错误！！！！
//不过这道题更见到的做法也很简单了
string ss[10010];
int t,n;
bool flag;

int main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=0;i<n;i++) cin>>ss[i];
		sort(ss,ss+n);
		flag=0;
		for(int i=0;i<n-1;i++){
			if(ss[i]==ss[i+1].substr(0,ss[i].length())) {
				flag=1;
				break;
			}
		}
		if(flag) cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}
	return 0;
}

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1e5+10;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//思路：把每一个数字 x 转化为31位的二进制数，不够的前面补0，并插入到字典树中（最低为二进制位为叶节点）；
//接下来对每一个数字 x 的二进制位进行查找，每一步都尽量找与当前位置相反的数字进行访问，入如果有相反的数字，根据xor运算这一位就会留下一个 1 ，最后找出最大值就行。
int trie[maxn*32][2];
int n,ans;
void inti(){
	memset(trie,0,sizeof(trie));
	ans=1;
}
void inse(int x){
	int now=1;
	for(int i=30;i>=0;i--){
		int c=x&(1<<i)?1:0;
		if(!trie[now][c]){
			trie[now][c]=++ans;
		}
		now=trie[now][c];
	}
}
int que(int x){
	int now=1;
	int tot=0;
	for(int i=30;i>=0;i--){
		int c=x&(1<<i)?1:0;
		if(trie[now][!c]){
			now=trie[now][!c];
			tot|=(1<<i);
		}
		else now=trie[now][c];
	}
	return tot;
}
int main(){
	inti();
	scanf("%d",&n);
	int x,maxx=0;
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		inse(x);
		maxx=max(maxx,que(x));
	}
	printf("%d\n",maxx);
return 0;
}

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=4e5+10;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//所以处理出异或前缀和，不断加入01Trie树求解即可。
//考虑到要求两个子段，用ls[i],rs[i分别表示1~i、i~n的最大异或子段,最后扫一遍取max即可。
//原文链接：https://blog.csdn.net/Jason_lxy/article/details/88855100
//重点就是要枚举每一个点左右边的最大异或和
//另一种做法：不太懂  https://blog.csdn.net/bao___zi/article/details/83092217 

//过不了两个点》。。。。y一个是内存超限，一个是运行错误 
int ch[12500000][2];
int lf[maxn],ri[maxn];
int n,a[maxn];
int tot=1;
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch==‘-‘) ff=-1;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
inline void inti(){
	memset(ch,0,sizeof(ch));
	tot=1;
}
inline void inse(int x){
	int now=1;
	for(int i=30;i>=0;i--){
		int c=x&(1<<i)?1:0;
		if(!ch[now][c]) ch[now][c]=++tot;
		now=ch[now][c]; 
	}
}
inline int fin(int x){
	int now=1,ans=0;
	for(int i=30;i>=0;i--){
		int c=x&(1<<i)?1:0;
		if(ch[now][!c]){
			now=ch[now][!c];
			ans|=(1<<i);
		}
		else now=ch[now][c];
	}
	return ans;
}

int main(){
 	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	lf[1]=a[1];
	inse(a[1]);
	for(int i=2;i<=n;i++){
		lf[i]=max(lf[i-1],fin(a[i]));  //前缀异或和 
		inse(a[i]);
	}
	inti();
	ri[n]=a[n];
	inse(a[n]);
	for(int i=n-1;i>=2;i--){
		ri[i]=max(ri[i+1],fin(a[i]));
		//fin(a[i])表示的其实是通过a[i]异或能够得到的最大值
		//而ri[i+1]就是表示不需要用a[i] 去异或 
		inse(a[i]);
	}
	int maxx=0;
	for(int i=1;i<=n-1;i++){
		maxx=max(maxx,lf[i]+ri[i+1]);
	}
	printf("%d\n",maxx);
return 0;
}