CF1873G ABBC or BACB 题解

__Star_Sky · 2023-09-27 22:29:08 · 题解

Description

给定一个由字符 A 和 B 组成的字符串。一开始你没有硬币。你可以执行两种类型的操作:

• 选择子字符串 AB，将其改为 BC，并获得一枚硬币。

• 选择子字符串 BA，将其改为 CB，并获得一枚硬币。

问最多能获得多少硬币?

注意，这里说的子字符串必须是连续的。

Solution

观察样例，可以发现形如 AAAB 的子串和形如 BAAA 的子串一定都可以一次性消完。以 BAAA 为例，消去的过程如下: BAAA,CBAA,CCBA,CCCB，显然这时能获得的硬币数量就是连续的 A 的数量。消去 A 的过程其实可以看作将 B 左移或右移。

但是并不是所有的连续的 A 都能被消去。考虑如下数据：AABAAA，这时只能消去其中一边的 A。

那么什么时候所有的连续的 A 都能被删去呢？经过思考容易发现，只要原字符串以 B 开头或结尾，或存在至少一个子串 BB，那么所有的 A 都能够被删去，此时能获得的最大的硬币数量就是所有 A 的数量。例如 BAAAABAAA，AAABBAABA。如果不满足条件，那么最优的选择一定是选择最小的连续一段 A 不删，枚举即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
char a[N];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",a+1);
        int n=strlen(a+1);
        int ans=0x3f3f3f3f,cnt=0;
        bool flag=false;
        if(a[1]=='B'||a[n]=='B') flag=true;
        else for(int i=1;i<=n;i++)if(a[i]=='B'&&a[i-1]=='B') {flag=true;break;}
        if(flag)
        {
            for(int i=1;i<=n;i++) if(a[i]=='A') cnt++;
            printf("%d\n",cnt);
            continue;
        }
        for(int i=1;i<=n+1;i++)
        {
            if(a[i]=='A') cnt++;
            else if(cnt) ans=min(ans,cnt),cnt=0;
        }
        cnt=0;
        for(int i=1;i<=n;i++) if(a[i]=='A') cnt++;
        if(cnt==n||cnt==0) puts("0");
        else printf("%d\n",cnt-ans);
    }
    return 0;
}