【题目描述】
给定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^31
Solution
由于出题人数据是随机生成的就卡不掉我的暴力骗分啦~不过我是构了一组。
很明显，a-b<=a^b<=a+b
先对A[]排序，选取k个可能成为答案的数，用堆或者线段树维护修改和查询。当插进去的数比当前堆中的最大数还大的话就break。
1 #include<cstdio>
2 #include<cstring>
3 #include<cstdlib>
4 #include<ctime>
5 int main()
6 {
7 freopen("xorit.in","w",stdout);
8 srand(time(0));
9 int n=1000,m=2500,mod=1<<30;mod--;
10 printf("%d %d\n",n,m);
11 for(int i=1;i<=n;i++)printf("%d ",rand());
12 }
1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 int t[1000010],d,n,k,a[100010],tmp;
5 int main()
6 {
7 scanf("%d%d",&n,&k);int i,j,l;
8 memset(t,127,sizeof(t));
9 for(d=1;d<k;d<<=1);
10 for(i=1;i<=n;i++)scanf("%d",&a[i]);
11 std::sort(a+1,a+1+n);
12 for(i=2;i<=n;i++)
13 for(j=i-1;j;j--)t[++tmp]=a[i]^a[j];
14 std::sort(t+1,t+1+tmp);
15 for(i=1;i<=k;i++)printf("%d ",t[i]);
16 }
1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 int t[524288],d,n,k,a[100010],cnt,tmp,now;
5 int main()
6 {
7 scanf("%d%d",&n,&k);int i,j,l,o;k++;
8 for(d=1;d<k;d<<=1);
9 for(i=1;i<=n;i++)scanf("%d",&a[i]);
10 std::sort(a+1,a+1+n);
11 for(i=2;i<=n;i++)
12 for(j=i-1;j;j--)
13 {
14 tmp=a[i]^a[j];now=0;
15 for(l=k+d-2;l;l>>=1)now<t[l]?now=t[l]:1;
16 if(now==0&&cnt==k)break;
17 if(cnt<k)
18 {
19 if(now<tmp)now=tmp;
20 for(t[l=d+cnt]=tmp,cnt++,l>>=1;l;l>>=1)
21 {
22 tmp=t[l<<1]>t[l<<1|1]?t[l<<1]:t[l<<1|1];
23 t[l]=tmp;
24 }
25 }
26 else
27 {
28 if(tmp>=now&&a[i]-a[j]>now)break;
29 if(tmp<now)
30 {
31 for(o=1;o<d;t[o<<1|1]==now?o=o<<1|1:o<<=1);
32 if(now<tmp)now=tmp;
33 for(t[o]=tmp,o>>=1;o;o>>=1)
34 {
35 tmp=t[o<<1]>t[o<<1|1]?t[o<<1]:t[o<<1|1];
36 t[o]=tmp;
37 }
38 }
39 }
40 }
41 std::sort(t+d,t+d+k);k--;
42 for(i=d;i<d+k;i++)printf("%d ",t[i]);
43 }
另外还有一种二进制分组的做法。考虑在二进制中前k位相同的数，k+1位对答案的贡献为cnt[0]*cnt[1]，cnt[i]表示k+1位为i的数。
于是我们可以找到第k小的答案范围，然后暴力就行了。复杂度O(nlogn)
还有一种可持久化Trie树的做法--详见Noi超级钢琴