hdu1671

 

个人感觉trie作为一种数据结构其实并不难，在hdu上早先干掉了1251、1075，今天干掉了1247、1671，1247看懂题以后想了一下没有想出，后来参照网上代码，输入数据存入字典树后，再重新例举已输入的串，每一个串代入到字典树中，先判断是不是前缀，然后判断其后的那个单词是不是在字典树中，1671个人认为较为简单，设置一个count成员变量记录有多少个串通过该字母，判断的时候只要count>1&&x[i+1]=='/0'就可以了。

    附1671代码：

    #include<iostream>using namespace std;const int tot=11;const int fir='0';const int len=10000;struct Node{       int son[tot];       int end;       int count;       void to0()       {            count=0;            memset(son,-1,sizeof(son));            end=0;            }            }node[len*10];int num;void insert(char *x){     int len = strlen(x),root = 0;     for (int i = 0; i < len; i++){         int k = x[i]-fir;         if (node[root].son[k]==-1){            num ++;            node[root].son[k] = num;            node[num].to0();                            }         root=node[root].son[k];         node[root].count++;         }     node[root].end++;    }int search(char *x){     int len=strlen(x),root=0,i;     for ( i = 0; i<len; i++){         int temp=x[i]-fir;         if (node[root].son[temp]==-1)return 0;         root=node[root].son[temp];          if (node[root].count>1&&x[i+1]=='/0')return 1;//此句让我wa了N次       }     return 0;}char x[10001][11];int main(){    int  t;    cin >> t;    while (t--){           int n;          cin >> n;           num=0;          node[0].to0();          for (int i=0;i<n;i++){              scanf("%s",x[i]);              insert(x[i]);                }               int check = 0;          for (int i =0;i<n;i++){              if (search(x[i])){check = 1;break;}          }          if (check){printf("NO/n");}          else printf("YES/n");    }    //system("pause");    return 0;    }