首页 > 代码库 > poj4089:电话号码
poj4089:电话号码
总时间限制: 1000ms 内存限制: 65536kB描述给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如:Emergency 911Alice 97 625 999Bob 91 12 54 26在这个例子中,我们不可能拨通Bob的电话,因为Emergency的电话是它的前缀,当拨打Bob的电话时会先接通Emergency,所以这些电话号码不是一致的。输入第一行是一个整数t,1 ≤ t ≤ 40,表示测试数据的数目。每个测试样例的第一行是一个整数n,1 ≤ n ≤ 10000,其后n行每行是一个不超过10位的电话号码。输出对于每个测试数据,如果是一致的输出“YES”,如果不是输出“NO”。样例输入2391197625999911254265113123401234401234598346样例输出NOYES
这题思路很简单,就是字母树,俗称trie树。然后我就开始傻乎乎地写了。。。果不其然地WA了。
忘记注意一件事情,正常的trie树只是判断前缀,这个还要判断后缀。
即如果输入顺序是:
11
110
需要判断出来NO。
而且,如果输入顺序是:
110
11
也需要判断出来是NO。
注意到这一点就很简单了。
直接看代码:
1 #include <iostream> 2 #include <stdio.h> 3 4 using namespace std; 5 6 struct P 7 { 8 //int i; 9 P* next[10];10 bool flag;11 }s;12 13 void init()14 {15 s.flag = false;16 //s.i = -1;17 for(int i = 0; i < 10; i ++)18 (s.next)[i] = NULL;19 }20 char a[11];21 bool add(int i,P* p)22 {23 if(p->flag == true)24 return false;25 if(a[i] == ‘\0‘)26 {27 p->flag = true;28 bool f = true;29 for(int j = 0; j < 10; j ++)30 if((p->next)[j] !=NULL)31 f = false;32 return f;33 }34 int x = a[i]-‘0‘;35 if((p->next)[x] == NULL)36 {37 (p->next)[x] = new P();38 (p->next)[x]->flag = false;39 for(int j = 0; j < 10; j ++)40 {41 (((p->next)[x])->next)[j] = NULL;42 }43 }44 if(add(i+1,(p->next)[x]))45 return true;46 return false;47 }48 49 int main()50 {51 int t;52 scanf("%d",&t);53 while(t--)54 {55 init();56 int n;57 scanf("%d",&n);58 bool f=true;59 char c;60 scanf("%c",&c);61 while(n--)62 {63 cin.getline(a,11);64 if(!add(0,&s))65 f = false;66 }67 if(f)68 cout<<"YES"<<endl;69 else70 cout<<"NO"<<endl;71 }72 return 0;73 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。