题解：CF2066B White Magic

E_M_T · 2025-02-15 08:12:20 · 题解

在 dp 上想了一会，然后发现 dp 没前途，然后发现是简单题。

考虑转化题目条件，即对于 i\in [1,n),a_i\ge \operatorname{mex}(a_{i+1},\cdots,a_n)。

其实不转化也能做，只是转化了好观察一点。

然后观察一些性质：

• 没有 0 一定合法，\operatorname{mex}=0。
• 不能存在两个以上的 0，否则前一个 0 不满足上文条件。

于是必须将序列删除至一个 0，留下最前面的 0 一定不劣。

如果留下一个 0 仍不合法，则序列至少要删一个数，为了最优删去 0（否则可能需要删去更多数），如果合法就都不删。

#include<bits/stdc++.h>
#define sd std::
//#define int long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define ff(i,a,b) for(int i=(a);i>=(b);i--)
#define MIN(x,y) (x<y?x:y)
#define MAX(x,y) (x>y?x:y)
#define me(x,y) memset(x,y,sizeof x)
#define pii sd pair<int,int>
#define X first
#define Y second
#define Fr(a) for(auto it:a)
int read(){int w=1,c=0;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) c=(c<<3)+(c<<1)+ch-48;return w*c;}
void printt(int x){if(x>9) printt(x/10);putchar(x%10+48);}
void print(int x){if(x<0) putchar('-'),printt(-x);else printt(x);}
void put(int x){print(x);putchar('\n');}
void printk(int x){print(x);putchar(' ');}
const int N=3e5+10;
int n,a[N],vis[N],pp[N];
void solve()
{
    n=read();
    F(i,1,n+1) vis[i]=pp[i]=0;
    int sum=n,fi=0;
    F(i,1,n)
    {
        a[i]=read();
        if(!a[i])
        {
            if(!fi) fi=i;
            else
            {
                pp[i]=1;
                sum--;
            }
        }
    }
    int fl=0,mex=1;//是否有0以及不考虑0的mex
    ff(i,n,1)
    {
        if(fl&&mex>a[i])
        {
            put(sum-1);
            return;
        }
        if(a[i]<=n) vis[a[i]]=1;
        while(vis[mex]) mex++;
        if(a[i]==0&&!pp[i]) fl=1;
    }
    put(sum);
}
int main()
{
    int T=1;
    T=read();
    while(T--) solve();
    return 0;
}