[UVA11362]Phone List

发布于 2018-10-01  47 次阅读


题目

PDF

题解

虽然我很想说这是一道字典树模板题,但是还是有点技巧的。
对于每组输入,我们先把它存入字典树,然后再来查找(也就是所谓的离线)
为了说明方便,用表格说明一下变量吧

变量名 变量作用
\(st\) 保存读入的字符串,用于离线
\(word\) 保存字典树每条边被覆盖的次数,遍历时为1说明不是前缀
\(ch\) 字典树,第一维是编号,第二维是哪条边,值为指向的点
\(sz\) 用来编号,类似于链式前向星里的\(tot\)

关键是遍历的时候,只要word为1就返回0(就是它自己啊),能顺利的走下来就返回1

代码


哇,你居然发现了这里!