E. Bored Bakry 题解(二进制+思维)

题目链接

题目思路

第一眼以为是二分，但是发现倒了

那么就肯定是和二进制有关

其实差不多能发现性质

就是必须为偶数，并且这个区间的第k位二进制全部为1，且位数大于k位的二进制数，异或起来都为0就行

但是感觉写起来没那么简单，看了一下一个大佬的写法，一下就解决了

我的复杂度多了一个log，其实可以不用map，但是我懒。。

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e6+5,inf=(1ll<<31)-1,mod=1e9+7;
const double eps=1e-6;
int n;
int a[maxn];
vector<int> tmp;
int cal(){
    int len=0,val=0;
    map<int,int> mp1,mp2;
    mp2[0]=0;
    // 一个放奇数，一个放偶数
    for(int i=0;i<tmp.size();i++){
        val^=tmp[i];
        if(i%2==0){
            if(mp1.count(val)){
                len=max(len,i+1-mp1[val]);
            }
            if(!mp1.count(val)){
                mp1[val]=i+1;
            }
        }else{
            if(mp2.count(val)){
                len=max(len,i+1-mp2[val]);
            }
            if(!mp2.count(val)){
                mp2[val]=i+1;
            }
        }

    }
    return len;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int num=0,ans=0;
    for(int i=20;i>=0;i--){
        num+=(1<<i);
        for(int j=1;j<=n;j++){
            if(a[j]&(1<<i)){
                tmp.push_back(a[j]&num);
            }else{
                ans=max(ans,cal());
                tmp.clear();
            }
        }
        ans=max(ans,cal());
        tmp.clear();
    }
    printf("%d
",ans);
    return 0;
}