CF2271B MEX Game

对于一个多重集 $\mathcal{S}$ 和一个正整数 $k$，定义 $\operatorname{mex}_k(\mathcal{S})$ 为在 $\mathcal{S}$ 中出现次数少于 $k$ 次的最小非负整数。特别地，$\operatorname{mex}_1(\mathcal{S})$ 就是 $\mathcal{S}$ 的通常意义下的 $\operatorname{mex}$ $^{\text{∗}}$。 例如： - $\operatorname{mex}_1(\{0, 1, 1, 2\}) = 3$； - $\operatorname{mex}_2(\{0, 0, 1, 1, 1, 3\}) = 2$； - $\operatorname{mex}_2(\{0, 1, 1, 2\}) = 0$； - $\operatorname{mex}_2(\{0, 0, 1, 2\}) = 1$。 给定一个偶数 $n$、一个正整数 $k$ 和 $n$ 张卡片。第 $i$ 张卡片上写着整数 $a_i$。 Alice 和 Bob 用这些卡片进行如下游戏。Alice 先手，两人轮流操作。每回合当前玩家可以拿走剩下卡片中的任意一张。游戏直到所有 $n$ 张卡片都被取走结束，因此每位玩家最终都拿到 $\dfrac{n}{2}$ 张卡片。 令 $\mathcal{A}$ 表示 Alice 拿到卡片上的整数组成的多重集，$\mathcal{B}$ 表示 Bob 拿到卡片上的整数组成的多重集。当且仅当 $\operatorname{mex}_k(\mathcal{A}) \ne \operatorname{mex}_k(\mathcal{B})$ 时 Alice 获胜，否则 Bob 获胜。 若双方都采取最优策略，判断 Alice 是否能获胜。 $^{\text{∗}}$ 最小遗漏非负整数（MEX）：对于由 $c_1, c_2, \ldots, c_m$ 组成的整数集合，MEX 定义为没有出现在集合 $c$ 中的最小非负整数 $x$。

每组数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每组测试用例的描述。 每组测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 2 \cdot 10^5$，$n$ 为偶数，$1 \le k \le n$），分别表示卡片数和游戏参数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le n$），表示每张卡片上写的数字。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试用例，如果 Alice 能获胜，输出 "YES"；否则输出 "NO"。 输出时不区分大小写。例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被判定为正解。

在第一个样例中，Alice 可以在第一回合选择一张数字为 $1$ 的卡片，第二回合选一张数字为 $0$ 的卡片。此时 $\mathcal{A} = \{0, 1\}$，$\mathcal{B} = \{0, 2\}$，所以 $\operatorname{mex}_1(\mathcal{A}) = 2$，$\operatorname{mex}_1(\mathcal{B}) = 1$。可以证明无论 Bob 如何选择，Alice 都一定能赢，所以答案是 "YES"。 在第二个样例中，两人取牌的顺序可以是：Alice 取 $1$，Bob 取 $1$，Alice 取 $0$，Bob 取 $0$。此时 $\mathcal{A} = \mathcal{B} = \{0, 1\}$，$\operatorname{mex}_1(\mathcal{A}) = \operatorname{mex}_1(\mathcal{B}) = 2$。可以证明当双方采取最优操作时，Bob 一定能获胜，所以答案是 "NO"。 由 ChatGPT 5 翻译