Codeforces Round #746 (Div. 2) E – Bored Bakry解题报告

发布于 2021-11-15  1018 次阅读


题目链接:https://codeforces.com/contest/1592/problem/E

这也是一个及其优雅的暴力。枚举最后按位与之后的最高位k,对于每一个i要找到一个左端点j(j<i),使这之间每一个数字的k位,大于k位的所有位最后异或完等于0,具体实现过程我的文字难以表述。看代码吧

其实上述我都想出来了,但是写不出来2333333333

#include <bits/stdc++.h>
using namespace std;
int a[1000005],ans;
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int k=19;k>=0;k--){
		int mask=(1<<20)-(1<<k);
		vector<int>pre(n+5);
		map<int,int>cnt;
		int l=1;
		for(int i=1;i<=n;i++){
			pre[i]=pre[i-1]^(mask&a[i]);
			if(a[i]&(1<<k)){
				if(l==-1) l=i;
				if((cnt[pre[i]]||pre[i]==0)&&cnt[pre[i]]+1>=l){
					ans=max(ans,i-cnt[pre[i]]);
				}
			}
			else{
				l=-1;
			}
			if(l==-1||cnt[pre[i]]+1<l||(cnt[pre[i]]==0&&pre[i]!=0)) cnt[pre[i]]=i;
		}
	}
	printf("%d",ans);
	return 0;
}

回忆这理想不够理想,沿途逛世间一趟只有向上