HDU1671 字典树

Phone List

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18421    Accepted Submission(s): 6207

Problem Description

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:
1. Emergency 911
2. Alice 97 625 999
3. 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.

Input

The
first line of input gives a single integer, 1 <= t <= 40, the
number of test cases. Each test case starts with n, the number of phone
numbers, on a separate line, 1 <= n <= 10000. Then follows n
lines with one unique phone number on each line. A phone number is a
sequence of at most ten digits.

Output

For each test case, output “YES” if the list is consistent, or “NO” otherwise.

Sample Input

2

3

911

97625999

91125426

5

113

12340

123440

12345

98346

Sample Output

NO

YES

题意:

一次给出n个电话号码,如果刚给出的一个电话号码的前几位包含前面给出的某一个号码则这个号码不能拨打(输入那前几位时就会马上打出去了)。

代码:

 1 //字典树的权值作为标记点,每输入一个号码,查找他每一位的val值有没有等于1的,如果没有就把他放入字典树他的最后一
 2 //位的val值置为1,如果有说明与前面的某一个冲突。
 3 #include<iostream>
 4 #include<cstdio>
 5 #include<cstring>
 6 using namespace std;
 7 const int MAX=1000000;
 8 const int CON=10;
 9 int nod[MAX][CON],val[MAX];
10 int sz;
11 void init()
12 {
13     sz=1;
14     memset(nod[0],0,sizeof(nod[0]));
15     val[0]=0;
16 }
17 void insert(char s[])
18 {
19     int len=strlen(s);
20     int rt=0;
21     for(int i=0;i<len;i++)
22     {
23         int id=s[i]-‘0‘;
24         if(nod[rt][id]==0)
25         {
26             memset(nod[sz],0,sizeof(nod[sz]));
27             nod[rt][id]=sz;
28             val[sz++]=0;
29         }
30         rt=nod[rt][id];
31     }
32     val[rt]=1;
33 }
34 int search(char s[])
35 {
36     int len=strlen(s);
37     int rt=0,cnt=0;
38     for(int i=0;i<len;i++)
39     {
40         int id=s[i]-‘0‘;
41         if(nod[rt][id]==0)
42         return 0;
43         rt=nod[rt][id];
44         if(val[rt]==1)
45         return 1;
46     }
47 }
48 int main()
49 {
50     char ch[20];
51     int t,n,flag;
52     scanf("%d",&t);
53     while(t--)
54     {
55         init();
56         scanf("%d",&n);
57         flag=0;
58         for(int i=1;i<=n;i++)
59         {
60             scanf("%s",ch);
61             if(flag) continue;
62             flag=search(ch);
63             insert(ch);
64         }
65         if(flag) printf("NO\n");
66         else printf("YES\n");
67     }
68     return 0;
69 }
时间: 11-02

HDU1671 字典树的相关文章

HDU1671 Phone List (字典树)

题目大意: 输入多串数字串,要求判断是否有的数字串是其它串的前缀.如果存在输出NO,否则输出YES. 解题思路: 用trie建立字典树,然后在每个数字串的结尾处标志1,之后每输入一个串,就判断一下.是否有之前的标志记号. #include<iostream> #include<malloc.h> #include<cstring> #include<cstdio> using namespace std; const int MAX_LEN = 11; ty

hdu1671 Phone List [字典树 hash]

传送门 Phone List Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 11633    Accepted Submission(s): 3965 Problem Description Given a list of phone numbers, determine if it is consistent in the sense

HDU1671 Phone List【字典树】

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1671 题目大意: 给你N个字符串,判断这N个字符串中是否存在一个字符串是另一个字符串的前缀,如果存在就 输出"NO",否则输出"YES". 思路: 建立一个字典树,将N个字符串存入字典树中,统计前缀出现次数.再查找这N个字符串,如果 出现字符串出现次数>1,则说明重复出现了两次,就输出"NO".如果都每出现,则输出"YES"

hihoCoder 1014trie树(字典树)

hihoCoder 1014 题目提示已经很清楚了~ 贴代码…… #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXN = 100000 + 10; const int alNum = 26; struct Node{ int cnt; int next[alNum]; void init(){ memset(next,-1,sizeof(

字典树板子

基本的操作 1.定义(即定义结点) next是表示每层有多少种类的数,如果只是小写字母,则26即可,若改为大小写字母,则是52,若再加上数字,则是62了,这里根据题意来确定. cnt可以表示一个字典树到此有多少相同前缀的数目,这里根据需要应当学会自由变化. 1 struct node{ 2 int cnt; 3 struct node *next[26]; 4 node(){ 5 cnt=0; 6 memset(next,0,sizeof(next)); 7 } 8 }; 2.插入(即建树过程)

hdu 1251 统计难题(字典树)

Problem Description Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀). Input 输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 注意:本题只有一组测试数据,处理到文件结束. Output 对于每个提

51nod round3# 序列分解(折半枚举+字典树)

小刀和大刀是双胞胎兄弟.今天他们玩一个有意思的游戏. 大刀给小刀准备了一个长度为n的整数序列.小刀试着把这个序列分解成两个长度为n/2的子序列. 这两个子序列必须满足以下两个条件: 1.他们不能相互重叠. 2.他们要完全一样. 如果小刀可以分解成功,大刀会给小刀一些糖果. 然而这个问题对于小刀来说太难了.他想请你来帮忙. Input 第一行给出一个T,表示T组数据.(1<=T<=5) 接下来每一组数据,输入共2行. 第一行包含一个整数n (2<=n<=40且为偶数). 第二行给出n

白话算法与数据结构之【字典树】

1. 什么是trie树 1.Trie树 (特例结构树) Trie树,又称单词查找树.字典树,是一种树形结构,是一种哈希树的变种,是一种用于快速检索的多叉树结构.典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高.      Trie的核心思想是空间换时间.利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的. Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子

[算法系列之二十]字典树(Trie)

一 概述 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种.典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计. 二 优点 利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高. 三 性质 (1)根节点不包含字符,除根节点外每一个节点都只包含一个字符: (2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串: (3)每个节点的所有子节点包含的字符都不相同. 单词列表为"apps&