526互联

CF1861C-Queries-for-the-Array-题解

发布时间 2023-12-20 09:08:38作者: jr_inf
title: CF1861C Queries for the Array 题解
date: 2023-09-06 07:53:53
categories: 
 - 题解

因为插入和删除操作都在队尾，所以对序列前缀分析一下：

  1. 若一个序列的答案为 YES，那么它前缀的答案也为 YES。（对于没检查过的序列）
  2. 若一个序列的答案为 NO，那么它前缀的答案不确定。（对于没检查过的序列）
  3. 若一个序列的某个前缀的答案为 NO，那么它的答案为 No。

根据第一点，维护最后一个答案为 YES 的前缀的下标；根据二、三点，维护第一个答案为 NO 的前缀的下标。对于四种情况分讨即可。

code：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int iinf=2147483647;
const int N=2e5+10;
int t,len,min0,max1,nl;
bool flag;
char ch[N];
signed main()
{
	scanf("%d",&t);
	while(t--)
	{
		flag=0;
//    最后YES    首个No   序列长
		max1=-1,min0=iinf,nl=0;
		scanf("%s",ch);
		len=strlen(ch);
		for(int i=0;i<len;i++)
		{
			if(ch[i]=='+')nl++;
			if(ch[i]=='-')
			{
				if(max1==nl)max1--;
				if(min0==nl)min0=iinf;
				nl--;
			}
			if(ch[i]=='0')
			{
				if(nl<=1||max1==nl)
				{
					flag=1;
					break;
				}
				min0=min(min0,nl);
			}
			if(ch[i]=='1')
			{
				if(nl>1&&min0<=nl)
				{
					flag=1;
					break;
				}
				max1=nl;
			}
		}
		if(flag)puts("NO");
		else puts("YES");
	}
}