解题思路： 因为查询的是前缀，只需要将单词中的每个字母的cnt相加即可
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int son[maxn][26],cnt[maxn],idx; char str[maxn]; void add(char *str){ int p=0; for(int i=0;str[i];i++){ int u=str[i]-'a'; if(!son[p][u]) son[p][u]=++idx; p=son[p][u]; } cnt[p]++; } int ask(char *str){ int p=0,res=0; for(int i=0;str[i];i++){ int u=str[i]-'a'; if(!son[p][u]) break; p=son[p][u]; res+=cnt[p]; } return res; } void AC(){ int n,m; cin>>n>>m; while(n--){ cin>>str; add(str); } while(m--){ cin>>str; cout<<ask(str)<<endl; } } int main(){ AC(); return 0; }
#include<bits/stdc++.h> using namespace std; const int N=1e6+7; int son[N][26],cnt[N],idx; char str[N]; void insert(char *str){ int p=0; for(int i=0;str[i];i++){ int u=str[i]-'a'; if(!son[p][u]) son[p][u]=++idx; p=son[p][u]; } cnt[p]++; } int query(char *str){ int p=0; for(int i=0;str[i];i++){ int u=str[i]-'a'; if(!son[p][u]) return 0; p=son[p][u]; } return cnt[p]; } int main(){ int n; cin>>n; while(n--){ char op[2]; scanf("%s%s",op,str); if(*op=='I') insert(str); else printf("%d\n",query(str)); } return 0; }
解题思路： 有点贪心的感觉，我们每一次都走与当前这一位相反的位置,也就是让异或值最大,如果说没有相反的位置可以走的话,那么就走相同的位置.
代码：
#include<bits/stdc++.h> using namespace std; const int N = 100010, M = 3000000; int n; int a[N], son[M][2], idx; void insert(int x) { int p = 0; for (int i = 30; i >= 0; i -- ) { int &s = son[p][x >> i & 1]; if (!s) s = ++ idx; p = s; } } int search(int x) { int p = 0, res = 0; for (int i = 30; i >= 0; i -- ) { int s = x >> i & 1; if (son[p][!s]) { res += 1 << i; p = son[p][!s]; } else p = son[p][s]; } return res; } int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) { scanf("%d", &a[i]); insert(a[i]); } int res = 0; for (int i = 0; i < n; i ++ ) res = max(res, search(a[i])); printf("%d\n", res); return 0; }
思路： 满足答案的关系只有两种，一种是插入的串是之前的串的前缀，那么只要看在插入过程中是不是没有新增节点；另一种是插入的串包括之前的串，也就是之前的串是插入的串的前缀，这个只要看看有没有走到打了标记的点就好了。所以只需要在插入时判断即可；
#include<bits/stdc++.h> using namespace std; const int maxn=100010; int son[maxn][10],cnt[maxn],idx; char str[maxn]; int add(char *str){ int p=0,f1=0,f2=1; for(int i=0;str[i];i++){ int u=str[i]-'0'; if(!son[p][u]) son[p][u]=++idx,f2=0; p=son[p][u]; if(cnt[p]) f1=1; } cnt[p]=1; if(f1||f2) return 1; return 0; } void AC(){ int t;cin>>t; while(t--){ int n;cin>>n; idx=0; memset(son,0,sizeof son); memset(cnt,0,sizeof cnt); bool flag=true; while(n--){ cin>>str; if(add(str)) flag=false; } if(flag) puts("YES"); else puts("NO"); } } int main(){ AC(); return 0; }
未完待续
待刷题目合集：字典树题目 - Virtual Judge
密码：ludicpc
