首页 > 代码库 > Tire树入门专题
Tire树入门专题
POJ 3630Phone List
题目连接：http://poj.org/problem?id=3630
题意：问是否有号码是其他号码的前缀。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<map> 5 using namespace std; 6 const int N=1e5+100; 7 struct Tire 8 { 9 int T[N][30];10 int sum[N];11 int cou;12 void init()13 {14 cou=1;15 memset(T,0,sizeof(T));16 memset(sum,0,sizeof(sum));17 }18 void Insert(char *s)19 {20 int h=0,i,n=strlen(s);21 for(i=0; i<n; i++)22 {23 if(T[h][s[i]-‘0‘]==0)24 T[h][s[i]-‘0‘]=cou++;25 h=T[h][s[i]-‘0‘];26 }27 sum[h]++;28 }29 int ask(char *s)30 {31 int h=0,i=0,n=strlen(s);32 for(i=0; i<n-1; i++)33 {34 if(T[h][s[i]-‘0‘])35 {36 h=T[h][s[i]-‘0‘];37 if(sum[h]>0) return 1;38 }39 else return 0;40 }41 return 0;42 }43 } tire;44 char s[10100][100];45 int main()46 {47 int i,T,n;48 scanf("%d",&T);49 while(T--)50 {51 int ans=1;52 scanf("%d",&n);53 getchar();54 tire.init();55 for(i=0; i<n; i++)56 {57 scanf("%s",s[i]);58 getchar();59 tire.Insert(s[i]);60 }61 for(i=0; i<n; i++)62 if(tire.ask(s[i])) ans=0;63 if(ans==0) cout<<"NO"<<endl;64 else cout<<"YES"<<endl;65 }66 return 0;67 }
HDU 1251统计难题
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1251
题意：统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N=5e5+100;struct Tire{ int T[N][30],sum[N]; int cou; void Init() { cou=1; memset(T,0,sizeof(T)); memset(sum,0,sizeof(sum)); } void Insert(char *s) { int i,h=0,n=strlen(s); for(i=0; i<n; i++) { if(T[h][s[i]-‘a‘]==0) T[h][s[i]-‘a‘]=cou++; h=T[h][s[i]-‘a‘]; sum[h]++; } } int ask(char *s) { int i,h=0,n=strlen(s); for(i=0; i<n; i++) { if(T[h][s[i]-‘a‘]!=0) h=T[h][s[i]-‘a‘]; else return 0; } return sum[h]; }} tire;int main(){ char s[100]; tire.Init(); while(gets(s)) { if(strlen(s)==0) break; tire.Insert(s); } while(scanf("%s",s)!=EOF) { cout<<tire.ask(s)<<endl; } return 0;}
HDU 1004Let the Balloon Rise
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1004
题意：输出颜色数量最多的一种颜色。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N=1000+100;struct Tire{ int T[N][30],sum[N]; int cou; void Init() { cou=1; memset(T,0,sizeof(T)); memset(sum,0,sizeof(sum)); } int Insert(char *s) { int i,h=0,n=strlen(s); for(i=0; i<n; i++) { if(T[h][s[i]-‘a‘]==0) T[h][s[i]-‘a‘]=cou++; h=T[h][s[i]-‘a‘]; } sum[h]++; return sum[h]; }} tire;int main(){ int n; char s[100],ans[100]; while(scanf("%d",&n)!=EOF) { if(n==0) break; tire.Init(); int Max=0; while(n--) { getchar(); scanf("%s",s); int x=tire.Insert(s); if(x>Max) { Max=x; strcpy(ans,s); } } printf("%s\n",ans); } return 0;}
HDU 4825Xor Sum
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4825
题意：在集合当中找出一个正整数 K ，使得 K 与 S 的异或结果最大。
思路：尽量使得K的高位与S的高位不同。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N=3e6+100;struct Tire{ int T[N][3],sum[N]; int cou; void Init() { cou=1; memset(T,0,sizeof(T)); memset(sum,0,sizeof(sum)); } void Insert(int num) { int i=0,h=0; for(i=31; i>=0; i--) { if(T[h][(num>>i)&1]==0) T[h][(num>>i)&1]=cou++; h=T[h][(num>>i)&1]; } sum[h]=num; } int ask(int num) { int i=0,h=0; for(i=31; i>=0; i--) { int x=(num>>i)&1,sign=0; if(x==0) sign=1; if(T[h][sign]) h=T[h][sign]; else h=T[h][x]; } return sum[h]; }} tire;int main(){ int n,m; int t,T; scanf("%d",&T); for(t=1; t<=T; t++) { tire.Init(); scanf("%d%d",&n,&m); int num; while(n--) { scanf("%d",&num); tire.Insert(num); } printf("Case #%d:\n",t); while(m--) { scanf("%d",&num); cout<<tire.ask(num)<<endl; } } return 0;}
Tire树入门专题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。