Trie

http://acm.hdu.edu.cn/showproblem.php?pid=6059 题意： # 含 N 个数字的 A 数组，求有多少个三元组 (i,j,k) 满足 i<j<k 且a[i]^a[j] < a[j]^a[k] 思路： # 考虑a[i]和a[k]二进制不同位中的最高位，此时满足题意的a[j]是该位与a[i]相同，其他位任意的所有a[j]的个数。

poj 2001 题目链接 题意：给出n个字符串的表，问每个字符串的简化表示。简化表示的要求是，以该字符串的最短的而且不能产生歧义的前缀来表示。 思路：字典树，多一个cnt属性，每次insert的时候，路过的每个节点的cnt++

poj 3630 题目链接 题意：给出n个字符串，问是否满足所有的字符串都不以其他的字符串为前缀。 思路：字典树，先建树，然后每次查找的之前先删掉自己，找完以后再加回来。 以及这题动态建艹不过。。。学习了一下静态建树的写法。。。第一次写静态的写法。。。可以当做模板用。。。

hdu 1247 题目链接 题意：给出n个字符串的单词表，输出所有的字符串a，满足字符串a是由n中另外两个字符串拼接成的。 思路：字典树。。其实我一开始想出了正解。。。。就是分割一个单词然后分别在trie上查找。。。但是由于题目坑爹得没给单词的长度这个数据范围。。并不是很敢写2333。。。看了下题解发现就是这么做。。。然后写了下1A。。。

hdu 5536 题目链接 题意：给出 n 个数，然后问最大的 (a[i]+a[j])^a[k]（i,j,k 互不相同）。 思路：异或和最大很容易想到字典树，但是如何保证 i,j,k 互不相同这里没有想明白。我的想法是加一个标记代表之前的 id，但是我加的标记只有在叶子节点上才有，也就是会出现走到了最后一步才发现这个节点不能走的情况。

hdu 4825 题目链接 题意：给定n个数，然后给出m个询问，每组询问一个数x，问n中的数y使得x和y的异或和最大。 思路：字典树。。把每个数转化成二进制，注意补全前导0，使得所有数都有相同的位数。

hdu 1251 题目链接 题意：先给一个单词表，然后给出若干查询，每个查询一个单词，问单词表中以这个单词为前缀的单词的个数。 思路：trie树裸题。第一次写trie树。。感觉要注意的是trie树是一个比较耗费空间的数据结构。。？ 以及动态开辟内存记得free…？