Ela Sorting Books

题意翻译

将 $n$ 个字母（在 `a` 到 `y` 中）任意分为大小相等的 $k$ 份，将每一份的 MEX 字母组合成一个字符串，求能得到的字典序最大的字符串。 一组字母的 MEX 字母是在字母表中出现最早的一个不存在于这组字母中的字母。 by Wu_while

题目描述

Ela loves reading a lot, just like her new co-workers in DTL! On her first day after becoming an engineer in DTL, she is challenged by a co-worker to sort a heap of books into different compartments on the shelf. $ n $ books must be split into $ k $ compartments on the bookshelf ( $ n $ is divisible by $ k $ ). Each book is represented by a lowercase Latin letter from 'a' to 'y' inclusively, which is the beginning letter in the title of the book. Ela must stack exactly $ \frac{n}{k} $ books in each compartment. After the books are stacked, for each compartment indexed from $ 1 $ to $ k $ , she takes the minimum excluded (MEX) letter of the multiset of letters formed by letters representing all books in that compartment, then combines the resulting letters into a string. The first letter of the resulting string is the MEX letter of the multiset of letters formed by the first compartment, the second letter of the resulting string is the MEX letter of the multiset of letters formed by the second compartment, ... and so on. Please note, under the constraint of this problem, MEX letter can always be determined for any multiset found in this problem because 'z' is not used. What is the lexicographically greatest resulting string possible that Ela can create? A string $ a $ is lexicographically greater than a string $ b $ if and only if one of the following holds: - $ b $ is a prefix of $ a $ , but $ b \ne a $ ; - in the first position where $ a $ and $ b $ differ, the string $ a $ has a letter that appears later in the alphabet than the corresponding letter in $ b $ . The minimum excluded (MEX) letter of a multiset of letters is the letter that appears earliest in the alphabet and is not contained in the multiset. For example, if a multiset of letters contains $ 7 $ letters 'b', 'a', 'b', 'c', 'e', 'c', 'f' respectively, then the MEX letter of this compartment is 'd', because 'd' is not included in the multiset, and all letters comes before 'd' in the alphabet, namely 'a', 'b' and 'c', are included in the multiset.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). Description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 200 $ ; $ 1 \le k \le n $ ). It is guaranteed that $ n $ is divisible by $ k $ . The second line of each test case contains a string of $ n $ lowercase Latin letters from 'a' to 'y' inclusively. Each letter represents the starting letter of the title of a book in the initial heap. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 1000 $ .

输出格式

For each test case, output a string of $ k $ letters which is the most optimal string that Ela can find.

输入输出样例

输入样例 #1

5
12 3
cabccadabaac
12 6
cabccadabaac
12 12
cabccadabaac
25 1
abcdefghijklmnopqrstuvwxy
10 5
bcdxedbcfg

输出样例 #1

edb
ccbbba
bbbbbaaaaaaa
z
aaaaa

说明

In the first test case, the books can be divided into $ 3 $ compartments as below: - the first compartment contains the books with indices $ 1, 2, 3, 7 $ : $ multiset_1 = \{ $ 'c', 'a', 'b', 'd' $ \} $ $ \rightarrow $ $ MEX(multiset_1) = $ 'e' - the second compartment contains the books with indices $ 4, 5, 6, 9 $ : $ multiset_2 = \{ $ 'c', 'c', 'a', 'b' $ \} $ $ \rightarrow $ $ MEX(multiset_2) = $ 'd' - the third compartment contains the remaining books $ 8, 10, 11, 12 $ : $ multiset_3 = \{ $ 'a', 'a', 'a', 'c' $ \} $ $ \rightarrow $ $ MEX(multiset_3) = $ 'b' Therefore, the answer is 'edb'. It can be proven that there is no way that Ela can arrange the books so that it results in a lexicographically greater string. 

**题意翻译**

将 $n$ 个字母（在 `a` 到 `y` 中）任意分为大小相等的 $k$ 份，将每一份的 MEX 字母组合成一个字符串，求能得到的字典序最大的字符串。

一组字母的 MEX 字母是在字母表中出现最早的一个不存在于这组字母中的字母。

**题目描述**

Ela 爱读书，就像她在 DTL 的新同事一样！在她成为 DTL 工程师的第一天，她被一位同事挑战将一堆书分成书架上的不同隔间。$n$ 本书必须分成书架上的 $k$ 个隔间（$n$ 可以被 $k$ 整除）。每本书由一个小写拉丁字母表示，从 'a' 到 'y'（包括 'a' 和 'y'），这是书名的第一个字母。

Ela 必须在每个隔间中正好堆放 $\frac{n}{k}$ 本书。堆放书籍后，对于从 $1$ 到 $k$ 编号的每个隔间，她取出由该隔间中所有书籍的字母形成的多重集的最小排除（MEX）字母，然后将得到的字母组合成一个字符串。结果字符串的第一个字母是第一个隔间的字母多重集的 MEX 字母，结果字符串的第二个字母是第二个隔间的字母多重集的 MEX 字母，依此类推。请注意，在本问题的约束下，MEX 字母可以始终确定为任何在此问题中找到的多重集，因为 'z' 没有被使用。

求 Ela 可以创建的按字典序最大的结果字符串。

一个字符串 $a$ 按字典序大于字符串 $b$ 当且仅当以下任一条件成立：

- $b$ 是 $a$ 的前缀，但 $b \ne a$；
- 在 $a$ 和 $b$ 首次不同的位置，字符串 $a$ 有一个在字母表中比对应的 $b$ 中的字母出现得更晚的字母。

一个字母多重集的 MEX 字母是字母表中最早出现的不包含在此多重集中的字母。例如，如果一个字母多重集按顺序包含字母 'b', 'a', 'b', 'c', 'e', 'c', 'f'，那么这个隔间的 MEX 字母是 'd'，因为 'd' 不包含在多重集中，且所有在字母表中小于 'd' 的字母，即 'a', 'b' 和 'c'，都包含在多重集中。

**输入输出格式**

**输入格式**

每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 100$）。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 200$；$1 \le k \le n$）。保证 $n$ 可以被 $k$ 整除。

每个测试用例的第二行包含一个由 $n$ 个小写拉丁字母组成的字符串，从 'a' 到 'y'（包括 'a' 和 'y'）。每个字母代表初始堆中一本书的标题首字母。

保证所有测试用例的 $n$ 之和不超过 $1000$。

**输出格式**

对于每个测试用例，输出一个由 $k$ 个字母组成的字符串，这是 Ela 可以找到的最优字符串。

**输入输出样例**

**输入样例 #1**

```
5
12 3
cabccadabaac
12 6
cabccadabaac
12 12
cabccadabaac
25 1
abcdefghijklmnopqrstuvwxy
10 5
bcdxedbcfg
```

**输出样例 #1**

```
edb
ccbbba
bbbbbaaaaaaa
z
aaaaa
```**题意翻译** 将 $n$ 个字母（在 `a` 到 `y` 中）任意分为大小相等的 $k$ 份，将每一份的 MEX 字母组合成一个字符串，求能得到的字典序最大的字符串。 一组字母的 MEX 字母是在字母表中出现最早的一个不存在于这组字母中的字母。 **题目描述** Ela 爱读书，就像她在 DTL 的新同事一样！在她成为 DTL 工程师的第一天，她被一位同事挑战将一堆书分成书架上的不同隔间。$n$ 本书必须分成书架上的 $k$ 个隔间（$n$ 可以被 $k$ 整除）。每本书由一个小写拉丁字母表示，从 'a' 到 'y'（包括 'a' 和 'y'），这是书名的第一个字母。 Ela 必须在每个隔间中正好堆放 $\frac{n}{k}$ 本书。堆放书籍后，对于从 $1$ 到 $k$ 编号的每个隔间，她取出由该隔间中所有书籍的字母形成的多重集的最小排除（MEX）字母，然后将得到的字母组合成一个字符串。结果字符串的第一个字母是第一个隔间的字母多重集的 MEX 字母，结果字符串的第二个字母是第二个隔间的字母多重集的 MEX 字母，依此类推。请注意，在本问题的约束下，MEX 字母可以始终确定为任何在此问题中找到的多重集，因为 'z' 没有被使用。 求 Ela 可以创建的按字典序最大的结果字符串。 一个字符串 $a$ 按字典序大于字符串 $b$ 当且仅当以下任一条件成立： - $b$ 是 $a$ 的前缀，但 $b \ne a$； - 在 $a$ 和 $b$ 首次不同的位置，字符串 $a$ 有一个在字母表中比对应的 $b$ 中的字母出现得更晚的字母。 一个字母多重集的 MEX 字母是字母表中最早出现的不包含在此多重集中的字母。例如，如果一个字母多重集按顺序包含字母 'b', 'a', 'b', 'c', 'e', 'c', 'f'，那么这个隔间的 MEX 字母是 'd'，因为 'd' 不包含在多重集中，且所有在字母表中小于 'd' 的字母，即 'a', 'b' 和 'c'，都包含在多重集中。 **输入输出格式** **输入格式** 每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 100$）。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 200$；$1 \le k \le n$）。保证 $n$ 可以被 $k$ 整除。 每个测试用例的第二行包含一个由 $n$ 个小写拉丁字母组成的字符串，从 'a' 到 'y'（包括 'a' 和 'y'）。每个字母代表初始堆中一本书的标题首字母。 保证所有测试用例的 $n$ 之和不超过 $1000$。 **输出格式** 对于每个测试用例，输出一个由 $k$ 个字母组成的字符串，这是 Ela 可以找到的最优字符串。 **输入输出样例** **输入样例 #1** ``` 5 12 3 cabccadabaac 12 6 cabccadabaac 12 12 cabccadabaac 25 1 abcdefghijklmnopqrstuvwxy 10 5 bcdxedbcfg ``` **输出样例 #1** ``` edb ccbbba bbbbbaaaaaaa z aaaaa ```