HDU1251
题意就是统计出以某个字符串为前缀的单词数量，首先构建出trie树并记录每个节点的访问次数，然后在上面查询就好了，模板题。
HDU1251代码
HDU2072
题意就是出现的不同单词个数
直接把字符全部插入Trie树中，然后统计所有具有flagg标记的节点个数就好了。
也可以边插入边统计，如果当前字符串结尾下标已经被标记，就不对答案做贡献，否则ans++.
第二题代码
POJ2001
题意就是求一个能代表这个字符串的最短前缀，也就是只有这个字符串具有的前缀。
做法很显然，我们先构建好Trie树，然后对每个单词进行find，递归到直到节点出现次数为1，表示这个节点只有这一个单词走过，返回就ok。这里我用了string不断拼接字符，然后直接返回，减少了一些代码量。
POJ2001代码
POJ3630
本题题意就是给你一个字符串集合，问你否所有的字符串都不是其他人的前缀。
首先我们构造出Trie树，然后对每个字符串find，当find的路径上如果出现其他字符串结尾标记，就说明其他字符串是当前字符串的前缀。注意这里对每个字符串find的时候只要搜索到即可，如果搜索到，那么将会将本身的字符串统计进去。
POJ3630代码
LightOJ1224
本题题意是让你找出一个字符串，使该字符串作为前缀的次数该字符串的长度结果最大
我们首先构建好trie树，我们利用记录节点出现次数的方式存储，这时候结果就是，对于当前的len也就是递归深度，如果我们要存入所有节点之后再重新扫一遍Trie树复杂度会高很多，所以我们可以在插入字符串的时候进行统计，用一个maxx保存的最大值就好了.具体实现看代码。
LightOJ1224代码
POJ2513
本题题意是给一堆木棒，每种木棒左右两端有两种颜色，木棒进行拼接的时候，只有相同颜色之间才可以拼接，问最后是否可以将所有木棒拼为一根木棒。
我们考虑把同一种颜色的点聚在一起，我们就可以得到一个无向图，如果这个无向图是欧拉图，代表展开之后可以一笔走完，也就是可以连接成一条木棒。所以我们用trie树判断每种颜色出现的次数，再用并查集判一下图是否连通，最后用欧拉图的性质判断一下是否为欧拉图就好了（只存在两个或者0个奇度的点）
POJ2513代码
POJ1451
本题题意比较有意思，大概就是模拟手机输入法，先给你一个用户的词库，即每个单词出现的次数，这个时候再按照九键输入法给你一个数字序列，问你在输入这个序列的过程中，出现的字符串顺序，也就是对于每个数字序列，给出一个最有可能出现的字符串。
这道题我的做法比较巧妙，但是不怎么会算复杂度，还是很快的过去了。首先我们考虑，对于每个数字序列，我们都可以用一个string去映射，这样我们可以用一个map来离线保存每个数字序列对应的最有可能出现的字符串，可是我们怎么知道每个数字序列最有可能出现的字符串是哪个呢，首先我们对单词进行映射，把每个单词映射成数字序列，然后在插入的过程中，对于每一个前缀都更新一下这个前缀对应的map，最后查询的时候就可以直接输出了。
POJ1451代码
POJ1816
本题的题意是给你n个模式串和m个匹配串，模式串中有两种字符，？可以匹配任意一种字符，可以匹配任意个字符，问每种匹配串可以和之前哪些模式串匹配。
我们先构建好字典树，对于每个匹配串实现find，find的时候用类似dfs的写法，如果当前节点的字符或者?存在，直接dfs下一个位置的字符，如果当前字符对应的位置有存在，那么就从匹配串之后的每一个位置进行往下dfs，因为可以匹配任意个字符。而dfs计数的条件是匹配串匹配结束而且达到模式串某个结尾标记。则在这个模式串上做标记。需要注意的细节是此时不能直接return,因为有可能此时的字符串和剩下的匹配串还能匹配，类似模式串A ： AA 模式串B： AA* 匹配串为AAA ,那么匹配到A字符串之后则不能停止，要继续往下搜索。
POJ1816代码
HDU1247
本题题意是问你某个单词是否可以拆成单词表中的其他两个单词。
我们可以建两颗Trie树，然后分别正序倒序插入每个单词，对每个单词查询的时候，我们分别正序倒序查询，对出现过单词的前缀下标进行标记，对每个出现过单词的后缀进行标记，最后扫描标记数组，如果某个位置前缀后缀均被标记过，则表示可以拆成单词表中的两个其他单词。
HDU1247代码
POJ2408
本题题意是，把可以通过重新排列变成相同单词的单词放入一个集合，最后按照集合元素由多到少输出前五个集合，如果集合元素相同，按照字典序由小到大输出
我们考虑，如果两个单词可以通过重新排列组合变成相同单词，那么他们的字典序最小的排列方式一定是相同的，所以我们可以利用每个元素的最小排列方式判定是否在同一个集合，字典树在这里用于判定某个字符串时候出现过。最后用set来保存以便维持字典序
POJ2408代码
HDU1075
本题的题意是给你火星文与地球文的映射方式，然后给你一个火星文组成的文本，若某单词在映射文本中出现过，则输出映射之后的文本。否则输出原文本。
我们可以建立trie树，插入火星文本，将返回的下标pos与地球文相对应，在翻译文本的时候，从前往后截取每一段单词，在trie树上查找该单词是否出过，要注意必须是单词，而不能是某单词的前缀。若找到则返回下标，然后输出该下标对应的地球文，否则返回-1，输出原文本。
HDU1075代码
Lightoj1269
本题的题意是求出一段连续的区间，使这段区间异或和最小/最大。分别输出最大异或值和最小异或值。
区间异或和的题目一般都要用到前缀异或和，我们这里可以预处理出前缀异或和，然后我们考虑，对于每个值，在字典树上查找之前出现过的最优的匹配，利用字典树的特点，将其拆为二进制，贪心的去查找，查找最大值则是0找1，1找0，查找最小值则是1找1，0找0。维护一下最大值与最小值即可。Find的时候可以利用两个不同的root并行查找最大值与最小值，减少代码量。
Lightoj1269代码
未完待续…
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/5359.html