AcWing 142. 前缀统计
统计一条路径上的end即可
#include<bits/stdc++.h>
using namespace std;
int n,m;
int tr[100005][26],tot,ed[100005];
void ins(string s){int p=0;for(int i=0;i<s.size();i++){int ch=s[i]-'0';if(tr[p][ch])p=tr[p][ch];else{tr[p][ch]=++tot;p=tot;}}ed[p]++;
}
int sum(string s){int p=0,res=0;for(int i=0;i<s.size();i++){int ch=s[i]-'0';if(tr[p][ch])p=tr[p][ch],res+=ed[p];else{break;}}return res;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){string a;cin>>a;ins(a);}for(int j=1;j<=m;j++){string a;cin>>a;printf("%d\n",sum(a));}return 0;
}
AcWing 143. 最大异或对
二进制数位从高到低插入每个数，试图更新答案时能走不一样的使异或值为1就走不一样的
注意trie树至少开30*10000
#include<bits/stdc++.h>
using namespace std;
int n,x,ans;
int tr[3000005][2],tot;
void ins(int x){int p=0;for(int i=30;i>=0;i--){int ch=(x>>i)&1;if(tr[p][ch]==0)tr[p][ch]=++tot;p=tr[p][ch];}
}
int calc(int x){int p=0,ans=0;for(int i=30;i>=0;i--){int ch=(x>>i)&1;if(tr[p][ch^1]!=0){ans=ans*2+1; p=tr[p][ch^1];}else if(tr[p][ch]!=0){ans=ans*2;p=tr[p][ch];}}return ans;
}
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&x);ins(x);ans=max(ans,calc(x));}cout<<ans;return 0;
}
AcWing 144. 最长异或值路径
求出树上每个点到根节点的异或路径长度的d[i]
可以发现x，y路径即d[x] xor d[y]
因为根到lca的路径恰好抵消了，留下的即为x，y路径
即求
变成上一题
同理trie开30*100000
#include<bits/stdc++.h>
using namespace std;
int n,u,v,w,d[100005],ans,tr[3000005][2],tot;
vector<pair<int,int> >edge[500005];
void dfs(int x,int fa){for(auto i:edge[x]){int y=i.first,z=i.second;if(y==fa)continue;d[y]=d[x]^z;dfs(y,x);}
}
void ins(int x){int p=0;for(int i=30;i>=0;i--){int ch=(x>>i)&1;if(!tr[p][ch])tr[p][ch]=++tot;p=tr[p][ch];}
}
int query(int x){int p=0,ans=0;for(int i=30;i>=0;i--){int ch=(x>>i)&1;if(tr[p][ch^1]) {ans=ans*2+1;p=tr[p][ch^1];}else{ans=ans*2;p=tr[p][ch];}}return ans;
}
int main(){scanf("%d",&n);for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);edge[u].push_back({v,w});edge[v].push_back({u,w}); }dfs(0,-1);for(int i=0;i<n;i++){ans=max(query(d[i]),ans);ins(d[i]);}printf("%d",ans);return 0;
}
AcWing 161. 电话列表
先插入后判断
分两种情况
1.为其他串的前缀：搜到最后一个点还有儿子
2.其他串是其前缀：中途有end[p]==1
一样注意开10*10000
多测不能提前return/break
#include<bits/stdc++.h>
using namespace std;
int tr[100005][10],tot,ed[100005],f,n;
string s;
void ins(){int p=0;for(int i=0;i<s.size();i++){int ch=s[i]-'0';if(!tr[p][ch])tr[p][ch]=++tot;p=tr[p][ch];}ed[p]=1;
}
bool check(){int p=0;for(int i=0;i<s.size();i++){int ch=s[i]-'0';p=tr[p][ch];if(p==0)return 1;if(ed[p]==1)return 0;}int flag=0;for(int i=0;i<=9;i++)flag=(flag||tr[p][i]);if(flag)return 0;return 1;
}
void work(){memset(tr,0,sizeof(tr));memset(ed,0,sizeof(ed));tot=0;scanf("%d",&n);f=1;for(int i=1;i<=n;i++){cin>>s;if(!check()){f=0;//不能break}ins();}if(f)printf("YES\n");else printf("NO\n");
}
int main(){int T;cin>>T;while(T--)work();return 0;
}