[ABC328D] Take ABC 题解

发布时间 2023-11-24 19:35:08作者: gsczl71

题目大意:

给你一个字符串 \(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;
}