思路
机翻害人，我还以为是 \(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\) 为 \(1\)。
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;
}