trie树就是从当前节点往每个字母连一个指针，从而(O(26*n))或别的复杂度，反正有一个常数。表达能力不不行……
建树(插入)
void ins(char *s)
{
int len=strlen(s),u=1;
for(int i=0;i<=len-1;++i)
{
int v=s[i]-'a';
if(!ch[u][v])ch[u][v]=++cnt;
u=ch[u][v];
++val[u];
}
}
查询
int find(char *s)
{
int u=1;
int len=strlen(s);
for(int i=0;i<=len-1;++i)
if(ch[u][s[i]-'a'])u=ch[u][s[i]-'a'];
else return 0;
return val[u];
}
应该看完代码就能理解吧qwq
trie树最经典的应用是找与一个串有相同前缀的串有几个。
就是这题：HDU1251
#include<bits/stdc++.h>
using namespace std;
#define gc() getchar()
const int N=1000005;
char s[N][11],a[11];
int cnt=1,lens,n=1,ch[N][26],val[N*26];
bool f;
void ins(char *s)
{
int len=strlen(s),u=1;
for(int i=0;i<=len-1;++i)
{
int v=s[i]-'a';
if(!ch[u][v])ch[u][v]=++cnt;
u=ch[u][v];
++val[u];
}
}
int find(char *s)
{
int u=1;
int len=strlen(s);
for(int i=0;i<=len-1;++i)
if(ch[u][s[i]-'a'])u=ch[u][s[i]-'a'];
else return 0;
return val[u];
}
int main()
{
char c;
while(true)
{
c=gc();
if(c==10)
{
if(f)break;
else f=true,++n,lens=0;
}
else f=false,s[n][lens++]=c;
}
for(int i=1;i<=n;++i)ins(s[i]);
while(scanf("%s",a)!=EOF)printf("%d
",find(a));
return 0;
}
然后主要就是找异或最大值。这类问题就是把数二进制拆分反着插入，然后对于查询，每次选择与当前点权值（0/1）相反的节点继续往下，如果没有沿着相同的数走，一个贪心。
这题的意思是，给一个含有n个元素的集合，再给m个数，对于每个数求出与集合中数的异或最大值。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=100005;
ll T,n,m,a[N],cnt;
ll ch[N*32+5][2];
ll en[(N*32+5)<<1];
void ins(int x)
{
ll u=1;
ll i=(((ll)(1ll<<30ll))<<1ll);
for(;i;i>>=1)
{
int c=(i&x)?1:0;
if(!ch[u][c])ch[u][c]=++cnt;
u=ch[u][c];
}
en[u]=x;
}
void clear()
{
memset(ch,0,sizeof(ch));
memset(en,0,sizeof(en));
cnt=1;
}
ll find(int x)
{
ll u=1;
ll i=(((ll)(1ll<<30ll))<<1ll);
for(;i;i>>=1)
{
ll c=(i&x)?0:1;
if(ch[u][c])u=ch[u][c];
else u=ch[u][!c];
}
return en[u];
}
signed main() {
scanf("%lld",&T);
for(int t=1;t<=T;++t)
{
scanf("%lld%lld",&n,&m);
clear();
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]),ins(a[i]);
ll x;
printf("Case #%d:
",t);
while(m--)
{
scanf("%lld",&x);
printf("%lld
",find(x));
}
}
return 0;
}
很经典的做法。考虑用一个比较套路的DP，l[i]表示[1,i]的最大值，r[i]表示区间[i,n]的最大值，最后求max{l[i],r[i+1]}.
关于l[i],考虑求出异或前缀和(s_i=a_1igoplus a_2igoplus cdots igoplus a_i)，最后 (a_iigoplus a_{i+1}igoplus cdots igoplus a_j=s_{i-1}igoplus s_j) ,然后针对 (s) 跑一遍上面那道题的做法就好了。
r[i]反着做一遍就好了。
#include<bits/stdc++.h>
using namespace std;
int max(int a,int b){return a>b?a:b;}
const int N=400005;
int n,a[N],ans,cnt,l[N],r[N],sum;
int ch[N<<5][2];
void ins(int x)
{
int u=1;
int i=1<<30;
for(;i;i>>=1)
{
int c=(i&x)?1:0;
if(!ch[u][c])ch[u][c]=++cnt;
u=ch[u][c];
}
}
int find(int x)
{
int u=1,ans=0;
int i=1<<30;
for(;i;i>>=1)
{
int c=(i&x)?0:1;
if(!ch[u][c])c=!c;
u=ch[u][c];
ans<<=1;ans|=c;
}
return ans^x;
}
void clear()
{
cnt=1;sum=0;
memset(ch,0,sizeof(ch));
}
signed main() {
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
clear();
for(int i=1;i<=n;++i)
{
sum^=a[i];
ins(sum);
l[i]=max(l[i-1],find(sum));
}
clear();
for(int i=n;i>=1;--i)
{
sum^=a[i];
ins(sum);
r[i]=max(r[i+1],find(sum));
}
for(int i=1;i<n;++i)ans=max(ans,l[i]+r[i+1]);
printf("%d
",ans);
return 0;
}
关于异或，要充分利用前缀和，即 (xigoplus x=0) 的性质。
这道题，可以把每个节点到根的异或和 ，(O(n)) 可以搞定，然后任取2个节点x,y，然后算一下异或和，会发现异或路径和就是2个节点向根的异或前缀和异或一下！
#include<cstdio>
#include<cstring>
using namespace std;
int max(int a,int b){return a>b?a:b;}
const int N=100005;
int n,a[N],num_edge,head[N],ans,cnt;
int ch[N<<5][2];
struct edge{
int to,next,len;
}e[N<<1];
void add(int from,int to,int len)
{
++num_edge;
e[num_edge].len=len;
e[num_edge].next=head[from];
e[num_edge].to=to;
head[from]=num_edge;
}
void dfs(int u,int fa)
{
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to,w=e[i].len;
if(v==fa)continue;
a[v]=a[u]^w;
dfs(v,u);
}
}
void ins(int x)
{
int u=1;
int i=1<<30;
for(;i;i>>=1)
{
int c=(i&x)?1:0;
if(!ch[u][c])ch[u][c]=++cnt;
u=ch[u][c];
}
}
int find(int x)
{
int u=1,ans=0;
int i=1<<30;
for(;i;i>>=1)
{
int c=(i&x)?0:1;
if(!ch[u][c])c=!c;
u=ch[u][c];
ans<<=1;
ans|=c;
}
return ans^x;
}
void clear()
{
cnt=1;ans=0;
num_edge=0;
memset(ch,0,sizeof(ch));
memset(head,0,sizeof(head));
memset(e,0,sizeof(e));
}
signed main() {
while(scanf("%d",&n)!=EOF)
{
clear();
for(int i=1,u,v,w;i<n;++i)
{
scanf("%d%d%d",&u,&v,&w);
++u,++v;
add(u,v,w);
add(v,u,w);
}
dfs(1,0);
for(int i=1;i<=n;++i)ins(a[i]);
for(int i=1;i<=n;++i)ans=max(ans,find(a[i]));
printf("%d
",ans);
}
return 0;
}