|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
#include <iostream> #include <stdio.h> #include <vector> using namespace std; struct node{ bool endofmark; node *next[11]; node() { endofmark=false; for(int i=0;i<10;i++) next[i]=NULL; } }*root; int insert(string str) { node *curr=root; int id; int created=0; for(int i=0;i<str.size();i++) { id=str[i]-'0'; if(curr->next[id]==NULL) { curr->endofmark=false; curr->next[id]=new node(); created =1; } curr=curr->next[id]; } if(created==0) curr->endofmark=false; else curr->endofmark=true; return created; } bool search(string str) { node *curr=root; int len=str.size(); int id; for(int i=0;i<len-1;i++) { id=str[i]-'0'; curr=curr->next[id]; curr->endofmark=false; } if(curr->next[str[len-1]-'0']) curr=curr->next[str[len-1]-'0']; for(int i=0;i<=9;i++) { if(curr->next[i]) return false; } return true; } void delet(node *curr) { for(int i=0;i<10;i++) { if(curr->next[i]) delet(curr->next[i]); } delete(curr); } int main() { int t,n,d,consist; vector<string> VB; string str; cin>>t; while(t--) { cin>>n; root=new node(); consist=0; d=0; for(int i=0;i<n;i++) { cin>>str; VB.push_back(str); d = insert(str); if(d==0) consist=-1; } if(consist==-1) { cout<<"NO\n"; VB.clear(); delet(root); consist=0; continue; } for(int i=0;i<n;i++) { if(!search(VB[i])) { cout<<"NO\n"; consist=-1; break; } } if(consist!=-1) cout<<"YES\n"; VB.clear(); delet(root); consist=0; } return 0; } |