G. ABBC or BACB
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.
Example
input
8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA
output
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}$$
解题思路
经典思维题不会做.jpg
官方给出的题解很长,这里简练下给出其核心思想。最关键的地方是要注意到任意一种操作执行后字符 $\texttt{B}$ 的变化情况。
如果是 $\texttt{AB} \to \texttt{BC}$,那么可以理解成 $\texttt{B}$ 左移并覆盖其左邻的 $\texttt{A}$,再用 $\texttt{C}$ 覆盖原来的位置。同理对于 $\texttt{BA} \to \texttt{CB}$,可以理解成 $\texttt{B}$ 右移并覆盖其右邻的 $\texttt{A}$,再用 $\texttt{C}$ 覆盖原来的位置。
因此对于 $\texttt{AAAB}$ 这一类字符串,将 $\texttt{B}$ 不断左移并覆盖,即有 $\texttt{AAAB} \to \texttt{AABC} \to \texttt{ABCC} \to \texttt{BCCC}$,那么就可以获得最大收益(即操作次数最多)。同理对于 $\texttt{BAAA}$ 这一类字符串,将 $\texttt{B}$ 不断右移并覆盖,即有 $\texttt{BAAA} \to \texttt{CBAA} \to \texttt{CCBA} \to \texttt{CCCB}$,可以获得最大收益。
因此可以发现对于一个字符 $\texttt{B}$,如果其两边相邻的都是 $\texttt{A}$,那么可以选择左移或右移,并且之后只能向同个方向移动(因为另一个方向会变成 $\texttt{C}$)。因此一个字符 $\texttt{B}$ 只能覆盖某一段与其相邻且连续的 $\texttt{A}$。所以我们找到字符串中所有的 $\texttt{B}$,假设有 $k$ 个,那么就会将整个字符串中的 $\texttt{A}$ 分成 $k+1$ 个段(包括空串)。例如有 $\texttt{AABBAAAB}$,那么 $\texttt{A}$ 就被分成 $\left\{ \texttt{AA}, \, \phi, \, \texttt{AAA}, \phi \right\}$。由于 $k$ 个 $\texttt{B}$ 只能覆盖 $k$ 段的 $\texttt{A}$,意味着必然有一段 $\texttt{A}$ 无法被覆盖,而为了得到最大收益,我们选择长度最小的那段舍弃即可。
因此我们只需根据 $\texttt{B}$ 的划分来累加每一段 $\texttt{A}$ 的长度,并维护长度的最小值。最后答案就是 $\texttt{A}$ 的个数减去这个最小值。
AC 代码如下,时间复杂度为 $O(n)$:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
char s[N];
void solve() {
scanf("%s", s);
int sum = 0, mn = 1e9;
for (int i = 0, j = -1; s[i]; i++) {
if (s[i] == 'B') {
int t = i - j - 1;
sum += t;
mn = min(mn, t);
j = i;
}
if (!s[i + 1]) {
int t = i - j;
sum += t;
mn = min(mn, t);
}
}
printf("%d\n", sum - mn);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
参考资料
Codeforces Round #898 (Div. 4) Editorial:https://codeforces.com/blog/entry/120634
Codeforces Round 898 (Div. 4)A-H:https://zhuanlan.zhihu.com/p/657711661
标签:ABBC,BA,int,texttt,color,test,BACB,red From: https://www.cnblogs.com/onlyblues/p/17759222.html