题意:给定一个长度为 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 已经被满足了。
#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