CF1706A Another String Minimization Problem

你有一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$，其中每个元素都是 $1$ 到 $m$ 之间的整数。你还有一个由 $m$ 个字符 B 组成的字符串 $s$。 你将进行如下 $n$ 次操作： - 在第 $i$ 次操作（$1 \le i \le n$）时，你可以将 $s$ 的第 $a_i$ 个字符或第 $(m + 1 - a_i)$ 个字符替换为 A。在所有操作过程中，你可以多次替换同一个位置的字符。 请你求出经过这 $n$ 次操作后，能够得到的字典序最小的字符串。 如果两个长度相同的字符串 $x$ 和 $y$，在第一个不同的位置，$x$ 的字母在字母表中比 $y$ 的字母靠前，则称 $x$ 的字典序小于 $y$。

第一行包含一个整数 $t$（$1 \le t \le 2000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 50$），分别表示序列 $a$ 的长度和字符串 $s$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le m$），表示序列 $a$。

对于每个测试用例，输出一个长度为 $m$ 的字符串，即你能得到的字典序最小的字符串。字符串中的每个字符应为大写英文字母 A 或 B。

在第一个测试用例中，序列 $a = [1, 1, 3, 1]$。一种可能的方案如下： - 第 $1$ 次操作，你可以将 $s$ 的第 $1$ 个字符替换为 A。此时 $s$ 变为 ABBBB。 - 第 $2$ 次操作，你可以将 $s$ 的第 $5$ 个字符替换为 A（因为 $m+1-a_2=5$）。此时 $s$ 变为 ABBBA。 - 第 $3$ 次操作，你可以将 $s$ 的第 $3$ 个字符替换为 A。此时 $s$ 变为 ABABA。 - 第 $4$ 次操作，你可以将 $s$ 的第 $1$ 个字符替换为 A。此时 $s$ 仍为 ABABA。 最终得到的字符串为 ABABA。无法得到字典序更小的字符串。 在第二个测试用例中，你只进行一次操作。你可以将 $s$ 的第 $2$ 个字符或第 $4$ 个字符替换为 A。你可以得到 BABBB 或 BBBAB，其中 BABBB 的字典序最小。 在第三个测试用例中，唯一能得到的字符串是 A。 在第四个测试用例中，你可以将 $s$ 的第 $1$ 个和第 $2$ 个字符替换为 A，得到 AABB。 在第五个测试用例中，你可以将 $s$ 的第 $1$ 个和第 $3$ 个字符替换为 A，得到 ABABBBB。 由 ChatGPT 4.1 翻译