CF1873G

题面

ABBC or BACB

题面翻译

给定一个由 A 和 B 组成的字符串 $s$，有两种操作：

• 将一个子串 AB 转换为 BC 并获得一枚金币。
• 将一个字串 BA 转换为 CB 并获得一枚金币。

你可以进行若干次操作，问最多能获得多少枚金币。

By @Larryyu

题目描述

You are given a string $s$ made up of characters $\texttt{A}$ and $\texttt{B}$. Initially you have no coins. You can perform two types of operations:

• Pick a substring$^\dagger$ $\texttt{AB}$, change it to $\texttt{BC}$, and get a coin.
• Pick a substring$^\dagger$ $\texttt{BA}$, change it to $\texttt{CB}$, and get a coin.

What is the most number of coins you can obtain?

$^\dagger$ A substring of length $2$ is a sequence of two adjacent characters of a string.

输入格式

Input

The input consists of multiple test cases. The first line of the input contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The only line of each test case contains the string $s$ ($1 \leq |s| \leq 2 \cdot 10^5$). All characters of $s$ are either $\texttt{A}$ or $\texttt{B}$.

The sum of the lengths of $s$ over all test cases does not exceed $2 \cdot 10^5$.

输出格式

Output

For each test case, output a single integer — the maximum number of coins you can obtain.

样例 #1

样例输入 #1

8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA

样例输出 #1

2
1
3
1
6
2
0
0

提示

Note

In the first test case you can perform the following operations to get $2$ coins:

$\color{red}{\texttt{AB}}\texttt{BA} \to \texttt{BC}\color{red}{\texttt{BA}} \to \texttt{BCCB}$

In the second test case you can perform the following operation to get $1$ coin:

$\color{red}{\texttt{AB}}\texttt{A} \to \texttt{BCA}$

In the third test case you can perform the following operations to get $3$ coins:

$\color{red}{\texttt{BA}}\texttt{ABA} \to \texttt{CBA}\color{red}{\texttt{BA}} \to \texttt{C}\color{red}{\texttt{BA}}\texttt{CB} \to \texttt{CCBCB}$

思路

首先对于单独的 AB 或者 BA，可以直接把它变成 BC 和 CB 并获得一枚金币。

想想扩展一下呢？假如 AB 变成 BC 后发现前面还有一个 A，也就是说可以从 AAB 变成 BCC。

以此类推，AAAAAAAAA...B 就可以变成 BCCCCCCCCCCCC...，得到的价值是参与变换的 A 的个数。

同理可得，BAAAAAAAA... 就可以变成 CCCCCCCC...B，得到的价值也是参与变换的 A 的个数。

所以我们可以把原串看作若干个被 B 分割的区间，对于每个 B，我们维护它到上一个 B 之间 A 的个数和它到下一个 B 之间 A 的个数。

假设有 $n$ 个 B，那么就会有 $n+1$ 个区间（包括长度为 0 的区间），那么对于每一个 B 都有两种选择，选左边或者选右边（不选重的情况下），最后会选出 $n$ 个区间，那么可以转化一下，也就是有一个区间不选，我们排一下序拿总区间和减去这个最小的区间和得到的就是最大价值了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 8;

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int ans = 0;
        char s[N];
        cin >> s;
        int len = strlen(s);
        int cnt = 0, be = 0;
        int l[N], r[N], last[N];
        for(int i = 0, j = 0; i < len; i++)
        {
            if(s[i] == 'B')
            {
                cnt++;
                last[cnt] = be;
                be = cnt;
                j = i - 1;
                while(j >= 0 && s[j] != 'B') j--;
                l[cnt] = i - j - 1;
                if(last[cnt] != 0)
                {
                    r[last[cnt]] = l[cnt];
                }
            }
        }
        for(int i = len - 1; i >= 0; i--)
        {
            if(s[i] == 'B')
            {
                r[cnt] = len - i - 1;
                break;
            }
        }
        vector<int> num;
        for(int i = 1; i <= cnt; i++)
        {
            num.push_back(l[i]);
            num.push_back(r[i]);
            ans += l[i];
        }
        ans += r[cnt];
        if(ans == 0)
        {
            cout << 0 << endl;
            continue;
        }
        sort(num.begin(), num.end());
        ans -= num[0];
        cout << ans << endl;
    }
    return 0;
}