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.具体解释见代码注释。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz