| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:第二组数据犀利啊In Reply To:第二组数据犀利啊 Posted by:wchhlbt at 2017-03-07 20:52:46 #include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
const int LETTER=10;
int tot=0;
int flag=1;
struct Trie{
int count;
struct Trie *next[LETTER];
bool isEnd;
string name;
Trie(){
count=0;
memset(next,0,sizeof(next));
isEnd=false;
}
};
struct Trie *root=new Trie;
void insert(string s){
int len = s.size();
struct Trie *u=root,p;
for(int i=0;i<len;i++){
int id=s[i]-'0';
if(u->next[id]==NULL){
u->next[id]=new Trie;
}
u=u->next[id];
// if(u->isEnd==true)
// {
// flag=0;
// return ;
// }
u->count++;
}
u->isEnd=true;
u->name=s;
}
void search(Trie *u){
if(flag==0)
return ;
if(u->isEnd==true&&u->count>1){
flag=0;
return ;
}
if(u->isEnd==true&&u->count==1&&flag==1){
flag=1;
return ;
}
for(int i=0;i<LETTER;i++){
if(u->next[i]!=NULL)
{
search(u->next[i]);
}
if(flag==0) return ;
}
}
void del(Trie *u){
for(int i=0;i<LETTER;i++){
if(u->next[i]!=NULL)
del(u->next[i]);
}
if(u==root){
for(int i=0;i<LETTER;i++){
u->next[i]=NULL;
u->count=0;
u->isEnd=false;
}
}
else
delete(u);
}
int main(){
int t;
cin>>t;
while(t--){
int n;
flag=1;
string s;
cin>>n;
for(int i=0;i<n;i++){
cin>>s;
insert(s);
}
search(root);
if(flag==1)
cout<<"YES\n";
else cout<<"NO\n";
del(root);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator