← 返回题目列表

Codeforces · 1468/H

H. K 和中位数

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

如果我们按非递减顺序对 $$$s$$$ 进行排序,那么我们将奇数长度的序列 $$$s$$$ 的中位数表示为 $$$s$$$ 中间的值。例如,令 $$$s = [1, 2, 5, 7, 2, 3, 12]$$$。排序后得到序列$$$[1, 2, 2, \underline{3}, 5, 7, 12]$$$,中位数等于$$$3$$$。

你有一个由 $$$n$$$ 整数 $$$[1, 2, \dots, n]$$$ 和一个奇数整数 $$$k$$$ 组成的序列。

在一个步骤中,您从序列中选择任何 $$$k$$$ 元素,并删除除中位数之外的所有选定元素。这些元素不必连续(它们之间允许有间隙)。

例如,如果您有序列 $$$[1, 2, 3, 4, 5, 6, 7]$$$ (即 $$$n=7$$$)且 $$$k = 3$$$,则第一步可以使用以下选项:

- 选择 $$$[1, \underline{2}, 3]$$$; $$$2$$$是它们的中位数,所以不会被擦除,得到的序列是$$$[2,4,5,6,7]$$$;
- 选择 $$$[2, \underline{4}, 6]$$$; $$$4$$$是它们的中位数,所以不会被擦除,得到的序列是$$$[1, 3, 4, 5, 7]$$$;
- 选择 $$$[1, \underline{6}, 7]$$$; $$$6$$$是它们的中位数,所以不会被擦除,得到的序列是$$$[2,3,4,5,6]$$$;
- 以及其他几个。

您可以执行零个或多个步骤。经过几步,你能得到序列 $$$b_1$$$, $$$b_2$$$, ..., $$$b_m$$$ 吗?

您将获得 $$$t$$$ 测试用例。独立解决每个测试用例。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$m$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$3 \le k \le n$$$; $$$k$$$ 是奇数; $$$1 \le m < n$$$) — 序列的长度,您在每个步骤中选择的元素数量以及您想要获得的序列的长度。

每个测试用例的第二行包含 $$$m$$$ 整数 $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_1 < b_2 < \dots < b_m \le n$$$) - 您想要获取的序列,按升序给出。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果可以获得序列 $$$b$$$,则打印 YES,否则打印 NO。您可以在任何情况下打印每个字母(例如,YES、Yes、yes、yE 都将被识别为肯定答案)。

示例

输入 #1

4
3 3 1
1
7 3 3
1 5 7
10 5 3
4 5 6
13 7 7
1 3 5 7 9 11 12

输出 #1

NO
YES
NO
YES

注意

在第一个测试用例中,您有序列 $$$[1, 2, 3]$$$。由于 $$$k = 3$$$,您只有一种方法来选择 $$$k$$$ 元素 - 即选择中位数为 $$$2$$$ 的所有元素 $$$[1, \underline{2}, 3]$$$。这就是为什么在删除除中位数之外的所有选定元素后,您将得到序列 $$$[2]$$$。换句话说,无法得到序列 $$$b = [1]$$$ 作为结果。

在第二个测试用例中,您有序列 $$$[1, 2, 3, 4, 5, 6, 7]$$$,最佳策略之一如下:

1. 选择 $$$k = 3$$$ 元素 $$$[2, \underline{3}, 4]$$$ 并删除除中位数之外的所有元素;你会得到序列 $$$[1, 3, 5, 6, 7]$$$;
2. 选择$$$3$$$元素$$$[3, \underline{5}, 6]$$$并删除除中位数之外的所有元素;你会得到想要的序列 $$$[1, 5, 7]$$$;

在第四个测试用例中,序列为 $$$[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]$$$。您可以选择 $$$k=7$$$ 个元素 $$$[2, 4, 6, \underline{7}, 8, 10, 13]$$$ 并删除除中位数之外的所有元素,得到序列 $$$b$$$。