Lex String

题意翻译

给定两个字符串 $a,b$，保证两个字符串中的字符无交，即不存在某个字符同时在两个串中都出现了，要求通过以下的两种操作构造一个新的字符串 $c$，使得 $c$ 的字典序最小，并且要求不能连续使用某一种操作超过 $k$ 次。 1.从 $a$ 中**任选**一个字符插入到 $c$ 的末尾。 2.从 $b$ 中**任选**一个字符插入到 $c$ 的末尾。 若某一个字符串为空则认为构造结束。 若字符串 $x$ 比字符串 $y$ 字典序小则必定满足**以下两种情况**之一： 1.$x$ 为 $y$ 的前缀，且 $x \not= y$。 2.从左到右的顺序，$x$ 与 $y$ 第一个不同的位置上 $x$ 的字符的字典序比 $y$ 的字符的字典序小。 ----$By$ linyihdfj

题目描述

Kuznecov likes art, poetry, and music. And strings consisting of lowercase English letters. Recently, Kuznecov has found two strings, $ a $ and $ b $ , of lengths $ n $ and $ m $ respectively. They consist of lowercase English letters and no character is contained in both strings. Let another string $ c $ be initially empty. Kuznecov can do the following two types of operations: - Choose any character from the string $ a $ , remove it from $ a $ , and add it to the end of $ c $ . - Choose any character from the string $ b $ , remove it from $ b $ , and add it to the end of $ c $ . But, he can not do more than $ k $ operations of the same type in a row. He must perform operations until either $ a $ or $ b $ becomes empty. What is the lexicographically smallest possible value of $ c $ after he finishes? A string $ x $ is lexicographically smaller than a string $ y $ if and only if one of the following holds: - $ x $ is a prefix of $ y $ , but $ x \neq y $ ; - 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 $ .

输入输出格式

输入格式

There are several test cases in the input data. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases. This is followed by the test cases description. The first line of each test case contains three integers $ n $ , $ m $ , and $ k $ ( $ 1\leq n,m,k \leq 100 $ ) — parameters from the statement. The second line of each test case contains the string $ a $ of length $ n $ . The third line of each test case contains the string $ b $ of length $ m $ . The strings contain only lowercase English letters. It is guaranteed that no symbol appears in $ a $ and $ b $ simultaneously.

输出格式

In each test case, output a single string $ c $ — the answer to the problem.

输入输出样例

输入样例 #1

3
6 4 2
aaaaaa
bbbb
5 9 3
caaca
bedededeb
7 7 1
noskill
wxhtzdy

输出样例 #1

aabaabaa
aaabbcc
dihktlwlxnyoz

说明

In the first test case, it is optimal to take two 'a's from the string $ a $ and add them to the string $ c $ . Then it is forbidden to take more characters from $ a $ , hence one character 'b' from the string $ b $ has to be taken. Following that logic, we end up with $ c $ being 'aabaabaa' when string $ a $ is emptied. In the second test case it is optimal to take as many 'a's from string $ a $ as possible, then take as many 'b's as possible from string $ b $ . In the end, we take two 'c's from the string $ a $ emptying it.

题目大意：
给定两个字符串a和b，保证两个字符串中的字符没有交集，即不存在某个字符同时在两个串中都出现。要求通过以下两种操作构造一个新的字符串c，使得c的字典序最小，并且要求不能连续使用某一种操作超过k次。

1. 从a中任选一个字符插入到c的末尾。
2. 从b中任选一个字符插入到c的末尾。

若某一个字符串为空则认为构造结束。

若字符串x比字符串y字典序小则必定满足以下两种情况之一：

1. x为y的前缀，且x ≠ y。
2. 从左到右的顺序，x与y第一个不同的位置上x的字符的字典序比y的字符的字典序小。

输入输出数据格式：

输入格式：
输入数据包含多个测试用例。第一行包含一个整数t（1≤t≤100）——测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含三个整数n、m和k（1≤n,m,k≤100）——来自题目描述的参数。

每个测试用例的第二行包含一个长度为n的字符串a。

每个测试用例的第三行包含一个长度为m的字符串b。

字符串只包含小写英文字母。保证a和b中没有同时出现的符号。

输出格式：
对于每个测试用例，输出一个字符串c——问题的答案。

输入输出样例：

输入样例 #1：
```
3
6 4 2
aaaaaa
bbbb
5 9 3
caaca
bedededeb
7 7 1
noskill
wxhtzdy
```

输出样例 #1：
```
aabaabaa
aaabbcc
dihktlwlxnyoz
```

说明：
在第一个测试用例中，最优的方法是从字符串a中取两个'a'并将它们添加到字符串c中。然后禁止从a中取更多字符，因此必须从字符串b中取一个字符'b'。按照这个逻辑，当字符串a为空时，我们得到c为'aabaabaa'。

在第二个测试用例中，最优的方法是尽可能多地从字符串a中取'a'，然后尽可能多地从字符串b中取'b'。最后，我们从字符串a中取两个'c'，使其为空。题目大意： 给定两个字符串a和b，保证两个字符串中的字符没有交集，即不存在某个字符同时在两个串中都出现。要求通过以下两种操作构造一个新的字符串c，使得c的字典序最小，并且要求不能连续使用某一种操作超过k次。 1. 从a中任选一个字符插入到c的末尾。 2. 从b中任选一个字符插入到c的末尾。 若某一个字符串为空则认为构造结束。 若字符串x比字符串y字典序小则必定满足以下两种情况之一： 1. x为y的前缀，且x ≠ y。 2. 从左到右的顺序，x与y第一个不同的位置上x的字符的字典序比y的字符的字典序小。 输入输出数据格式： 输入格式： 输入数据包含多个测试用例。第一行包含一个整数t（1≤t≤100）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含三个整数n、m和k（1≤n,m,k≤100）——来自题目描述的参数。 每个测试用例的第二行包含一个长度为n的字符串a。 每个测试用例的第三行包含一个长度为m的字符串b。 字符串只包含小写英文字母。保证a和b中没有同时出现的符号。 输出格式： 对于每个测试用例，输出一个字符串c——问题的答案。 输入输出样例： 输入样例 #1： ``` 3 6 4 2 aaaaaa bbbb 5 9 3 caaca bedededeb 7 7 1 noskill wxhtzdy ``` 输出样例 #1： ``` aabaabaa aaabbcc dihktlwlxnyoz ``` 说明： 在第一个测试用例中，最优的方法是从字符串a中取两个'a'并将它们添加到字符串c中。然后禁止从a中取更多字符，因此必须从字符串b中取一个字符'b'。按照这个逻辑，当字符串a为空时，我们得到c为'aabaabaa'。 在第二个测试用例中，最优的方法是尽可能多地从字符串a中取'a'，然后尽可能多地从字符串b中取'b'。最后，我们从字符串a中取两个'c'，使其为空。