学了Trie树（学习Trie树相关的内容，！），来做这题，感觉挺简单的，边输入边判断是否存在是否有前缀（prefix）,这样的话要考虑两种情况，一种是前面的某个串是该串的前缀，或者该串是前面某个串的前缀。   写完，提交，TLE！！原来不能用动态建树的方法，必须用静态树！ 后来再提交，WA。。。哎。纠结死我了。跟别人的对比了下，觉得自己的也没错啊...真不知道错在哪了。下面贴出代码，求大牛指导！ 最后看了discuss里面前辈给出的程序，把自己的改了下，是先排序，然后再Insert，这样可以少考虑一种情况。然后再把静态树的数组开大点，不然还是会WA的！最后终于AC了。

AC代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;char str[10001][11];const int sunnum=10,base='0';struct Trie{      bool terminal;      //int num;      Trie *sun[sunnum];}node[1000000];struct Phone{       char num[11];       int len;       friend bool operator<(const Phone &a,const Phone &b)       {           return a.len
        
         sun[i]=NULL;    }    temp->terminal=false;    return temp;}void Insert(Trie *root,Phone cur){    Trie *temp=root;    for(int i=0; i
         
          sun[k]==NULL) temp->sun[k]=NewTrie();        else        {            if(temp->sun[k]->terminal==true)   //排序后只需处理这一种情况 即前面的串是后面的串的prefix            {                //return true;                result=false;            }        }        temp=temp->sun[k];    }     temp->terminal=true;}int main(){    int t,n,i;    freopen("acm.txt","r",stdin);    scanf("%d",&t);    while(t--)    {        Trie *root=NewTrie();        scanf("%d",&n);        for(i=0; i
         
        
       
      
     

 

我纠结了好久，但总是WA的代码。求大神指导！他们说的这组数据我也测试通过了。有没有其他的数据来测试呢？

2

2

1

12

2

12

1

#include 
     
      #include 
      
       #include 
       
        using namespace std;char str[10001][11];const int sunnum=10,base='0';struct Trie{      bool terminal;      //int num;      Trie *sun[sunnum];}node[1000000];int x=0;bool result;Trie *NewTrie(){    Trie* temp=node+x++;    for(int i=0; i<10; i++)    {        temp->sun[i]=NULL;    }    temp->terminal=false;    return temp;}bool Insert(Trie *root,char*s){    Trie *temp=root;    while(*s)    {        int k=*s-base;        if(*(s+1)=='\0' && temp->sun[k]!=NULL)  //该串是前面某个串的前缀        {             return true;        }        if(temp->sun[k]==NULL) temp->sun[k]=NewTrie();        else        {            //temp->sun[*s-base]->num++;            if(temp->sun[k]->terminal==true)   //别的字符串是该字符串的前缀            {                return true;            }        }        temp=temp->sun[k];        s++;    }     temp->terminal=true;       return false;}int main(){    int t,n,i;    freopen("acm.txt","r",stdin);    scanf("%d",&t);    while(t--)    {        Trie *root=NewTrie();        scanf("%d",&n);        for(i=0; i