题解 [ABC328D] Take ABC

cjh20090318 · 2023-11-12 15:07:45 · 题解

因为信仰写了一个 string 的朴素算法上去，然后多了一发罚时，甚至过了很多个点。

题意

给定一个仅含 A、B、C 三个字母的字符串，你需要对其进行操作：

• 每次从最左边找到第一个 \texttt{ABC} 连续子串，然后删掉这个连续子串。

你需要对字符串不断执行操作直到无法找到这样一个连续子串，并输出操作后的字符串。

分析

这样一个操作很类似于括号序列，如果当前字符为右括号且栈顶为左括号就弹出，否则压入。

这道题也一样，如果当前字符为 C 且栈顶为 B，其次为 A，就将两个字符弹出，否则压入 C。

代码

//the code is from chenjh
#include<cstdio>
#include<vector>
using namespace std;
vector<char> v;
int main(){
    for(char c=getchar();'A'<=c&&c<='C';c=getchar()){
        if(c=='C' && v.size()>=2 && v.back()=='B' && v[v.size()-2]=='A') v.pop_back(),v.pop_back();//在元素数量足够的情况下判断。
        else v.push_back(c);//压入该字符。
    }
    for(const char c:v) putchar(c);//输出当前字符串。
    return 0;
}