【Codeforces】 CF1870E Another MEX Problem

题目链接

CF方向
Luogu方向

题目解法

解法1
考虑优化 $dp$ 转移次数，即只转移有用的区间
不难发现， $mex(l,r)=mex(l+1,r)$ 或 $mex(l,r)=mex(l,r-1)$，那么区间 $[l,r]$ 就没用
考虑证明剩下有用的区间个数是 $O(n)$ 的
若 $[l,r]$ 是有用的，我们不妨令 $a_l>a_r$
如果有 $R>r$ 且满足 $[l,R]$ 是有用的，且 $a_l>a_R$
根据上面的定义，$mex(l,r)>a_l$，不然可以踢掉 $l$，所以 $a_R<mex(l,r)$，那么 $r$ 就没有加的必要
所以对于 $a_l>a_r$，有用的 $r$ 只有一个
对于 $a_l<a_r$ 同理，$a_l=a_r$ 随便删去 $l,r$ 都比 $[l,r]$ 优
所以剩余的区间个数是 $2n$ 个
直接 $dp$ 即可

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=5100;
int mex[N][N],cnt[N],a[N];
bool ok[N][N<<1];
vector<int> trans[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
void work(){int n=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++){int curmex=0;for(int j=i;j<=n;j++){cnt[a[j]]++;while(cnt[curmex]) curmex++;mex[i][j]=curmex;}for(int j=0;j<=n;j++) cnt[j]=0;}for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) if(mex[i][j]!=mex[i+1][j]&&mex[i][j]!=mex[i][j-1]) trans[j].pb(i);ok[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=n<<1;j++) ok[i][j]=ok[i-1][j];for(int j:trans[i]) for(int k=0;k<=n<<1;k++) if(ok[j-1][k]) ok[i][k^mex[j][i]]=1;}for(int i=n<<1;;i--) if(ok[n][i]){ printf("%d\n",i);break;}for(int i=1;i<=n;i++) trans[i].clear();
}
int main(){int T=read();while(T--) work();fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

解法2
我们发现 $mex$ 的上界是 $2n$
所以我们考虑 $g_i$ 表示异或 $mex$ 和为 $i$ 最少需要的前缀长度
显然 $g_i$ 可用类似最短路的方式实现
但这样会多一个 $log$，因为值域较小，开 $n$ 个 $vector$ 存最优位置对应的异或 $mex$ 值即可