自动搬运

查看原文

来自洛谷，原作者为

	pigstd Hello, the cruel world.

搬运于2025-08-24 22:24:21，当前版本为作者最后更新于2020-08-29 19:29:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的阅读体验

对于每一个$a$和$k$，在二进制下，若前$1$到$j - 1$位异或出来的值都相同，那么对于第$j$位：

• $k_{j} = 0$：那么$x_{j}$只能为$a_{j}$

• 如果$k_{j} = 1$，那么$x_{j}$有两种取值：

  • .$x_{j} = a_{j}$ 然后后面取什么都可以

  • .$x_{j}= a_{j}\oplus 1$ 那么第$j$位异或出来的值也相同，继续枚举下一位即可

那么$x$的取值范围一定是一段区间，差分即可

（$x_{j}$为$x$在二进制下的第$j$位，其他同理）

code:

#include<bits/stdc++.h>
using namespace std;

const int M=1e6+10;
int c[M*2],a[M],n,k,ans,maxn;
int s1[50],s2[50]; 

void f(int b)
{
	memset(s1,0,sizeof(s1));
	memset(s2,0,sizeof(s2));
	int len1=0,len2=0,kk=k;
	while(b)
		s1[++len1]=b%2,b/=2;
	while(kk)
		s2[++len2]=kk%2,kk/=2;
	int len=max(len1,len2);
	for (int i=1;i<=len/2;i++)
		swap(s1[i],s1[len-i+1]),swap(s2[i],s2[len-i+1]);
	int sum=0;
	for (int i=1;i<=len;i++)
		if (s2[i]==0)
			sum=sum*2+s1[i];
		else
		{
			int k1=(sum*2+s1[i])*1<<(len-i),k2=(sum*2+1+s1[i])*1<<(len-i);
			c[k1]++,c[k2]--;
			sum=sum*2+(s1[i]^1);
		}
	c[sum]++,c[sum+1]--;
}

int main()
{
	scanf("%d%d",&n,&k);maxn=k;
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f(a[i]);
		maxn=max(maxn,a[i]);
	}
	for (int i=1;i<=maxn*2;i++)
		c[i]+=c[i-1];
	for (int i=0;i<=maxn*2;i++)
		ans=max(ans,c[i]);
	cout<<ans;
	return 0;
}