codeforces 1030E

68 阅读 0 评论 45 点赞

我是靠谱客的博主激情鲜花，最近开发中收集的这篇文章主要介绍codeforces 1030E，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

根据题意，反正就是随便安排每个数字1的位置了，那么一段区间是good，首先要是1的个数是偶数，因为1个1消掉另一个1，然后就是要一个数的1要用另外一个1去消掉，所以最多的1不能比所有1的一半大，那么这个区间是good的。

又考虑到b[i]（每个数字1的个数）是1到63的，所以以每个i为左端点，只要for循环遍历j<=i+63，sum[j]-sum[i-1]%==0，2*mx<=sum[j]-sum[i]就行了，因为大于j的所有sum[j]-sum[i]都一定比2*mx要大，那么只要满足sum[j]-sum[i-1]%2==0就行了，这个预处理一蛤。

#include<bits/stdc++.h>
#define maxl 300010

using namespace std;

int n;
long long ans;
long long a[maxl],b[maxl],sum[maxl];
int f[maxl][2];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]),b[i]=__builtin_popcountll(a[i]);
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+b[i];
		if(sum[i]&1)
			f[i][1]=f[i-1][1]+1,f[i][0]=f[i-1][0];
		else
			f[i][0]=f[i-1][0]+1,f[i][1]=f[i-1][1];
	}
	ans=0;
	long long mx,tmp;
	for(int i=1;i<=n;i++)
	{
		mx=0;
		for(int j=i;j<=i+63 && j<=n;j++)
		{
			mx=b[j]>mx?b[j]:mx;
			if((sum[j]-sum[i-1])%2==0 && sum[j]-sum[i-1]>=mx*2)
				ans++;
		}
		if(i+63<n)
		{
			if(sum[i-1]&1)
				ans+=f[n][1]-f[i+63][1];
			else
				ans+=f[n][0]-f[i+63][0];
		}
	}
	printf("%lldn",ans);
}