POJ 3630 Phone List [Trie]

判斷是否有前綴...明顯就是一個trie了...裸的不能再裸

注意用動態的trie額外分配內存的時候會TLE...所以就用靜態的...

不過靜態trie一開始還不太會用...不過後來感覺思路和靜態鄰接表感覺差不多...

[cpp]
#include <set>  
#include <map>  
#include <list>  
#include <cmath>  
#include <ctime>  
#include <deque>  
#include <queue>  
#include <stack>  
#include <bitset>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <cassert>  
#include <cstdlib>  
#include <cstring>  
#include <sstream>  
#include <fstream>  
#include <numeric>  
#include <iomanip>  
#include <iostream>  
#include <algorithm>  
#include <functional>  
using namespace std; 
//typedef long long LL;  
//typedef __int64 LL;  
//typedef long double DB;  
//typedef unisigned __int64 LL;  
//typedef unsigned long long ULL;  
#define EPS  1e-8  
#define MAXN 100005  
#define MAXE 300000  
#define INF  0x3f3f3f3f  
#define PI   acos(-1.0)  
#define MOD  99991  
//#define MOD  99990001  
//#define MOD  1000000007  
#define max(a,b)    ((a)>(b)?(a):(b))  
#define min(a,b)    ((a)<(b)?(a):(b))  
#define max3(a,b,c) (max(max(a,b),c))  
#define min3(a,b,c) (min(min(a,b),c))  
#define mabs(a)     ((a<0)?(-a):a)  
//#define L(t)      (t << 1)  //Left son t*2  
//#define R(t)      (t << 1 | 1) //Right son t*2+1  
//#define Mid(a,b)  ((a+b)>>1) //Get Mid  
//#define lowbit(a) (a&-a) //Get Lowbit  
//int gcd(int a,int b){return b?gcd(b,a%b):a;}  
//int lcm(int a,int b){return a*b/gcd(a,b);}  
//std::ios::sync_with_stdio(false);  
struct  trie 
{ 
    int next[10]; 
    bool vis; 
}tree[MAXN]; 
struct  alpha 
{ 
    int len ; 
    char ch[11]; 
}str[MAXN]; 
int cnt,n,T,loc; 
bool judge; 
void insert(alpha s) 
{ 
    int now = 1,len = s.len; 
    for(int i  = 0 ; i < len ; i++) 
    { 
        int tmp = s.ch[i] - '0'; 
        if(tree[now].next[tmp] == -1) 
        { 
            tree[now].next[tmp] = loc; 
            if(i == len-1) 
                tree[loc].vis = true; 
            else 
                tree[loc].vis = false; 
            for(int j = 0 ; j < 10 ; j++) 
                tree[loc].next[j] = -1; 
            now = loc; 
            loc++; 
        }else 
        { 
            now = tree[now].next[tmp]; 
            if(tree[now].vis || (i == len-1)) 
            { 
                judge = true; 
                return; 
            } 
        } 
    } 
} 
int main() 
{ 
//  freopen("in.txt","r",stdin);  
//  freopen("out.txt","w",stdout);  
    cin>>T; 
    while(T--) 
    { 
        tree[1].vis = false; 
        judge = false; 
        loc = 2; 
        for(int i = 0 ; i < 10 ; i++) 
            tree[1].next[i] = -1; 
        cin>>n; 
        for(int i = 0 ; i < n ; i++) 
        { 
            scanf("%s",str[i].ch); 
            str[i].len = strlen(str[i].ch); 
        } 
        for(int i = 0 ; i < n ; i++) 
        { 
            if(!judge) 
                insert(str[i]); 
            else 
                break; 
        } 
        if(judge) 
            cout<<"NO"<<endl; 
        else 
            cout<<"YES"<<endl; 
    } 
    return 0; 
} 

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
//typedef long long LL;
//typedef __int64 LL;
//typedef long double DB;
//typedef unisigned __int64 LL;
//typedef unsigned long long ULL;
#define EPS  1e-8
#define MAXN 100005
#define MAXE 300000
#define INF  0x3f3f3f3f
#define PI   acos(-1.0)
#define MOD  99991
//#define MOD  99990001
//#define MOD  1000000007
#define max(a,b)  ((a)>(b)?(a):(b))
#define min(a,b)  ((a)<(b)?(a):(b))
#define max3(a,b,c) (max(max(a,b),c))
#define min3(a,b,c) (min(min(a,b),c))
#define mabs(a)  ((a<0)?(-a):a)
//#define L(t)   (t << 1)  //Left son t*2
//#define R(t)   (t << 1 | 1) //Right son t*2+1
//#define Mid(a,b)  ((a+b)>>1) //Get Mid
//#define lowbit(a) (a&-a) //Get Lowbit
//int gcd(int a,int b){return b?gcd(b,a%b):a;}
//int lcm(int a,int b){return a*b/gcd(a,b);}
//std::ios::sync_with_stdio(false);
struct  trie
{
 int next[10];
 bool vis;
}tree[MAXN];
struct  alpha
{
 int len ;
 char ch[11];
}str[MAXN];
int cnt,n,T,loc;
bool judge;
void insert(alpha s)
{
 int now = 1,len = s.len;
 for(int i  = 0 ; i < len ; i++)
 {
  int tmp = s.ch[i] - '0';
  if(tree[now].next[tmp] == -1)
  {
   tree[now].next[tmp] = loc;
   if(i == len-1)
    tree[loc].vis = true;
            else
                tree[loc].vis = false;
   for(int j = 0 ; j < 10 ; j++)
    tree[loc].next[j] = -1;
   now = loc;
   loc++;
  }else
  {
   now = tree[now].next[tmp];
   if(tree[now].vis || (i == len-1))
   {
    judge = true;
    return;
   }
  }
 }
}
int main()
{
//  freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
 cin>>T;
 while(T--)
 {
     tree[1].vis = false;
     judge = false;
  loc = 2;
        for(int i = 0 ; i < 10 ; i++)
            tree[1].next[i] = -1;
  cin>>n;
  for(int i = 0 ; i < n ; i++)
  {
   scanf("%s",str[i].ch);
   str[i].len = strlen(str[i].ch);
  }
  for(int i = 0 ; i < n ; i++)
  {
   if(!judge)
    insert(str[i]);
   else
                break;
  }
  if(judge)
   cout<<"NO"<<endl;
  else
   cout<<"YES"<<endl;
 }
    return 0;
}