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 |
字典树,1A#include <string> #include <cstring> #include <cstdlib> #include <iostream> using namespace std; struct node { bool end; int a[10]; }; bool x; int ptr; node list[100000]; void Init() { x=true; ptr=0; for(int i=0;i<100000;i++) { list[i].end=false; for(int j=0;j<10;j++) list[i].a[j]=-1; } } void Insert(char*s) { bool z=false; bool y=false; int now=0; int len=strlen(s); for(int i=0;i<len;i++) { if(list[now].a[s[i]-'0']==-1) { z=true; list[now].a[s[i]-'0']=++ptr; now=ptr; } else { now=list[now].a[s[i]-'0']; if(list[now].end) y=true; } } list[now].end=true; x=(!y)&&z; } int main() { int t,n; char s[11]; scanf("%d",&t); while(t--) { Init(); scanf("%d",&n); while(n--) { scanf("%s",&s); if(x) Insert(s); } if(x) printf("YES\n"); else printf("NO\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator