本文共三道题目, 都算是 $ Trie $ 树的模板题
- 1.Phone List https://loj.ac/problem/10049
- Code
- #include<cmath>
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define LL long long
- using namespace std;
- int T,n,rot,trie[100005][15];
- bool flag,book[100005];
- char ch[15];
- bool insert(char s[])
- {
- int u=0,len=strlen(s);
- bool frog=0;
- for(int i=0;i<len;i++)
- {
- int v=s[i]-'0';
- if(!trie[u][v]) trie[u][v]=++rot;
- else if(i==len-1) frog=1;
- u=trie[u][v];
- if(book[u]) frog=1;
- }
- book[u]=1;
- return frog;
- }
- int main()
- {
- scanf("%d",&T);
- while(T--)
- {
- flag=0,rot=0;
- memset(trie,0,sizeof(trie));
- memset(book,0,sizeof(book));
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- cin>>ch;
- if(!flag&&insert(ch)) flag=1;
- }
- if(flag) puts("NO");
- else puts("YES");
- }
- return 0;
- }
- 2.The XOR Largest Pair https://loj.ac/problem/10050
- Code
- #include<cmath>
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define LL long long
- using namespace std;
- const int N=1e5+5;
- int n,rot,ans,a[N],trie[N<<5][2];
- void insert(int x)
- {
- int u=0;
- for(int i=1<<30;i;i>>=1)
- {
- int v=(x&i)?1:0;
- if(!trie[u][v]) trie[u][v]=++rot;
- u=trie[u][v];
- }
- return;
- }
- int find(int x)
- {
- int u=0,res=0;
- for(int i=1<<30;i;i>>=1)
- {
- int v=(x&i)?1:0;
- if(trie[u][!v])
- {
- res+=i;
- u=trie[u][!v];
- }
- else u=trie[u][v];
- }
- return res;
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&a[i]);
- insert(a[i]);
- ans=max(ans,find(a[i]));
- }
- printf("%d\n",ans);
- return 0;
- }
3.Nikitosh 和异或 https://loj.ac/problem/10051
- Code
- #include<cmath>
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define LL long long
- using namespace std;
- const int N=4e5+5;
- int n,rot,now,ans,a[N],trie[N<<5][2],l[N],r[N];
- void insert(int x)
- {
- int u=0;
- for(int i=1<<30;i;i>>=1)
- {
- int v=(x&i)?1:0;
- if(!trie[u][v]) trie[u][v]=++rot;
- u=trie[u][v];
- }
- return;
- }
- int find(int x)
- {
- int u=0,res=0;
- for(int i=1<<30;i;i>>=1)
- {
- int v=(x&i)?1:0;
- if(trie[u][!v])
- {
- res+=i;
- u=trie[u][!v];
- }
- else u=trie[u][v];
- }
- return res;
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++) scanf("%d",&a[i]);
- insert(now);
- for(int i=1;i<=n;i++)
- {
- now^=a[i];
- insert(now);
- l[i]=max(l[i-1],find(now));
- }
- now=0,rot=0;
- memset(trie,0,sizeof(trie));
- insert(now);
- for(int i=n;i>=1;i--)
- {
- now^=a[i];
- insert(now);
- r[i]=max(r[i+1],find(now));
- }
- for(int i=1;i<n;i++) ans=max(ans,l[i]+r[i+1]);
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3184662.html