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 |
C++静态建树!!/* 考察了字典树的操作,刚开始我是动态建树的,好遗憾 竟然超时了,所以采取了静态建树的方式 注意输入顺序 假如有 110002 和 110 要考虑两种情况 110002 110 与 110 110002; 这两种情况 其他的就没傻了 */ #include <iostream> #include <stdio.h> #include <string.h> #include <string> #include <algorithm> using namespace std; int Count; struct Trie { Trie * next[10]; bool flag;//标记是否是结尾 int cnt; Trie() { for(int i = 0; i < 10; i++) next[i] = NULL; flag = false; cnt = 0; } }; Trie memory[600050]; Trie * root = NULL;//根节点 bool Insert(char msg[]) { int i = 0; Trie * cur = root; int k; while(msg[i]) { int k = msg[i] - '0'; if(cur->next[k] == NULL) cur->next[k] = &memory[Count++];//new Trie();//创建新结点 else { cur->next[k]->cnt++; if(cur->next[k]->flag) return false; } cur = cur->next[k]; i++; } cur->flag = true; if(cur->cnt>=1) return false; return true; } /* void Delete(Trie * root) { for(int i = 0; i < 10; i ++ ) { if(root->next[i] != NULL) Delete(root->next[i]); } delete root; } */ int t; int n; int main() { scanf("%d",&t); char msg[12]; while(t--) { Count = 0; scanf("%d",&n); memset(memory,0,sizeof(memory)); root =&memory[Count++];// new Trie(); bool flag = true; for(int i = 0; i < n; i++) { scanf("%s",msg); if(flag) flag = Insert(msg); } if(!flag) printf("NO\n"); else printf("YES\n"); // Delete(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