E. Bored Bakry

E. Bored Bakry

题意:给定一个长度为 n 的序列 an ,找出最长的 good 子序列的长度。当一个序列 al-r 满足它的 & 大于它的 ^ 时,我们称该序列是 good 序列。

分析:来分析一个 good 序列性质。

  • 不妨设一个序列的 & 为 X ,一个序列的 ^ 为 Y 。
  • X > Y 即存在 i 使得在大于 i 的位上 X 与 Y 相等,在第 i 位上 X 大于 Y 。也就是说 Xi 为 1 ,Yi 为 0 。
  • 进一步可以发现这个序列一定是偶数长度的。这说明:对于某一比 i 高的 j 位,Xj = Yj = 0 ,因为Xj = Yj = 1 是不可能的。
  • 具体操作时,我们枚举每一个二进制位 i 。如果一个序列 al-r 的第 i 位全部为 1 ,且对于任意 j ≥ i ,j 位上的异或和都为 0 ,则该序列是 good 序列。
  • 现在有一个问题我们没有保证 Xj 也必须为 0 。其实这已经没有必要了,因为主要的要求 X > Y 已经被满足了。
E. Bored Bakry
#include<bits/stdc++.h>
#define ll long long
#define ls u<<1
#define rs u<<1|1
#define mm(x) memset(x,0,sizeof(x))
#define debug(x) cout << #x << ":" << x << '\n'
using namespace std;
int read()
{
    int a=0;int f=0;char p=getchar();
    while(!isdigit(p)){f|=p=='-';p=getchar();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
    return f?-a:a;
}
const int INF=998244353;
int T;
int n;
int ans;
int val[1000050];
int vval[1000050];
int sum[1000050];
bool vis[1000050];
int tmp[2000050];
int tim[2][2000050];
queue<int >q;
void init()
{
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        tmp[sum[u-1]]=INF;
    }
}
int main()
{
    n=read();    ans=0;
    for(int i=1;i<=n;++i)    val[i]=read();
    memset(tmp,127,sizeof(tmp));
    for(int k=1<<20;k>=1;k>>=1)
    {
        for(int i=1;i<=n;++i)
        {
            vval[i]^=(val[i]&k);
            if(val[i]&k)    vis[i]=1;
            else    vis[i]=0;
        }
        for(int i=1;i<=n;++i)    sum[i]=sum[i-1]^vval[i];
        init();
        for(int i=1;i<=n;++i)
            if(!vis[i])
            {
                init();
            }
            else
            {
                q.push(i);
                tmp[sum[i-1]]=min(tmp[sum[i-1]],i-1);
                ans=max(ans,i-tmp[sum[i]]);
            }
    }
    printf("%d",ans);
    return 0;
}
View Code

 

上一篇:MarkDown语句学习


下一篇:CF1385D a-Good String(分治)