bzoj 4245: [ONTAK2015]OR-XOR【按位贪心】

知道按位贪心但是不知道怎么贪……

求一个a的异或前缀和s，然后按位从大到小贪心，ans的当前位能为0的条件是s中有>=m个位置这一位为0且没有flag，并且s[n]的这一位为0

如果符合要求，那么把s中这一位不为0的位置都打上flag，表示这些点不能作为区间断点了（如果作为断点的话这一位就要为1了，显然不优）

否则只能ans|=(1ll<<i)了

#include<iostream>

#include<cstdio>

using namespace std;

const int N=500005;

long long n,m,a[N],s[N],ans;

bool f[N];

long long read()

{

	long long r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<=n;i++)

		a[i]=read(),s[i]=s[i-1]^a[i];

	for(int i=62;i>=0;i--)

	{

		int con=0;

		for(int j=1;j<=n;j++)

			if(!f[j]&&!(s[j]&(1ll<<i)))

				con++;

		if(con>=m&&!(s[n]&(1ll<<i)))

		{

			for(int j=1;j<=n;j++)

				if(!f[j]&&(s[j]&(1ll<<i)))

					f[j]=1;

		}

		else

			ans|=(1ll<<i);

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

bzoj 4245: [ONTAK2015]OR-XOR【按位贪心】

最新文章

热门文章