首页 > 代码库 > 【POJ】3630 Phone List
【POJ】3630 Phone List
静态字典树。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 5 #define MAXN 10005 6 7 typedef struct Trie { 8 bool v; 9 Trie *next[10];10 Trie() {11 v = false;12 for (int i=0; i<10; ++i)13 next[i] = NULL;14 }15 } Trie;16 17 Trie tries[MAXN*10];18 int num;19 20 bool create(char str[]) {21 int i = 0, id;22 Trie *p = tries;23 bool ret = false;24 25 while (str[i]) {26 id = str[i] - ‘0‘;27 ++i;28 if (p->next[id] == NULL) {29 p->next[id] = &tries[num];30 ++num;31 ret = true;32 } else {33 if (p->next[id]->v == true)34 return false;35 }36 p = p->next[id];37 }38 p->v = true;39 return ret;40 }41 42 int main() {43 int case_n, n;44 char buf[12];45 bool f;46 47 scanf("%d", &case_n);48 49 while (case_n--) {50 scanf("%d", &n);51 f = true;52 num = 1;53 while (n--) {54 scanf("%s", buf);55 if (f)56 f = create(buf);57 }58 if (f) printf("YES\n");59 else printf("NO\n");60 for (int i=0; i<num; ++i) {61 tries[i].v = false;62 memset(tries[i].next, 0, sizeof(tries[i].next));63 }64 }65 66 return 0;67 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。