hdu 1671&& poj 3630 (trie 树应用)
Phone List
Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 25280 Accepted: 7678 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:
- 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.
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
98346Sample Output
NO
YESSource
为何感觉一用指针就各种力不从心?
题意:t组实例,每组n个号码,判断里面号码是否有谁是谁的前缀,如果有则输出”NO“,否则“YES”;
亮点:插入新单词时给每个分支的结束处加一个结束标志,那么便出现了两种情况1.之前单词顺着这个分支走还没结束,而新插入的单词到这里结束了,说明新单词与旧单词重叠,则说明冲突,2.新插入单词未结束,而旧单词在这个节点结束了,说明旧单词是新单词的前缀,判断直接结束,冲突了~
#include<iostream>
#include<vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <math.h>
#include<algorithm>
#define ll long long
#define eps 1e-8
using namespace std;
int p;
struct nodes
{
int cnt;
struct nodes *next[];
}* root,*temp,treenodes[];//静态申请节点比较省时间,也可以不用释放内存 int inserts(char word[])
{
nodes *cur = root;
int i = ;
while(word[i] )
{
int t = word[i] - '';
if(cur->next[t] )
{
if(cur->next[t]->cnt == || word[i + ] == '\0')//这里的结束条件最容易出错,关键也在这里
return ;
}
else
{
temp = &treenodes[p++];
temp->cnt = ;
for(int i = ; i < ; i++)
{
temp->next[i] = NULL;
}
cur->next[t] = temp;
}
cur = cur->next[t];
//printf("%d %c\n",cur->cnt,word[i]);
i++;
}
cur->cnt = ;
//printf("%d %c\n",cur->cnt,*word);
return ;
} int main(void)
{
int t,n,ans,last;
char phonenum[];
scanf("%d",&t);
while(t--)
{
p = ;
scanf("%d",&n);
root = &treenodes[p++];
root->cnt = ;
for(int i = ; i < ; i++)
{
root->next[i] = NULL;
}
last = ;
for(int i = ; i < n; i++)
{
scanf("%s",phonenum);
if(last)//如果只前的电话号码已经冲突,則不再插入新节点~
ans = inserts(phonenum);
if(ans == )
last = ;
}
if(last)
printf("YES\n");
else
printf("NO\n");
}
return ;
}
最新文章
- phpcmsv9自定义sql语句查询模型实现
- STL练习题续
- stanford coursera 机器学习编程作业 exercise 3(逻辑回归实现多分类问题)
- (转)The Road to TensorFlow
- Javascript模板及其中的数据逻辑分离思想(MVC)
- UMl概述(转)
- WPF属性与特性的映射(TypeConverter)
- 使用SeekBar办Android调色板
- spark java 代码example
- 1、Sencha cmd学习笔记(一) 使你的sencha cmd跑起来
- HTML 相同name 传递一个数组
- Docker实战--部署简单nodejs应用
- 走近webpack(1)--多入口及devServer的使用
- js中一个对象中遇到一个相同的key所对应的value值相加
- 作业二:构建swap函数
- IIS7常见错误及解决方法
- python基础之Day15
- PostgreSql 函数
- python下graphviz安装
- image_Magic