Problem Link

「LAOI-4」Mex Tower (Hard ver.)

题意

给定一个长度为 $ n $ 的序列 $ a $，求序列的 $ \operatorname{Mex} $ 值是否大于等于其他所有长度为 $ n $ 的自然数序列的 $ \operatorname{Mex} $ 值。

Solution

不难发现，两个数或一个序列的 $ \operatorname{Mex} $ 一定是 $ 0 \(，\) 1 $ 或 $ 2 $。

而要使序列 $ \operatorname{Mex} $ 大于等于其他所有等长序列 $ \operatorname{Mex} $ 值，显然得使序列 $ a $ 本身 $ \operatorname{Mex} $为 $ 2 $，故原问题被转化为“判断原序列 \(\operatorname{Mex}\) 值是否为 $ 2 $”。

暴力求的时间复杂度为 $ n^2 $，显然不行。

想到一句话：“正难则反”。我们无法快速求一个序列的 $ \operatorname{Mex} $ 值。无妨，我们倒推，判断什么样的序列的 $ \operatorname{Mex} $ 值为 $ 2 $。

推导的图如下：

发现只有圈内的数要特判，其他随便填。

按奇偶分类，分别处理即可。

代码

//written by Naught
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define Maxn 3000005
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}

int n, a[Maxn];

int main()
{
    int _ = read();
    while(_--)
    {
        n = read();
        fo(i, 1, n) a[i] = read();
        if( n == 1 )
        {
            if(a[1] == 2) puts("Yes");
            else puts("No");
            continue;
        }
        if( n == 2 )
        {
            if( (a[1] + a[2]) == 1 ) puts("Yes");
            else puts("No");
            continue;
        }
        if(n & 1)
        {
            if(a[n/2+1] < 2) {puts("No"); continue;}
            if( (a[n/2] + a[n/2+2]) != 0 && (a[n/2] * a[n/2+2]) == 0 ) puts("Yes");
            else puts("No");
        }
        else
        {
            if( (a[n/2] == 0 && a[n/2+1] == 1 && a[n/2+2] >= 1) || (a[n/2-1] >= 1 && a[n/2] == 1 && a[n/2+1] == 0) ) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

Tips

记得特判 \(n = 1\) 和 \(n = 2\) 的情况。