开学大二cf补题

whatdo / 2023-09-03 / 原文

Problem - C - Codeforces

题意：给你一个字符串有加号有减号还有0 和 1 +代表给数组加一个数字在末尾 -代表末尾减一个数，0代表这个数组是一个严格降序的数组 1代表当前这个数组是一个升序数组

问你当他询问0或者1时符不符合条件（如果数组元素小于2那么就是1）

题解：这个首先定-1元素为待定状态 1为这个元素是用来升序的 0代表这个元素是用来打乱升序的就是让这个数组变成0

然后我们开两个栈一个记录数组元素情况一个是用来记录升序个数的

首先+那么我们就把-1到栈里这些都是待定

-我们就弹出队尾

遇到1时检查有多少个-1把他全变成1升序

然后判断（-1全部搞完后）如果遇到0就不行了，不是升序了就NO

如果遇到0 那么如果队尾是1就是升序情况，那我们就无法更改，只有-1这个待定可以改，也就是要打NO了

如果队首是-1那么我们把他变成0就是在升序结尾改一个小的数这样就符合题目条件的0了(刚好破坏1的条件）就是YES

#include <bits/stdc++.h>
#pragma  GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
//#define endl '\n';
using namespace std;
const int N=600,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=998244353;
typedef pair<int,int> PII;


int32_t  main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int  t;
    cin>>t;
    while(t--) {
       string s;
       cin>>s;
      stack<int> st,ck;
      int f=0;
       for(int i=0;i<s.size();i++)
       {
          if(s[i]=='+')
          {
              st.push(-1);
          }
          else if(s[i]=='-')
          {
              st.pop();
          }
          else if(s[i]=='1')
          {
              if(st.size()==1) continue;
              while (!ck.empty()) ck.pop();
              while (!st.empty() && st.top()==-1)
              {
                  st.pop();
                  ck.push(1);
              }
              if(!st.empty() && st.size()>1 && st.top()==0)
              {
                  f=1;
                  cout<<"NO"<<endl;
                  break;
              }
              while (!ck.empty())
              {
                  st.push(ck.top());
                  ck.pop();
              }
          }
          else
          {
              if(st.size()<2)
              {
                  f=1;
                  cout<<"NO"<<endl;
                  break;
              }
              if(!st.empty() && st.size()>1 && st.top()==1)
              {
                  f=1;
                  cout<<"NO"<<endl;
                  break;
              }
              st.pop();
              st.push(0);
          }
       }
       if(f==0)
       {
           cout<<"YES"<<endl;
       }
    }

    return 0;
}