题目描述
给定一个由 A,B,C 构成的字符串，每次你可以进行操作：
-
选择下标 \(i\) ，使得 \(s_{[i,i + 2]} = ABC\) 。
-
如果 \(i\) 是奇数，删掉 A,C ；否则删掉 B。
-
更新每个字符的下标。
求最多能做多少次操作。
\(1 \leq n \leq 2 \times 10^5\) 。
算法描述
这题关键在于一步步推出足以支持贪心的性质。
首先，我们发现以每个 B 为中心，左A右C 进行拓展，我们发现每个 B 之间拓展的区域互不干扰。
我们又发现，删掉 B 以后，这个中心就废了。
我们还发现，删 AC 只会改变自己的状态（AC \(\to\) B），删 B 会废掉自己并且改变后面所有的状态。
所以一个形如 AAAAABCCCCC 这样的东西一定是先把状态调到 AC，删一次，通过前面的东西调到 AC，再删一次...这样删完的。
我们并不关注这个时间顺序，所以我们发现我们需要最大化对后缀调整的次数，为后面的长串争取机会。
导出以下算法：
从左往右扫描，记当前区域AAA..BCCC..嵌套 A,C 的层数是 tmp，前面争取到的最大翻转次数是 rev。
-
tmp = 1
-
当前状态为 AC 并且 rev = 0
说明这段不能为后面贡献翻转次数。
-
否则
如果状态为 B 或是 rev > 0，代表状态都可以调整到 B，删除后可以为后面做出一次贡献，rev++
-
-
tmp > 1
-
状态是 AC
可以删除一次变成 B，B的情况见下面。
-
状态是 B
首先利用前面翻转一次，然后删一次 AC...重复过程，要么最后消耗完，要么翻转次数不够，无论怎么样都可以以删除 B 结束，做出一次翻转贡献，rev++，对 ans 的贡献是 \(\max(rev,tmp)\) 。
-
注意以上过程删一次对答案贡献 1。
这样就完成了讨论，时间复杂度 \(\Theta(n)\) 。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
char s[N];
int ans = 0,n,rev = 0;
int main()
{
scanf("%s",s + 1);
n = strlen(s + 1);
int ans = 0;
for(int i = 1;i <= n;i++)
{
if(s[i] != 'B') continue;
int tmp = 0;
while(i - tmp - 1 >= 1 && i + tmp + 1 <= n && s[i - tmp - 1] == 'A' && s[i + tmp + 1] == 'C') ++tmp;
if(!tmp) continue;
int odd = (i - 1) & 1;
if(odd)
{
if(tmp >= 2) tmp--,ans++;
else
{
if(!rev) ans++;
else rev++,ans++;
tmp--;
}
}
if(tmp)
{
ans += min(tmp,rev + 1);
rev++;
}
}
cout<<ans;
return 0;
}