[ABC328D] Take ABC 题解

题目大意：

给你一个字符串 \(s\)。你要在其中找到多少个 ABC 的子串，例如 AABCBC 算两个，删掉中间的 ABC 后，前面的和后面的加起来也是一个 ABC，所以就算两个。

思路分析：

首先很容易写出暴力，把一个 ABC 提取出来后把后面的元素往前移，然后再重复操作，但是我们发现时间复杂度会卡成 \(O(n^2)\)。\(n\) 指 \(s\) 的长度。

于是我们想到用栈来维护，遍历这个字符串，把每一个字符串扔进栈里，设栈顶为 \(bk\)，如果栈中 \(bk-2\) 的位置为 A，\(bk-1\) 的位置为 B，\(bk\) 的位置为 C，那么就是可以组成一个 ABC。这样遍历的时候每一次做一下判断，如果发现存在 ABC，那么就把这对应的栈中位置给删除了即可。

link。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fir first
#define se second
#define endl '\n'
#define debug puts("AK IOI")
using namespace std;
const int N = 2E5+5;
char st[N];int bk,n;
string s;
int main(){
	cin >> s;
	n=s.size();
	s=' '+s;
	for(int i = 1;i <= n;i++){
		st[++bk]=s[i];
		if(bk >= 3 && st[bk-2]=='A' && st[bk-1]=='B' && st[bk]=='C'){
			bk-=3;
		}
	}
	for(int i = 1;i <= bk;i++) cout<<st[i];
	
	return 0;
}