trie树
trie树？？？
trie树是一种树形结构，可以用来找前缀固定的字符串。
思想
其实思想很简单，就是将每个字符串都挂到树上去，如果当前节点在之前已经有了就不用新建节点，可以继续前面的向下找。否则就新建一个节点，这样就节省了时间和空间。
具体实现
代码一看就懂了，不多bb
板子题
代码：
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int N=400010,L=12; int tree[N][27],tot,m; char s[L]; void add(char S[]) { int now=0; int l=strlen(S); for(int i=0;i<l;++i) { int x=S[i]-'a'; if(tree[now][x]) now=tree[now][x]; else { tree[now][x]=++tot; now=tot; } } return; } bool find(char S[]) { int l=strlen(S),now=0; for(int i=0;i<l;++i) { int x=S[i]-'a'; if(tree[now][x]) now=tree[now][x]; else return 0; } return 1; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%s",s); add(s); } scanf("%d",&m); while(m--) { scanf("%s",s); if(find(s)) printf("YES\n"); else printf("NO\n"); } return 0; }
01trie树
01trie树是一种特殊的trie树，它是将整数按照二进制挂到了树上，这样有时候更加有利于处理问题。比如处理异或值问题。
例题：
代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 const int N=100010; 6 int n; 7 int tree[N*32][2]; 8 int a[N],val[N*32]; 9 int tot; 10 void add(int x) { 11 int now=0; 12 for(int i=31; i>=0; --i) { 13 int c=x>>i&1; 14 if(!tree[now][c]) 15 tree[now][c]=++tot; 16 now=tree[now][c]; 17 } 18 val[now]=x; 19 } 20 int query(int x) { 21 int now=0; 22 for(int i=31; i>=0; --i) { 23 int c=x>>i&1; 24 if(tree[now][c^1]) { 25 now=tree[now][c^1]; 26 } else now=tree[now][c]; 27 } 28 return val[now]; 29 } 30 void pre() 31 { 32 memset(tree,0,sizeof(tree)); 33 tot=0; 34 } 35 int main() { 36 while(scanf("%d",&n)==1) { 37 pre(); 38 int maxx=0; 39 for(int i=1; i<=n; ++i) { 40 scanf("%d",&a[i]); 41 add(a[i]); 42 } 43 int ans=0; 44 for(int i=1; i<=n; ++i) { 45 int kk=query(a[i]); 46 ans=max(ans,kk^a[i]); 47 } 48 printf("%d\n",ans); 49 } 50 51 return 0; 52 }
查看9道真题和解析
韶音科技公司氛围 142人发布