← 返回题目列表

Codeforces · 1852/D

D. 米瑞妮和火柴棍

中文机器翻译题面 查看原题

Miriany 的火柴棍是一个 $$$2 \times n$$$ 网格,需要填充字符 A 或 B。

他已经填写了网格的第一行,并希望您填写第二行。这样做的方式必须使具有不同字符$$$^\dagger$$$ 的相邻单元对的数量等于 $$$k$$$。如果不可能,请报告。

$$$^\dagger$$$ 具有不同字符的相邻单元格对是一对单元格 $$$(r_1, c_1)$$$ 和 $$$(r_2, c_2)$$$ ($$$1 \le r_1, r_2 \le 2$$$, $$$1 \le c_1, c_2 \le n$$$) 使得 $$$|r_1 - r_2| + |c_1 - c_2| = 1$$$ 并且 $$$(r_1, c_1)$$$ 和 $$$(r_2, c_2)$$$ 中的字符不同。

输入

第一行由一个整数 $$$t$$$ 组成,即测试用例的数量 ($$$1 \leq t \leq 1000$$$)。测试用例的描述如下。

每个测试用例的第一行有两个整数,$$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 0 \leq k \leq 3 \cdot n$$$) – 火柴棒的列数,以及所需的不同字符的相邻单元格对的数量。

以下行包含 $$$n$$$ 个字符的字符串 $$$s$$$($$$s_i$$$ 是 A 或 B)– Miriany 火柴棍的顶行。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果无法用具有不同字符的相邻单元格对的数量等于 $$$k$$$ 填充第二行,则输出“NO”。

否则,输出“YES”。然后,打印 Miriany 火柴棍的有效底行所包含的 $$$n$$$ 个字符。如果有多个答案,则输出其中一个。

示例

输入 #1

4
10 1
ABBAAABBAA
4 5
AAAA
9 17
BAAABBAAB
4 9
ABAB

输出 #1

NO
YES
BABB
YES
ABABAABAB
NO

注意

在第一个测试用例中,可以证明不存在可能的方法来填充网格的行 $$$2$$$ 使得 $$$k = 1$$$。

对于第二个测试用例,BABB 是一个可能的答案。

下面的网格是第二行填写BABB的结果。

$$$\begin{数组}{|c|c|} \hline A & A & A & A \cr \hline B & A & B & B \cr \hline \end{数组}$$$

不同字符对如下以红色显示:

$$$\begin{array}{|c|c|} \hline \color{red}{A} & A & A & A \cr \hline \color{red}{B} & A & B & B \cr \hline \end{array}$$$—————————————————$$$\begin{array}{|c|c|} \hline A & A & \color{red}{A} & A \cr \hline B & A & \color{red}{B} & B \cr \hline \end{array}$$$—————————————————$$$\begin{array}{|c|c|} \hline A & A & A & \color{red}{A} \cr \hline B & A & B & \color{red}{B} \cr \hline \end{array}$$$—————————————————$$$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline \color{red}{B} & \color{red}{A} & B & B \cr \hline \end{array}$$$--------------------------------------------------------$$$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline B & \color{red}{A} & \color{red}{B} & B \cr \hline \end{array}$$$

总共有$$$5$$$对,满足$$$k$$$。