第k大异或值

这道题与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\n",l);

	fclose(stdin); fclose(stdout);

	return 0;

}

巴特西

第k大异或值

最新文章

热门文章