【bzoj3689】【FJ2014集训】异或之

2014年7月13日2,1500

【题目描述】

给定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] < 231

【题解】

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

我的做法比较坑。。。

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

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

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

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

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

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

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

总复杂度30n+klogk

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