E. Bored Bakry

陷入思维误区的一个题目.

首先肯定知道的是一定是最高位全为$11$,而且长度为偶数是最优,且前面的位异或和为$00$.

那么我在解这个题的时候,因为使用了局部最优,从而忽视了某些情况,导致一直$wawa$而且无法理解别人的代码.

其实这个不能使用$dpdp$.而应该使用贪心.

怎么贪,记录当前位的1的数量,和异或前缀和,显然的是我们必须使得异或前缀和都为0才能使得我们的条件成立,那么我们就记录每个异或值出现的位子就好了,判断是不是要更新,无非就是判断是不是这段是不是出现了0,出现了0就随着更新就好了,然后判断下这位1的数量是不是满足全为1且是偶数.

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int mod=1e9+7;
const int N=2e6+5;
const int M=2;

int n;
int a[N];
int x[N],num[N],pre[N];

void run()
{
	//不超过1<<20 
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int ans=0;
	int m=20;
	for(int i=20;i>=0;i--)
	{
		for(int j=1;j<=n;j++)	num[j]=num[j-1]+(a[j]>>i&1),x[j]^=((num[j]&1)<<i);
		memset(pre,-1,sizeof pre);
		pre[0]=0;
		for(int j=1;j<=n;j++)
		{
			if(pre[x[j]]==-1)	pre[x[j]]=j;
			else
			{
				if(num[j]-num[pre[x[j]]]==j-pre[x[j]])	ans=max(ans,j-pre[x[j]]); 
				else									pre[x[j]]=j;
			}
		}
	}
	printf("%d\n",ans);
}
 
int main()
{
	int T=1;
//	scanf("%d",&T);
	while(T--)	run(); 
	return 0;
}
/*


*/