题目链接: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;
}
Comments | NOTHING