poj 3630

这道题是得用静态内存方式的trie树，动态链表形式的trie树会TLE

#include<cstdio>
#include<cstring>
#include<cstdlib>
const int Max=10;
using namespace std;
struct trie{
    int next[Max];
    int flag;
}node[100000];
int num;
struct trie root;
bool insert(char * str){
    int i,len,tem,p;
    p=0;
    len=strlen(str);
    for(i=0;i<len;i++){
        tem=str[i]-'0';
        if(node[p].next[tem]!=-1){
            p=node[p].next[tem];
            if(i==len-1)
                return 1;
            if(node[p].flag==1)
                return 1;
        }
        else{
            node[p].next[tem]=++num;
            p=num;
        }
        if(i==len-1)
            node[p].flag=1;
    }
    return 0;
}
int main(){
    int T,t,n,i;
    char s[15];
    bool yes;
    scanf("%d",&T);
    for(t=1;t<=T;t++){
        scanf("%d",&n);
        memset(node,-1,sizeof(node));     ///初始化莫忘
        yes=0;
        num=0;
        root=node[0];
        for(i=1;i<=n;i++){
            scanf("%s",s);
            if(yes==0)
                if(insert(s))
                    yes=1;
        }
        if(yes==0)
            printf("YES\n");
        else
            printf("NO\n");
    }
}

注意写静态内存方式的trie树时不要乱写指针，我就悲剧的调试好久没有结果

#include<cstdio>
#include<cstring>
#include<cstdlib>
const int Max=10;
using namespace std;
struct trie{
    struct trie * next[Max];
    int flag;
    trie(){
        flag=0;
        for(int i=0;i<10;i++)
            next[i]=NULL;
    }
}node[200000];
int num;
struct trie root;
bool insert(char * str){
    int i,len,tem;
    struct trie* p,q;
    p=&root;
    len=strlen(str);
    for(i=0;i<len;i++){
        tem=str[i]-'0';
        if(p->next[tem]!=NULL){
            if(i==len-1)
                return 1;
            if(p->flag==1)
                return 1;
            p=p->next[tem];
        }
        else{
            q=node[num++];
            p->next[tem]=&q;
            p=&q;
        }
    }
    p->flag=1;
    return 0;
}
int main(){
    int T,t,n,i;
    char s[15];
    bool yes;
    scanf("%d",&T);
    for(t=1;t<=T;t++){
        scanf("%d",&n);
        yes=0;
        num=1;
        root=node[0];
        for(i=1;i<=n;i++){
            scanf("%s",s);
            if(yes==0)
                if(insert(s))
                    yes=1;
        }
        if(yes==0)
            printf("YES\n");
        else
            printf("NO\n");
    }
    system("pause");
}