POJ 3630 Phone List [Trie] - c++编程基础

判断是否有前缀...明显就是一个trie了...裸的不能再裸

注意用动态的trie额外分配内存的时候会TLE...所以就用静态的...

不过静态trie一开始还不太会用...不过后来感觉思路和静态邻接表感觉差不多...

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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"< else
cout<<"YES"< }
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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

POJ 3630 Phone List [Trie] (一)