CF1898A Milica and String

Milica 有一个长度为 $n$ 的字符串 $s$，该字符串只包含字符 A 和 B。她希望将 $s$ 修改为恰好包含 $k$ 个 B 的字符串。每次操作，她可以进行如下操作： - 选择一个整数 $i$（$1 \leq i \leq n$）和一个字符 $c$（$c$ 为 A 或 B）。 - 然后，将字符串 $s$ 的前 $i$ 个字符（即 $s_1, s_2, \ldots, s_i$）全部替换为字符 $c$。 Milica 不希望进行太多操作，以免浪费太多时间。 她希望你帮她求出将 $s$ 修改为恰好包含 $k$ 个 B 所需的最少操作次数，并输出这些操作（即每次操作选择的 $i$ 和 $c$）。

每组测试数据包含多个测试用例。第一行包含测试用例数 $t$（$1 \leq t \leq 500$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$3 \leq n \leq 100$，$0 \leq k \leq n$），分别表示字符串 $s$ 的长度和最终希望字符串中出现的 B 的个数。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 A 和 B 组成。

对于每个测试用例，第一行输出一个整数 $m$，表示 Milica 需要进行的最少操作次数。 接下来的 $m$ 行中，每行输出两个参数 $i$（$1 \leq i \leq n$）和 $c$（$c$ 为 'A' 或 'B'），表示第 $j$ 次操作选择的参数。 如果存在多种最优解，输出任意一种即可。

在第一个测试用例中，$s$ 中已经有 $2$ 个 B，因此 Milica 不需要进行任何操作。 在第二个测试用例中，唯一能通过一次操作使 $s$ 中有 $3$ 个 B 的方法是将第一个字符替换为 B：AABAB $\rightarrow$ BABAB。 在第三个测试用例中，唯一能通过一次操作使 $s$ 中有 $0$ 个 B 的方法是将前 $5$ 个字符全部替换为 A：BBBBB $\rightarrow$ AAAAA。 在第四个测试用例中，一种通过一次操作使 $s$ 中有 $0$ 个 B 的方法是将前 $2$ 个字符全部替换为 A：BAA $\rightarrow$ AAA。注意，“1 A” 和 “3 A” 也是正确的单次操作方案。 由 ChatGPT 4.1 翻译