CF1870E Another MEX Problem 题解
Augury
·
·
题解
CF1870E Another MEX Problem 题解
萌新啃了一晚上的官方题解，求管理大大给过/kel
CnBlogs链接
题意
给你一个序列 a，让你选出一些不交的子串，使得它们的 MEX 的异或和最大。
## 思路
考虑 dp。
首先这个东西是异或，不好做最优化 dp。于是我们考虑可行性 dp。
设 $dp_{i,j}$ 表示上一个选的区间的右端点位置 $\le i$ 时，答案是否可以是 $j$。
考虑这个东西怎么转移。我们枚举 $i$，然后枚举 $1\le j\le i$，枚举 $0\le k\le 2n$，从 $dp_{j-1,k\oplus MEX(j,i)}$ 转移到 $dp_{i,k}$。
显然，这样的复杂度是 $O(n^3)$ 的，不可通过。于是我们考虑优化。
我们定义一个东西，叫做好的区间。对于一个区间 $[l,r]$，不存在一个区间 $[l_1,r_1]$，使得 $l\le l_1 \le r_1 \le r$，且 $l\neq l_1$ 或 $r\neq r_1$，且 $MEX(l_1,r_1)=MEX(l,r)$，那么区间 $[l,r]$ 是一个好区间。
有一个结论，就是好区间只有 $O(n)$ 个。
假设我们现在有一个好区间 $[l,r]$，他的 $MEX\neq 0$。我们假设 $a_l>a_r$，因为 $a_l<a_r$ 可以类似地讨论。显然，$a_l\neq a_r$，除非 $a_l=0$。
显然有 $MEX(l,r)>a_l$，因为 $MEX(l,r)$ 肯定不能等于 $a_l$，而且如果 $MEX(l,r)<a_l$，就可以把 $a_l$ 踢出去，那么 $[l,r]$ 就不是一个好区间。
我们假设有一个 $r_1>r$，使得 $[l,r_1]$ 是一个好区间，且 $a_l>a_{r_1}$。
这样可能吗？不可能。因为 $a_l<MEX(l,r),a_{r_1}<a_l$，所以 $a_{r_1}<MEX(l,r)$。这就说明，$a_{r_1}$ 已经在 $[l,r]$ 中出现了，不会产生任何贡献，所以 $[l,r_1]$ 不是一个好区间。
所以我们就证明了，对于每个 $l$，至多有一个 $r$，使得 $a_l>a_r$ 且 $[l,r]$ 是一个好区间。
同时，这也说明了，对于每个 $r$，至多有一个 $l$，使得 $a_l<a_r$ 且 $[l,r]$ 是一个好区间。
而且，如果 $a_i=0$，那么 $i$ 一定不会是上面那两种好区间的端点，但 $[i,i]$ 本身就是一个好的区间，它的 $MEX$ 为 $1$。
综上，好的区间最多只有 $2n$ 个。
那么，我们怎么求出所有好的区间呢？
根据上面的定义，我们对于每个 $l$，找到最小的 $r$，使得 $a_l>a_r$ 且 $MEX(l,r)>a_l$ 即可。反方向也是一样。需要特殊处理一下 $0$。
这样，我们就不用枚举所有区间了，只要枚举好的区间就行了，复杂度 $O(n^2)$。
## 代码
```cpp
#include<bits/stdc++.h>
#define Pi pair<int,int>
using namespace std;
inline int read(){
int ans=0;bool op=0;char ch=getchar();
while(ch<'0'||'9'<ch){if(ch=='-')op=1;ch=getchar();}
while('0'<=ch&&ch<='9'){ans=(ans<<1)+(ans<<3)+(ch^48);ch=getchar();}
if(op)return -ans;
return ans;
}
const int maxn=5010;
int n;
int a[maxn];
int buc[maxn],mex;
vector<Pi>g[maxn];
bool dp[maxn][maxn<<1];
void solve(){
//read
n=read();
for(int i=1;i<=n;i++)a[i]=read();
//clear
for(int i=1;i<=n;i++)g[i].clear();
//init
for(int i=1;i<=n;i++)if(!a[i])g[i].push_back(make_pair(i,1));//特殊处理0
for(int i=1;i<=n;i++){//i是左端点
memset(buc,0,sizeof(int)*(n+5)),mex=0;
for(int j=i;j<=n;j++){
buc[a[j]]=1;
while(buc[mex])++mex;
if(mex>a[i]&&a[j]<a[i]){
g[j].push_back(make_pair(i,mex));
break;
}
}
}
for(int i=1;i<=n;i++){
memset(buc,0,sizeof(int)*(n+5)),mex=0;
for(int j=i;j>=1;j--){//i是右端点
buc[a[j]]=1;
while(buc[mex])++mex;
if(mex>a[i]&&a[j]<a[i]){
g[i].push_back(make_pair(j,mex));
break;
}
}
}
//solve
memset(dp[0],0,sizeof(bool)*((n<<1)+5));
dp[0][0]=1;
for(int i=1;i<=n;i++){
memcpy(dp[i],dp[i-1],sizeof(bool)*((n<<1)+5));
for(Pi j:g[i]){
for(int k=0;k<=(n<<1);k++){
if((k^j.second)<=(n<<1))dp[i][k]|=dp[j.first-1][k^j.second];
}
}
}
for(int i=(n<<1);i>=0;i--){
if(dp[n][i]){
cout<<i<<'\n';
return;
}
}
}
signed main(){//多组数据
int T=read();
while(T--)solve();
return 0;
}
```