自动搬运

查看原文

来自洛谷，原作者为

	lizeyuhello 爬山 || SB 新初一 OIer

搬运于2025-08-24 21:17:55，当前版本为作者最后更新于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;
}