题目描述

小 Y 给了小 X 一个长度为 $n$ 的只包含大写字母 $\tt{A,B,C}$ 的字符串。你可以对这个字符串进行如下操作：将子串 $\tt{ABC}$ 变成 $\tt{BCA}$。 小 X 想知道这个字符串最多能进行多少次操作。 一个字符串的子串是把这个字符串通过删去头部和尾部若干个字符形成的字符串。例如：$\tt{A,B,BB,AB,ABB}$ 是 $\tt{ABB}$ 的子串，$\tt{ABA}$ 不是 $\tt{ABBA}$ 的子串。

思路解析

我们首先考虑，如果把一个 $\tt{ABC}$ 变成 $\tt{BCA}$，会有什么影响，或者说，会对答案产生什么新的贡献。

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

所以结论很明显了，每次找到一个$\tt{ABC}$，统计它前面连续的$\tt{A}$的数量，和后面连续的$\tt{BC}$，两个数量相乘得的数量计入答案。最后输出

代码呈现

#include<bits/stdc++.h>
using namespace std;
int main(){
   //自己写，别学PuBliC
   return 0;
}