这道题与2018年十二省联考中的异或粽子很相像,可以算作一个简易版;
因为这不需要可持久化;
也就是说求任意两个数异或起来的第k大值;
首先把所有数放进trie里。
然后二分答案,枚举每个数,相应地在trie上从高位开始跑,统计答案。
具体做法:当前跑到二进制第k位,已经确定了比k高的位的数字,使得每一位与当前枚举的数的异或等于mid的这一位。
如果mid第k位为0,那么这一位异或为1的一定对答案有贡献,把整个子树的答案加起来。然后继续做下一位。
时间复杂度O(nlog^2n)
#include <bits/stdc++.h> using namespace std; const int maxn=50005,maxm=200005,M=15; typedef long long LL; int n,a[maxn],l,r,mid; LL m,ans,sum[maxm],t; char c; int read() { for (c=getchar();c<'0' || c>'9';c=getchar()); int x=c-48; for (c=getchar();c>='0' && c<='9';c=getchar()) x=x*10+c-48; return x; } void insert(int x,int num,int w) { sum[x]++; if (w<0) return; if ((num&(1<<w))==0) insert(x<<1,num,w-1);else insert(x<<1|1,num,w-1); } int query(int x,int num,int w,int now) { if (w<0) return sum[x]; int t=((num&(1<<w))>0); if ((now&(1<<w))==0) return query(x<<1|t,num,w-1,now)+sum[x<<1|(t^1)]; return query(x<<1|(t^1),num,w-1,now); } bool check(int x) { if (!x) return 1; ans=0; for (int i=0;i<n;i++) ans+=query(1,a[i],M,x); if (ans>=m) return 1; return 0; } int main() { scanf("%d%lld",&n,&m); for (int i=0;i<n;i++) insert(1,a[i]=read(),M); for (l=0,r=(1<<(M+1))-1,mid=r>>1;l<r;mid=l+r>>1) if (check(mid)) l=mid+1;else r=mid; if (!check(l)) l--; printf("%d ",l); fclose(stdin); fclose(stdout); return 0; }