uva 12526 Cellphone Typing

本文从WordPress迁移而来, 查看全部WordPress迁移文章

字典树

题意:给出一系列的单词,然后可以打字,系统会有一个自动补全功能,你需要统计出每个单词分别要敲击多少次键盘,然后算一下平均值输出即可。对于每个单词怎么计算要敲击多少次功能和怎么补全,看下面

1
2
3
4
hell
hello
heaven
goodbye

如果敲击了g,那么整个goodbye就补全了,因为第1个字母为g的单词只有1个,所以goodbye这个单词只需要敲一次键盘。敲打了h,自动补全e,因为h后面全部跟了e,但是不能再继续补全下去,是因为e后面可能跟l或a。如果敲了a,那么整个heaven就补全了,因为a这里只有1种可能,所以heaven这个单词敲了两次键盘,分别是h,a;如果敲l,那么自动补全一个l,因为hel后面一定跟l,但是不能补全o,因为hell可能是一个单词结束了,也可能还跟着一个o,所以hell这个单词敲了2次键盘,h,l;hello则敲了3次,h,l,o,最后那个o要自己敲上去

其实就是一个裸的字典树Trie,建好树后,对于每个单词查询一次。对于树中一个节点,如果有多于一个儿子,则要计数一次,如果只有1个儿子不同计数

注意处理单词的结束。注意如果字典中只有1个单词,那么应该输出1,第1个字符敲进去,然后整个单词补全了

第一次写Trie,写得不好,加了很多注释,下次搞个模板出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 8000010
#define N 100010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,son[MAX];
char str[N][80]; //字典
struct Trie{
char ch; //其实并不需要记录整个Trie里面每个位置放什么字符,用于debug
int next[30]; //指针,最多只需要26个指针
}a[MAX]; //保存整个树

inline void init_trie(){
//第一个位置0是根节点,根节点不保存任何字母
//先创建了根节点,下面没有儿子,所以根节点的26个指针全部初始化为-1
//根节点没有儿子,记录其有几个儿子的son数组也初始化为0
//son并不是Trie模板里面需要的信息,只是为了解决这题
tot = 1; son[0] = 0; a[0].ch = '#';
cl(a[0].next,-1);
}

inline void init_node(int pos){
son[pos] = 0;
cl(a[pos].next,-1); //新节点,还没有儿子,所以儿子指针都初始化为-1
}

void insert(char *s){
int fa = 0,child; //fa = 0,表示每次都从根节点开始遍历下来
for(int i = 0; s[i]; i++){
child = s[i] - 'a';
if(a[fa].next[child] == -1){ //还没有字符s[i]这个儿子
son[fa]++; //新增一个儿子
a[tot].ch = s[i];
a[fa].next[child] = tot; //指针指向这个儿子的位置tot
init_node(tot); //初始化儿子这个节点
tot++;
}
fa = a[fa].next[child]; //向下遍历来到儿子
}
son[fa]++;
}

int query(char *s){
int res = (son[0] == 1 ? 1:0);
int fa = 0,child;
for(int i = 0; s[i]; i++){
child = s[i] - 'a';
if(son[fa] > 1) res++;
fa = a[fa].next[child];
}
return res;
}

void travel(){
for(int i = 0; i < tot; i++)
printf("%c ",a[i].ch);
puts("");
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 0; i < n; i++)
scanf("%s",str[i]);

init_trie(); //非整个trie初始化

for(int i = 0; i < n; i++)
insert(str[i]); //先将每个单词插入到Trie中

// travel(); //遍历Trie,用于debug

int sum = 0;
for(int i = 0; i < n; i++){
int res = query(str[i]);
sum += res;
//cout << res << endl;
}
printf("%.2lf\n",(double)sum/((double)n));
}
return 0;
}