P12550 [UOI 2025] Reversal ABC

给定一个由字符 $\texttt{A}$、$\texttt{B}$ 和 $\texttt{C}$ 组成的字符串 $s$。 每次操作中，你可以选择字符串中两个**相邻**的元素 $s_is_{i+1}$，且它们的顺序为以下之一：$\texttt{AB}$、$\texttt{BC}$ 或 $\texttt{CA}$，然后交换它们的位置。 求可以对字符串 $s$ 进行的最大连续操作次数。 本题每个测试包含多组输入数据，你需要分别独立处理每组数据。

第一行包含一个整数 $T$ $(1\le T\le 10^5)$ —— 输入数据的组数。接下来是各组数据的描述。 每组数据的第一行包含一个整数 $n$ $(1 \le n \le 10^6)$ —— 字符串 $s$ 的长度。 每组数据的第二行包含一个长度为 $n$ 的字符串 $s$，由字符 $\texttt{A}$、$\texttt{B}$ 和 $\texttt{C}$ 组成。 保证单个测试中所有数据的 $n$ 之和不超过 $10^6$。

对于每组数据，输出一行一个整数 —— 可以对字符串 $s$ 进行的最大连续操作次数。

在第一个样例的第一组数据中，字符串 $\texttt{ABCCA}$ 最多可以进行 $3$ 次连续操作。其中一种可能的操作序列是：$[\texttt{ABCCA} \rightarrow \texttt{BACCA}, \texttt{BACCA} \rightarrow \texttt{BACAC}, \texttt{BACAC} \rightarrow \texttt{BAACC}]$。 ### 评分标准 设 $K$ 为单个测试中所有数据的 $n$ 之和。 - （$2$ 分）：答案为 $0$ 或 $1$； - （$3$ 分）：$n \le 3$； - （$5$ 分）：对于所有 $1 \le i \le n$，$s_i \ne \texttt{C}$； - （$5$ 分）：$s$ 的形式为 $\texttt{AA}\ldots \texttt{AABB}\ldots \texttt{BBCC}\ldots \texttt{CC}$（即 $x \cdot \texttt{A} + y \cdot \texttt{B} + z \cdot \texttt{C}$，其中 $x$、$y$、$z$ 为正整数）； - （$9$ 分）：对于所有 $1 \le i < n$，$s_is_{i+1} \ne \texttt{CA}$； - （$10$ 分）：$T = 1$，$n \le 12$； - （$8$ 分）：$n \le 12$； - （$28$ 分）：$K \le 2000$； - （$30$ 分）：无额外限制。 翻译由 DeepSeek V3 完成