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 |
这道题不要动态开辟空间,贴个代码,造福后人#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> using namespace std; const int Branch = 10; const int Max = 100010; bool result; struct Trie { bool tail; Trie * next[Branch]; }; //字典树结点 struct Phone { char num[11]; int len; friend bool operator <(const Phone &a, const Phone &b) { return a.len < b.len; } }; //电话号码结构体 Phone p[Max]; //存所有的电话号码 Trie tree[Max * 10]; //字典树 Trie *alloc; // = tree; void insert(Trie *&root, Phone cur) { Trie * p = root; for(int i=0; i<cur.len; i++) { int seq = cur.num[i] - '0'; if(p->next[seq] == NULL) { p->next[seq] = alloc ++; memset(p->next[seq], 0, sizeof(Trie)); } else { if(p->next[seq]->tail) result = false; } p = p->next[seq]; } p->tail = true; } int main() { int cases, n; Trie * root;//字典树根节点 cin >> cases; while(cases --) { alloc = tree; //分配指针指向数组首地址 root = alloc ++; memset(root, 0, sizeof(Trie)); scanf("%d", &n); for(int i=0; i<n; i++) { scanf("%s", p[i].num); p[i].len = strlen(p[i].num); } sort(p, p+n); result = true; for(int i=0; i<n && result; i++) { insert(root, p[i]); } if(result) cout << "YES" << endl; else cout << "NO" << endl; } system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator