Phone List HDU - 1671

题目链接：

题目：

给出一个电话号码列表，确定它是否一致，因为没有数字是另一个号码的前缀。假设电话目录列出了这些数字：

1. Emergency 911

2. Alice 97 625 999

3. Bob 91 12 54 26

在这种情况下，无法呼叫Bob，因为只要您拨打了Bob的电话号码的前三位数字，中心就会将您的呼叫转接到紧急线路。所以这个列表不一致。

输入

第一行输入给出一个整数，1 <= t <= 40，即测试用例的数量。每个测试用例以n（电话号码的数量）在单独的行上开始，1 <= n <= 10000.然后是n行，每行有一个唯一的电话号码。电话号码是最多十位数的序列。

产量

对于每个测试用例，如果列表一致则输出“YES”，否则输出“NO”。

思路：将这些电话号码插入字典树中，只要出现一个电话号码是另一个电话号码的前缀，那么就输出“NO”否则输出“YES”，

这题要注意内存的控制，否则会MLE，还有不能n方来利用find前缀函数判断每一个字符串在其他字符串是否是前缀，否则会TLE，

只要在将电话号码插入字典树的时候判断p->num是否不为0即可，如果不为0就break，很好的避免了n方判断、

// // Created by HJYL on 2019/8/20.//#include 
     
      #include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;typedef long long ll;const int maxn=1e6+10;struct trie{ int sum; trie* next[10];}*root;trie* build(){ trie *T=(trie *)malloc(sizeof(trie)); T->sum=0; for(int i=0;i<10;i++) T->next[i]=NULL; return T;}bool flag;void insert(char* s){ trie* p=root; for(int i=0;s[i];i++) { if(p->next[s[i]-'0']==NULL) { p->next[s[i]-'0']=build(); } p=p->next[s[i]-'0']; if(p->sum!=0) { flag=false;//一旦出现前缀就跳出 break; } } p->sum++;//在字符串结尾，单词个数加一 for(int i=0;i<10;i++) { if(p->next[i]!=NULL) { flag=false; return; } }}int find(char* s){ trie* p=root; for(int i=0;s[i];i++) { if(p->next[s[i]-'0']==NULL) return 0; else p=p->next[s[i]-'0']; } return p->sum;}void delte(trie *p)//很最重要的内存删除{ if(p!=NULL) { for(int i = 0; i < 10; i++) { if(p->next[i]!=NULL) delte(p->next[i]); } } free(p); p=NULL;}int main(){ //freopen("C:\\Users\\asus567767\\CLionProjects\\untitled\\text", "r", stdin); int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); root=build(); char str[10007][50]; flag=true; for(int i=0;i

转载于:https://www.cnblogs.com/Vampire6/p/11386356.html

你可能感兴趣的文章