首页 > ACM题库 > HDU-杭电 > HDU 1671 Phone List-字典树-[解题报告] C++
2013
12-21

HDU 1671 Phone List-字典树-[解题报告] C++

Phone List

问题描述 :

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.

输入:

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.

输出:

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

http://acm.hdu.edu.cn/showproblem.php?pid=1671

注意每次要删除字典树,要不然会超内存

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct node
{
    int count;
    node *next[10];
    node():count(0){memset(next,0,sizeof(next));}
};
node *root;
node *b[10003];
int k=0;
void insert(char *a)
{
    int l=strlen(a);
    node *p=root;
    int i;
    for(i=0;i<l;i++)
    {
        if(p->next[a[i]-'0']==0)
        {
            p->next[a[i]-'0']=new node;
        }
        p=p->next[a[i]-'0'];
        p->count++;
    }
    b[k++]=p;
}
int check(int n)
{
    int i;
    for(i=0;i<k;i++)
    {
        if(b[i]->count!=1)
            return 1;
    }
    return 0;
}
void de(node *p)
{
    if(p==0)
        return ;
    int i;
    for(i=0;i<10;i++)
    {
        de(p->next[i]);
    }
    delete p;

}
int main()
{
    int t;
    scanf("%d",&t);
    char a[15];
    while(t--)
    {
        root = new node;
        int n;
        k=0;
        scanf("%d",&n);
        int i;
        for(i=0;i<n;i++)
        {
            scanf("%s",a);
            insert(a);
        }
        if(check(n))
            printf("NO\n");
        else
            printf("YES\n");
        de(root);
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/juststeps/article/details/8600085


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  3. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  4. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  5. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  6. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。