刷题记-XIII

前言

数学大战即将来袭！所以写的少一些，还没怎么看数学呢！

字典树又称前缀树，顾名思义，用公共前缀来存储字符串，优点是效率高，但是缺点也明显，就是每个节点都要有一个next指针数组，极大的浪费内存

字典树可以动态建树，即每个节点都是new出来的，也可以静态建树，即用一个tot变量为每个节点连上一个node数组中的元素，因为ACM追求时间效率，所以本文通篇采用静态建树

动态建树与静态建树

https://www.cnblogs.com/George1994/p/6346790.html

Trie树详解

https://segmentfault.com/a/1190000008877595

不会做的题

POJ 2513 - Colored Sticks

HDU 2846 - Repository

Phone List - HDU 1671

题目大意

给定电话号码，求是否任意一个电话号码都不是其他电话号码的前缀

思路

模板题

一边加入单词一边建树，那么“任意一个电话号码都不是其他电话号码的前缀”就体现在：

①这个单词不是别的单词的前缀： 加入过程中有new一个新结点，说明一定不是别的单词的前缀

②别的单词不是这个单词的前缀： 加入过程中没经过end == true的节点，说明别的单词一定不是它的前缀

统计难题 - HDU 1251

题目大意

OMIT！

思路

这道题太邪门了……选G++过不了题，会Memory Limit Exceeded……选C++才过了

还有，不给范围，天！诛！地！灭！

这道题就是所走过之处，cnt++，然后查询的时候输出cnt就完事了

不过这题get了个点是gets的话，如果为空行，那么str[0]会被它改为NULL

Xor Sum - HDU 4825

题目大意

Omit as well

思路

这题目一开始看上去和Trie树并没有什么关系……

但是不妨想一想，要是异或值最大，就要每一位都和当前的查询的数的对应位相反

所以可以先把所给集合的每一个数以二进制形式存入树中，查询的数取反后查询，如果有这一位，那么就往下执行，如果没有，那就只能先妥协，走另一边，而另一边是一定有节点的，因为我们的数字都是全部位存进去的，而位只能是0和1，所以集合只要非空，一定有一条边可以走到底，不管它是不是妥协的

T9 - POJ 1451

题目大意

题目太长，很想omit

本题其实就是输入法的9键模式

注意本题中相同前缀的机率是相加的（因为这个WA了 T^T）

就这样，基本Omit！

思路

开个数组保存字典，然后建两棵树

第一棵树插入字符串，所走之处把对应字符串的机率加上去，并且写入对应字符串在字典中的位置，这样就得到了前缀机率相加后的字典树

第二棵树插入字符串对应数字，所走之处不断更新当前机率最大对应的字符串在字典中的位置，并更新节点的最大机率

最后问啥查啥，注意走到str[i] == '1'就可以了

（这题真的是模板题嘛？）