引言

剛學了\(Trie\)樹，寫篇博客鞏固一下。

題目

首先安利一發\(Trie\)樹模板

1、Phone List

2、The XOR largest pair

3、The xor-longest Path

4、Codechef REBXOR

第一題不難，但是我用的是暴力。

構造一棵\(Trie\)樹，然后把字符串長度從大到小排序，然后按順序插入。若在插入的時候\(Trie\)樹結點一直不為空，那么該串為其的子串。

\(Code\ Below:\)

#include <bits/stdc++.h> using namespace std; int n,trie[100010][10],ans,tot; char s[100010][15]; struct node{int len,id; }l[100010]; void insert(int k){int len=strlen(s[k]),p=0,b=0;for(int i=0;i<len;i++){if(trie[p][s[k][i]-'0']==-1) {trie[p][s[k][i]-'0']=++tot;b=1;}p=trie[p][s[k][i]-'0'];}if(b==0) ans=1; } bool cmp(node a,node b){return a.len>b.len; } int main() {int t;scanf("%d",&t);while(t--){memset(trie,-1,sizeof(trie));scanf("%d",&n);ans=0;tot=0;for(int i=1;i<=n;i++){scanf("%s",s[i]);l[i].len=strlen(s[i]);l[i].id=i;}sort(l+1,l+n+1,cmp);for(int i=1;i<=n;i++){if(ans==0) insert(l[i].id);}if(ans==1) printf("NO\n");else printf("YES\n");}return 0; }

第二題構造一棵\(Trie\)樹，然后根據異或的運算規則，盡量當前的值與結點的值不一樣。
此題是二三題的基礎。

\(Code\ Below:\)

#include <cstdio> int n,trie[100010*31][2],ans=0,val,tot=0; int max(int a,int b){return a>b?a:b;} int search(int x){int p=0,num=0,c;for(int i=31;i>=0;i--){c=(x>>i)&1;if(trie[p][c^1])p=trie[p][c^1],num=num<<1|1;else p=trie[p][c],num=num<<1;}return num; } void insert(int x){int p=0,c;for(int i=31;i>=0;i--){c=(x>>i)&1;if(!trie[p][c]) trie[p][c]=++tot;p=trie[p][c];} } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&val);ans=max(ans,search(val));insert(val);}printf("%d\n",ans);return 0; }

定義前綴異或和\(sum[1..i]=a[1]\)^\(...\)^\(a[i]\),\(v[i..j]=a[i]\)^\(a[i+1]\)^\(...\)^\(a[j]\),則\(v[i..j]=sum[1..i] * sum[1..j]\)

由于\(a^a=0,0^a=a,\)所以異或兩次值不變。

那么預處理出樹上前綴異或和（即到根的前綴異或和），跑一遍\(The\ XOR\ largest\ pair\)

\(Code\ Below:\)

#include <cstdio> int n,trie[100010*31][2],ans=0,a[100010],val,tot=0,t=0,head[100010]; int max(int a,int b){return a>b?a:b;} struct node{int to,val,next; }e[100010*2]; void add(int x,int y,int w){e[++t].to=y;e[t].val=w;e[t].next=head[x];head[x]=t; } void dfs(int x,int fa,int now){a[x]=now;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa) continue;dfs(y,x,now^e[i].val);} } int search(int x){int p=0,num=0,c;for(int i=31;i>=0;i--){c=(x>>i)&1;if(trie[p][c^1])p=trie[p][c^1],num=num<<1|1;else p=trie[p][c],num=num<<1;}return num; } void insert(int x){int p=0,c;for(int i=31;i>=0;i--){c=(x>>i)&1;if(!trie[p][c]) trie[p][c]=++tot;p=trie[p][c];} } int main() {scanf("%d",&n);for(int i=1;i<n;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);add(x,y,w);add(y,x,w);}dfs(1,1,0);for(int i=1;i<=n;i++){ans=max(ans,search(a[i]));insert(a[i]);}printf("%d\n",ans);return 0; }

第四題預處理出前綴異或和和后綴異或和，然后用\(O(n)\)的時間求最大值

\(Code\ Below:\)

#include <cstdio> int n,trie[400010*31][2],ans=0,val,tot=0,a[100010],l[400010],r[400010]; int max(int a,int b){return a>b?a:b;} int search(int x){int p=0,num=0,c;for(int i=31;i>=0;i--){c=(x>>i)&1;if(trie[p][c^1])p=trie[p][c^1],num=num<<1|1;else p=trie[p][c],num=num<<1;}return num; } void insert(int x){int p=0,c;for(int i=31;i>=0;i--){c=(x>>i)&1;if(!trie[p][c]) trie[p][c]=++tot;p=trie[p][c];} } int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int now=0;insert(now);for(int i=1;i<=n;i++){now^=a[i];l[i]=max(l[i-1],search(now));insert(now);}now=0;insert(now);for(int i=n;i>=1;i--){now^=a[i];r[i]=max(r[i+1],search(now));insert(now);}for(int i=1;i<n;i++){ans=max(ans,l[i]+r[i+1]);}printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/owencodeisking/p/9735350.html

總結

以上是生活随笔為你收集整理的[学习笔记]我们追过的神奇异或（Trie树系列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。