[GYM102452E] Erasing Numbers

Description

给定一个 (1 sim n) 的排列，(n) 为奇数，每次可以选择位置连续的三个数并且删去其中的最大最小值，保留中位数。问最后可能被留下的数字是哪些。

Solution

考虑转化为判定问题，我们只须要枚举每一个数，并且判断它是否可能被留下。

如果一个数字 (x) 可能被留下，那么它一定是最后剩下的 (3) 个数的中位数。

我们不妨将所有 (<x) 的数字记做 (0)，(>x) 的数字记做 (1)，那么很显然最后剩下的三个数一定是 (0,1,x) 的一个排列。

进一步考虑发现，如果序列中 (0,1) 的个数相等，那么一定可以完成，具体地，只需要不断找到 (0,1) 的分隔点，在这里做一次，一定可以恰好消去一个 (0) 和一个 (1)。

于是只需要考虑是否能将序列转化为 (0,1) 个数相等的序列。

具体地，我们只需要扫描整个序列，用栈维护即可。

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

#define int long long 
const int N = 1000005;
const int dbg = 1; //!!!!!

int n,a[N];

int test(int pos)
{
    int x=a[pos];
    int delta=0;    // 初始状态下 1 的个数 - 0 的个数
    int res=0;      // 可以修改的幅度
    for(int i=1;i<=n;i++)
    {
        if(a[i]>a[pos]) delta++;
        if(a[i]<a[pos]) delta--;
    }
    int cnt=0;      // 栈大小计数
    if(delta==0)
    {
        return 1;
    }
    if(delta>0)     // 要删除 1
    {
        for(int i=1;i<=n;i++)
        {
            if(i==pos) 
            {
                cnt=0;
                continue;
            }
            if(a[i]>a[pos]) 
            {
                cnt++;
                if(cnt>=3) cnt-=2, res+=2;
            }
            else
            {
                cnt--;
                cnt=max(cnt,0ll);
            }
        }
    }
    else            // 要删除 0
    {
        for(int i=1;i<=n;i++)
        {
            if(i==pos) 
            {
                cnt=0;
                continue;
            }
            if(a[i]<a[pos]) 
            {
                cnt++;
                if(cnt>=3) cnt-=2, res+=2;
            }
            else
            {
                cnt--;
                cnt=max(cnt,0ll);
            }
        }
    }
    return res>=abs(delta);
}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++)
    {
        cout<<test(i);
    }
    cout<<endl;
}

signed main()
{
    /*if(dbg)
    {
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    }*/

    ios::sync_with_stdio(false);

    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }

    if(dbg) system("pause");
}