【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 
#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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