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