nyoj 163 Phone List(动态字典树<trie>) poj Phone List (静态字典树<trie>)
2023-09-11 14:21:11 时间
Phone List
时间限制:1000 ms | 内存限制:65535 KB
难度:4
- 描述
-
Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogue listed these numbers:
- Emergency 911
- Alice 97 625 999
- Bob 91 12 54 26
In this case, it's not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob's phone number. So this list would not be consistent.
- 输入
- The first line of input gives a single integer, 1 ≤ t ≤ 10, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 100000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.
- 输出
- For each test case, output "YES" if the list is consistent, or "NO" otherwise.
- 样例输入
-
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
- 样例输出
-
NO YES
1 /** 2 题目大意(nyoj 163): 3 判断一个字符串是否是其他字符串的前缀字符串 4 5 算法:动态(链表)字典树 6 7 步骤: 8 Ⅰ、用struct建立字典树的模型(并在其内部构建初始化函数) 9 Ⅱ、建立my_insert方法实现将数据的插入(并在插入的时候判断是否满足题意) 10 11 **/
基础模板代码(node、my_insert):
1 struct node 2 { 3 node *next[10]; 4 int cnt; 5 node () 6 { 7 cnt = 0; 8 memset (next, 0, sizeof (next)); 9 } 10 } 11 12 node *root = new node(); 13 14 void my_insert (char *s) 15 { 16 node *p = new node(); 17 int i, k, len = strlen (s); 18 for (i = 0; i < len; ++ i) 19 { 20 k = s[i] - '0'; 21 if (p->next [k] == NULL) 22 p->next [k] = new node(); 23 p = p->next [k]; 24 } 25 p->cnt = 1; 26 return ; 27 }
nyoj 163 (AC) C\C++代码实现:
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 6 using namespace std; 7 8 int T, n, flag, mark; 9 10 char temp[12]; 11 12 struct node 13 { 14 node *next[10]; 15 int cnt; 16 node () 17 { 18 cnt = 0; 19 memset(next, 0, sizeof(next)); 20 } 21 }; 22 23 node *root; 24 25 void my_insert (char *s) 26 { 27 node *p = root; 28 mark = 0; 29 int i, k, len = strlen(s); 30 for (i = 0; i < len; ++ i) 31 { 32 k = s[i] - '0'; 33 if (p->next[k] == NULL) 34 { 35 mark = 1; 36 p->next[k] = new node(); 37 } 38 p = p->next[k]; 39 if (p->cnt) 40 { 41 flag = 0; 42 return ; 43 } 44 } 45 if (!mark) 46 { 47 flag = 0; 48 return ; 49 } 50 p->cnt = 1; 51 return ; 52 } 53 54 int main() 55 { 56 scanf("%d", &T); 57 while(T --) 58 { 59 flag = 1; 60 root = new node(); 61 scanf("%d", &n); 62 while(n --) 63 { 64 gets(temp); 65 if (!flag) continue; 66 my_insert (temp); 67 } 68 if (!flag) 69 printf("NO\n"); 70 else 71 printf("YES\n"); 72 } 73 return 0; 74 }
下面是poj 3630 的算法:
1 /** 2 题目大意(poj 3630): 3 判断一个字符串是否是其他字符串的前缀字符串 4 是 ==> return NO 5 (if all)否 ==> return YES 6 7 算法:静态字典树 8 9 步骤: 10 Ⅰ、用struct建立字典树模型(并在其内部构建初始化函数) 11 Ⅱ、建立my_insert方法实现数据的插入(并判断是否满足条件) 12 **/
基本模型:
1 int pos; 2 3 struct node 4 { 5 node *next[10]; 6 int cnt; 7 node() 8 { 9 cnt = 0; 10 memset(next, 0, sizeof(next)); 11 } 12 }; 13 14 node *root; 15 pos = 1; 16 17 void my_insert (node *root, char *s) 18 { 19 node *p = root; 20 int i, k, len = strlen (s); 21 for (i = 0; i < len; ++ i) 22 { 23 k = s[i] - '0'; 24 if (p->next [k] == 0) 25 { 26 p->next [k] = root + pos; 27 pos ++; 28 } 29 p = p->next [k]; 30 } 31 p->cnt = 1; 32 return ; 33 } 34 35 my_insert(root + 1, temp);
poj 3630 (C\C++代码实现 <AC>):
PS:调试用的 node root[10000]。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstring> 5 6 using namespace std; 7 8 int n, flag, mark, pos; 9 10 char temp[12]; 11 12 struct node 13 { 14 node *next[10]; 15 int cnt; 16 node() 17 { 18 cnt = 0; 19 memset(next, 0, sizeof(next)); 20 } 21 }; 22 23 void my_insert (node *root, char *s) 24 { 25 mark = 0; 26 node *p = root; 27 int i, k ,len = strlen(s); 28 for (i = 0; i < len; ++ i) 29 { 30 k = s[i] - '0'; 31 if (p->next[k] == 0) 32 { 33 mark = 1; 34 p->next[k] = root + pos; 35 ++ pos; 36 } 37 p = p->next[k]; 38 if (p->cnt) 39 { 40 flag = 1; 41 return; 42 } 43 } 44 if (!mark) 45 { 46 flag = 1; 47 return ; 48 } 49 50 p->cnt = 1; 51 return ; 52 } 53 54 int main () { 55 int N; 56 scanf ("%d", &N); 57 while (N --) { 58 flag = 0; 59 node root[100005]; 60 pos = 1; 61 scanf("%d", &n); 62 while (n --) 63 { 64 scanf("%s", &temp[0]); 65 if (flag) continue; 66 my_insert (root + 1, temp); 67 } 68 if (flag) 69 printf("NO\n"); 70 else 71 printf("YES\n"); 72 } 73 return 0; 74 }
相关文章
- dede:list 与 dede:arclist 的区别
- 遍历List、Map删除元素
- Unity编译时找不到AndroidSDK的问题 | Unable to list target platforms(转载)
- C#中数组、ArrayList与List对象的区别
- json串 转 list<class> 方法 List转JSONArray和JSONArray转List String 转List
- SAP Fiori Elements List Report Smart Table Toolbar 的 XML 视图实现
- how drop down list description is displayed by UI framework
- ABAP where used list
- java list按照元素对象的指定多个字段属性进行排序
- 如何从 SAP Fiori Elements List Report Table 点击事件响应函数里拿到表格某一行的信息
- 已解决IndexError: list index out of range
- C++ 如何正确使用erase删除list中的元素。
- list集合删除最后一个元素
- 标准库中 vector list等排序
- PostgreSQL的学习心得和知识总结(一百二十一)|词法级自上而下完美实现Oracle数据库PL/SQL过程语言的 for in list 的实现方案
- JDK源码详解之List接口
- MySQL ---- In aggregated query without GROUP BY, expression #2 of SELECT list contains nonaggregated