hdu 6059 | 2017 Multi-University Training Contest – Team 3 Kanade’s trio (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]的个数。

我们可以从1..n,依次插入a[k]到trie中,插入时,顺便用num[i][j]统计二进制第i位为j的数的个数。

当要插入a[k]时,a[1]..a[k-1]已经插入到了trie中。

trie上统计当某个节点,该位为0的数的个数和该为为1的数的个数。

需要注意这样统计出的数并不能保证i<j (但是可以保证i<k。。。)

因为我们的trie需要额外维护一部分ext.具体解释见代码注释。

 

 

poj 2001 Shortest Prefixes (trie树)

poj 2001 题目链接

题意:给出n个字符串的表,问每个字符串的简化表示。简化表示的要求是,以该字符串的最短的而且不能产生歧义的前缀来表示。

思路:字典树,多一个cnt属性,每次insert的时候,路过的每个节点的cnt++

find的时候从root往下扫。。遇到的cnt为1的节点结尾的字符串。。就是该单词的唯一表示。。。

按照这个思路写了一发。。。1A好开心哈哈哈

 

poj 3630 Phone List (带删除操作的静态trie树模板题)

poj 3630 题目链接

题意:给出n个字符串,问是否满足所有的字符串都不以其他的字符串为前缀。

思路:字典树,先建树,然后每次查找的之前先删掉自己,找完以后再加回来。

以及这题动态建艹不过。。。学习了一下静态建树的写法。。。第一次写静态的写法。。。可以当做模板用。。。

 

hdu 1247 Hat’s Words (trie树)

hdu 1247 题目链接

 

题意:给出n个字符串的单词表,输出所有的字符串a,满足字符串a是由n中另外两个字符串拼接成的。

思路:字典树。。其实我一开始想出了正解。。。。就是分割一个单词然后分别在trie上查找。。。但是由于题目坑爹得没给单词的长度这个数据范围。。并不是很敢写2333。。。看了下题解发现就是这么做。。。然后写了下1A。。。

不给数据范围玩个鸟啊。。。

 

 

hdu 5536 || 2015 长春区域赛 J Chip Factory (带删除操作的trie树)

hdu 5536 题目链接

题意:给出n个数,然后问最大的(a[i]+a[j])^a[k]  (i,j,k互不相同)

思路:异或和最大很容易想到字典树。。但是如何保证i,j,k互不相同这里没有想明白。。。。。我的想法是加一个标记代表之前的id,但是我加的标记是只有在叶子节点上才有的。。。也就是会出现走到了最后一步才发现这个节点是不能走的情况。。。

正确的做法是,加一个cnt标记。

每次插入的时候,这个数从根节点到叶子节点每个节点的cnt都+1

删除的时候做就是每个节点的cnt都-1.

这样子每次Find的时候只走cnt>0的点。。

 

这种做法的正确性基与:

两个不同的数。。一定有至少一位的二进制数不同。。。保证了当只出现过一次的数x被删掉以后,其他的数y的存在不会导致经过x的路径

两个相同的数,每一位二进制数位都是相同搞的。  保证了id不同的相同的数。。即使一个被删掉。。另外的也可以继续访问。。。因为cnt仍然是大于0的。。。

 

 

 

hdu 4828 Xor Sum (trie 树模板题,经典应用)

hdu 4825 题目链接

题意:给定n个数,然后给出m个询问,每组询问一个数x,问n中的数y使得x和y的异或和最大。

思路:字典树。。把每个数转化成二进制,注意补全前导0,使得所有数都有相同的位数。

如果想要异或和最大,那么每一位尽可能都是1.

所以做法是,先构建字典树,然后每次find的时候,尽可能按照和当前寻找的数的位相反的位的方向走(如果有的话)

比如当前位是1,那我就往0的方向走。

需要注意的是,多组数据,每次要重新初始化一遍。

做法是 在struct 中重新 root = new Node() 一下。。这样就重新调用了Node中初始化用的构造函数。

 

 

 

hdu 1251 统计难题 (trie树模板题)

hdu 1251 题目链接

题意:先给一个单词表,然后给出若干查询,每个查询一个单词,问单词表中以这个单词为前缀的单词的个数。

思路:trie树裸题。第一次写trie树。。感觉要注意的是trie树是一个比较耗费空间的数据结构。。? 以及动态开辟内存记得free…?