「题目描述」

给定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++中的“^”。

「输入格式」

第一行2个正整数 n,k，如题所述。

以下n行，每行一个非负整数表示A[i]。

「输出格式」

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

「样例输入」

4 5

1

1

3

4

「样例输出」

0 2 2 5 5

「样例解释」

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

「数据范围」

第一个数据点，n <= 1000；

第二个数据点，k = 1；

对于40%的数据，n <= 10000； k <= 10；

对于60%的数据，n <= 20000；

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

0 <= A[i] < 2³¹

「题解」

做法很多。。。有什么可持久字典树之类的真是高贵啊

我的做法比较坑。。。

从最高位开始，将该位0和1的分成俩组

不同组的异或值肯定比同组的大

这样每层扫一遍分俩半，递归下去30层，那么可以算出每层每块内自我匹配所能产生的数

从上往下扫每一层，如果某一层小于k那么就将前一层产生的数全部拿出来排序

因为数据是随机的所以这样就可以了。。。

但是zgg告诉我们，复杂度其实是有保证的

如果某层产生数小于k个，那么前一层不会超过2k个，所以排序复杂度是klogk

总复杂度30n+klogk

如果有手动构造的数据应该要特判最后一层如果某一块的平方大于k，直接输出k个0