首页 > 题解 > bzoj 3689 异或之

bzoj 3689 异或之

Description

给定n个非负整数A[1], A[2], ……, A[n]。
对于每对(i, j)满足1 <= i < j <= n,得到一个新的数A[i] xor A[j],这样共有n*(n-1)/2个新的数。求这些数(不包含A[i])中前k小的数。
注:xor对应于pascal中的“xor”,C++中的“^”。

Input

第一行2个正整数 n,k,如题所述。
以下n行,每行一个非负整数表示A[i]。

Output

共一行k个数,表示前k小的数。

Sample Input

4 5

1

1

3

4

Sample Output

0 2 2 5 5

HINT

【样例解释】

1 xor 1 = 0 (A[1] xor A[2])

1 xor 3 = 2 (A[1] xor A[3])

1 xor 4 = 5 (A[1] xor A[4])

1 xor 3 = 2 (A[2] xor A[3])

1 xor 4 = 5 (A[2] xor A[4])

3 xor 4 = 7 (A[3] xor A[4])

前5小的数:0 2 2 5 5

【数据范围】

对于100%的数据,2 <= n <= 100000; 1 <= k <= min{250000, n*(n-1)/2};

0 <= A[i] < 2^31

题解

这题感觉很强势啊。

首先是对于每个数拆成01串,建个Trie树。在每个节点上面存下它子树里有多少个is_end。

这样就可以知道每个串的第k小异或值:从Trie树往下走,siz大于k就k减掉siz走另一半,小于就直接按照这个串向下遍历。

考虑维护一个小根堆,先把所有串的第二小的串压到堆里面(第一小是它和它自己),k次取出堆顶的输出,假如这是第x小的那么再把第x+1小的压进去。

但是发现每个串都会出现两次(正着和反着异或相同),那就取出2k次,奇数次的时候输出。


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×