309608: CF1706A. Another String Minimization Problem
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Another String Minimization Problem
题意翻译
你有一个长为 $m$,初始全为 `B` 的字符串 $s$,和一个长为 $n$ 的数列 $a$。对于 $a$ 中的每个元素 $a_i$,你可以将 $s$ 的第 $a_i$ 位或 $(m+1-a_i$) 位(下标从 $1$ 开始)变为 `A`。求能得到的 $s$ 中字典序最小的一个。 多测,$1\le t\le 2\times10^3$,$1\le n,m\le 50$,$1\le a_i\le m$。 Translated by @Sya_Resory题目描述
You have a sequence $ a_1, a_2, \ldots, a_n $ of length $ n $ , consisting of integers between $ 1 $ and $ m $ . You also have a string $ s $ , consisting of $ m $ characters B. You are going to perform the following $ n $ operations. - At the $ i $ -th ( $ 1 \le i \le n $ ) operation, you replace either the $ a_i $ -th or the $ (m + 1 - a_i) $ -th character of $ s $ with A. You can replace the character at any position multiple times through the operations. Find the lexicographically smallest string you can get after these operations. A string $ x $ is lexicographically smaller than a string $ y $ of the same length if and only if in the first position where $ x $ and $ y $ differ, the string $ x $ has a letter that appears earlier in the alphabet than the corresponding letter in $ y $ .输入输出格式
输入格式
The first line contains the number of test cases $ t $ ( $ 1 \le t \le 2000 $ ). The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 50 $ ) — the length of the sequence $ a $ and the length of the string $ s $ respectively. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le m $ ) — the sequence $ a $ .
输出格式
For each test case, print a string of length $ m $ — the lexicographically smallest string you can get. Each character of the string should be either capital English letter A or capital English letter B.
输入输出样例
输入样例 #1
6
4 5
1 1 3 1
1 5
2
4 1
1 1 1 1
2 4
1 3
2 7
7 5
4 5
5 5 3 5
输出样例 #1
ABABA
BABBB
A
AABB
ABABBBB
ABABA