题解：B4218 [常州市程序设计小能手 2023] ABC 字符串

lizeyuhello · 2025-03-15 16:37:29 · 题解

赛时脑子抽了，只写了暴力。

题解

我们首先考虑，如果把一个 \texttt{ABC} 变成 \texttt{BCA}，会对答案产生什么新的贡献。

我们可以考虑将一个字符串分成三个部分：\texttt{A}，\texttt{BC}，和其他部分。当你将 \texttt{ABC} 中的 \texttt{BC} 换到A前面时，这个 \texttt{BC} 可能会和前面的 \texttt{A} 结合再次贡献答案。而被换到后面的 \texttt{A} 也可能和后面的 \texttt{BC} 结合，贡献一次答案。

每次找到一个 \texttt{ABC}，统计它前面连续的 \texttt{A} 的数量，和后面连续的 \texttt{BC}，两个数量相乘得的数量计入答案。

代码

#include<bits/stdc++.h>
using namespace std;

string s;
long long cnt, ans;

int main()
{
    cin >> s;
    int n = s.size(), pos = 0;
    while ((pos = s.find("BC",  pos)) != -1)
        s.replace(pos, 2, "X"), ++pos; //把所有 BC 替换为 X，方便之后的计算
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == 'A') //累计 BC 前面 A 的数量
            ++cnt;
        else if (s[i] == 'X')
            ans += cnt;
        else //当 s[i] 是其它部分时
            cnt = 0;
    }
    cout << ans;
    return 0;
}