← 返回题目列表

Codeforces · 2085/A

A. 薮和弦理论

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

仅由小写拉丁字母组成的字符串 $$$r$$$ 称为 通用 当且仅当 $$$r$$$ 按字典顺序小于 $$$r$$$ 的反转 $$$^{\text{†}}$$$。

给定一个字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。您需要赚取$$$s$$$ 通用。为此,您可以对 $$$s$$$ 执行以下操作 最多 $$$k$$$ 次:

  • 选择两个索引 $$$i$$$ 和 $$$j$$$ ($$$1\le i,j\le n$$$),然后交换 $$$s_i$$$ 和 $$$s_j$$$。请注意,如果 $$$i=j$$$,则您什么都不做。

确定是否可以赚$$$s$$$ 通用 通过执行上述操作最多 $$$k$$$ 次。

$$$^{\text{*}}$$$字符串 $$$a$$$ 按字典顺序小于相同长度的字符串 $$$b$$$,当且仅当以下条件成立:

  • 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。

$$$^{\text{†}}$$$字符串的反转$$$r$$$是从右向左书写$$$r$$$得到的字符串。例如,字符串 $$$\texttt{abcad}$$$ 的反转为 $$$\texttt{dacba}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\le n\le 100$$$, $$$0\le k\le 10^4$$$) — 字符串 $$$s$$$ 的长度,以及可以执行的最大操作数。

第二行包含一个由 $$$n$$$ 小写拉丁字母组成的字符串 $$$s$$$。

输出

对于每个测试用例,打印“是“如果可以使$$$s$$$ 通用 最多执行 $$$k$$$ 次操作。否则,打印“NO".

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

8
1 10000
a
3 3
rev
6 0
string
6 0
theory
9 2
universal
19 0
codeforcesecrofedoc
19 1
codeforcesecrofedoc
3 1
zzz

输出
复制

NO
YES
NO
YES
YES
NO
YES
NO

注意

在第一个测试用例中,$$$s$$$ 在任何操作后都将保持不变。然而$$$\texttt{a}$$$反转后仍然是$$$\texttt{a}$$$,所以不可能使$$$s$$$ 通用.

在第二个测试用例中,字符串 $$$\texttt{rev}$$$ 按字典顺序小于 $$$\texttt{ver}$$$。因此,$$$s$$$ 已经 通用.

在第五个测试用例中,可以执行如下操作:

  1. 交换 $$$s_4$$$ 和 $$$s_7$$$。经过此操作,$$$s$$$ 变为 $$$\texttt{uniserval}$$$;
  2. 交换 $$$s_1$$$ 和 $$$s_3$$$。执行此操作后,$$$s$$$ 变为 $$$\texttt{inuserval}$$$。

字符串 $$$\texttt{inuserval}$$$ 是 通用.