CF1861C Queries for the Array

One_JuRuo · 2023-09-02 00:05:20 · 题解

思路

机翻害人，我还以为是 1 和 0 是对原序列排序，害得我比赛的时候都没对，恼。

首先，对于新加入的数字，我们可以先不确定是否有序，而是等到后续的 1 或 0 出现，再确定。

用 num 表示目前有多少数字，用 so 表示确定有序的数字中最后一位的位置，nso 表示确定无序的第一位数字的位置。

那么，我们可以分几种情况讨论：

• 操作 0。

  • 如果满足 so=num，那么目前所有数字都一定排序，所以无解。
  • 如果满足 num<2，按照题意，一定有序，所以无解。
  • 其他情况都可以满足条件，此时对于 [so+1,num] 的数字中有一个数字是无序的就行，这里选择最后一位，因为最后一位更容易被删除，后续满足条件的可能性更大，即 nso=num，注意：如果 nso 本来就有值，代表有更靠前的无序数字，则无需更新 nso。
• 操作 1。
  • 如果此时 nso>1，代表前面有数字一定无序，所以无解。
  • 其他情况都可以满足条件，此时所有数都应该有序，即 so=num。
• 操作 +，为了使后续操作满足条件可能性更大，所以选择添加未知数字，即仅 num+1。
• 操作 -，先减 num，如果此时 num<so，则也要把 so 减一，如果此时 num<nso，则代表无序的数字一定都被删了，所以更改 nso 为 0。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,num,so,flag,nso;
char ch[200005];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",ch+1),n=strlen(ch+1),nso=num=so=flag=0;
        for(int i=1;i<=n;++i)
        {
            if(ch[i]=='+') ++num;
            if(ch[i]=='-') --num,nso=(num<nso)?0:nso,so=min(so,num);
            if(ch[i]=='1')
            {
                if(nso){flag=1;break;}
                so=num;
            }
            if(ch[i]=='0')
            {
                if(num<2||so==num){flag=1;break;}
                if(!nso) nso=num;
            }
        }
        if(flag) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}