Phone List
- Emergency 911
- Alice 97 625 999
- Bob 91 12 54 26
Input
Output
Sample Input
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
Sample Output
NO
YES
想法:暑假回炉重造第一天,无限TLE and MLE,菜到不行。简单的字典树模板题,一开始以为是hdu的题,动态指针建树后忘记销毁指针一直MLE;后面改了一直TLE,才发现是poj的3630,也是醉了。要用数组来建树才行。不会这玩意只能百度去学了,真的是菜。
CODE:
hdu1671版(指针建树)
#include<stdio.h>
#include<string.h>
struct trie{
trie *next[10];
int v;
trie(){
v=1;
for(int i=0;i<10;i++) next[i]=NULL;
}
}*root;
void create_trie(char *str){
int len=strlen(str);
trie *p=root,*q;
for(int i=0;i<len;i++){
int id=str[i]-'0';
if(p->next[id]==NULL){
q=new trie;
p->next[id]=q;
p=p->next[id];
}
else{
p->next[id]->v++;
p=p->next[id];
}
}
p->v=-1;
}
int find_trie(char *s){
int len=strlen(s);
trie *q=root;
for(int i=0;i<len;i++){
int id=s[i]-'0';
q=q->next[id];
if(q==NULL) return 0;
if(q->v==-1) return -1;
}
return -1;
}
void delete_trie(trie* q){
if(q==NULL) return ;
for(int i=0;i<10;i++) delete_trie(q->next[i]);
delete q;
}
int main()
{
int t,n,i;
char s[15];
scanf("%d",&t);
while(t--){
scanf("%d",&n);
root=new trie;
int flag=0;
for(i=0;i<n;i++){
scanf("%s",s);
if(flag) continue;
if(find_trie(s)==-1) flag=1;
if(flag) continue;
create_trie(s);
}
if(flag) puts("NO");
else puts("YES");
delete_trie(root);
}
}
poj3630(数组建树)
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e4+5;
char a[N][11];
struct node
{
bool flag;
node *next[11];
node(){
flag=0;
memset(next,0,sizeof(next));
}
}trie[100000];
int num;
void Insert(node *root,char *s)
{
int i=0;
node *p=root;
while(s[i]){
int k=s[i++]-'0';
if(p->next[k]==NULL) p->next[k]=&trie[num++];
p=p->next[k];
}
p->flag=1;
}
bool Search(node *root,char *s)
{
int i=0;
node *p=root;
while(s[i]){
int k=s[i++]-'0';
p=p->next[k];
if(p->flag&&s[i]) return 1;
}
return 0;
}
int main()
{
int t,n,i;
scanf("%d",&t);
while(t--){
memset(trie,0,sizeof(trie));
node *root=&trie[0];
num=1;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%s",a[i]);
Insert(root,a[i]);
}
int flag=0;
for(i=0;i<n;i++){
if(Search(root,a[i])){
flag=1;
break;
}
}
if(!flag) puts("YES");
else puts("NO");
}
return 0;
}