CF2271B.MEX Game

入门

通过率:0%

时间限制:1.50s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

For a multiset S\mathcal{S} and a positive integer kk, let mex⁡k(S)\operatorname{mex}_k(\mathcal{S}) be the smallest non-negative integer that appears in S\mathcal{S} fewer than kk times. In particular, mex⁡1(S)\operatorname{mex}_1(\mathcal{S}) is the usual mex⁡\operatorname{mex}^{\text{∗}}$ of mathcalS\\mathcal{S}.

For example:

  • mex⁡1(0,1,1,2)=3\operatorname{mex}_1({0, 1, 1, 2}) = 3;
  • mex⁡2(0,0,1,1,1,3)=2\operatorname{mex}_2({0, 0, 1, 1, 1, 3}) = 2;
  • mex⁡2(0,1,1,2)=0\operatorname{mex}_2({0, 1, 1, 2}) = 0;
  • mex⁡2(0,0,1,2)=1\operatorname{mex}_2({0, 0, 1, 2}) = 1.

You are given an even integer nn, a positive integer kk, and nn cards. The integer aia_i is written on the ii-th card.

Alice and Bob play the following game with these cards. Alice moves first, and the players alternate turns. On each turn, the current player takes any one of the remaining cards. The game ends when all nn cards have been taken, so each player ends up with exactly n2\dfrac{n}{2} cards.

Let A\mathcal{A} be the multiset of integers written on Alice's cards, and let B\mathcal{B} be the multiset of integers written on Bob's cards. Alice wins if mex⁡k(A)≠mex⁡k(B)\operatorname{mex}_k(\mathcal{A}) \ne \operatorname{mex}_k(\mathcal{B}), and Bob wins otherwise.

Determine whether Alice wins if both players play optimally.

∗^{\text{∗}}The minimum excluded (MEX) of a collection of integers c1,c2,…,cmc_1, c_2, \ldots, c_m is defined as the smallest non-negative integer xx which does not occur in the collection cc.

对于多重集 S\mathcal{S} 和正整数 kk,定义 mex⁡k(S)\operatorname{mex}_k(\mathcal{S}) 为在 S\mathcal{S} 中出现次数少于 kk 次的最小非负整数。特别地,mex⁡1(S)\operatorname{mex}_1(\mathcal{S}) 即为通常意义下的 mex⁡∗\operatorname{mex}^{\text{∗}}(最小未出现值)。

例如:

  • mex⁡1({0,1,1,2})=3\operatorname{mex}_1(\{0, 1, 1, 2\}) = 3;
  • mex⁡2({0,0,1,1,1,3})=2\operatorname{mex}_2(\{0, 0, 1, 1, 1, 3\}) = 2;
  • mex⁡2({0,1,1,2})=0\operatorname{mex}_2(\{0, 1, 1, 2\}) = 0;
  • mex⁡2({0,0,1,2})=1\operatorname{mex}_2(\{0, 0, 1, 2\}) = 1。

给定一个偶数 nn、一个正整数 kk 和 nn 张卡片。第 ii 张卡片上写有一个整数 aia_i。

Alice 和 Bob 使用这些卡片进行如下游戏:Alice 先手,双方轮流进行操作。在每一轮中,当前玩家从剩余卡片中任取一张。当所有 nn 张卡片均被取完时游戏结束,因此每位玩家最终恰好获得 n2\dfrac{n}{2} 张卡片。

令 A\mathcal{A} 表示 Alice 手中卡片上所写整数构成的多重集,B\mathcal{B} 表示 Bob 手中卡片上所写整数构成的多重集。若 mex⁡k(A)≠mex⁡k(B)\operatorname{mex}_k(\mathcal{A}) \ne \operatorname{mex}_k(\mathcal{B}),则 Alice 获胜;否则 Bob 获胜。

假设双方均以最优策略进行游戏,请判断 Alice 是否必胜。

∗^{\text{∗}} 一组整数 c1,c2,…,cmc_1, c_2, \ldots, c_m 的最小未出现值(MEX)定义为不在该集合 cc 中出现的最小非负整数 xx。

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains two integers nn and kk (2≤n≤2⋅1052 \le n \le 2 \cdot 10^5, nn is even, 1≤k≤n1 \le k \le n) — the number of cards and the parameter of the game.

The second line of each test case contains nn integers a1,a2,…,ana_1, a_2, \ldots, a_n (0≤ai≤n0 \le a_i \le n) — the integers written on the cards.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052 \cdot 10^5.

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 nn 和 kk(2≤n≤2⋅1052 \le n \le 2 \cdot 10^5,nn 为偶数,1≤k≤n1 \le k \le n)—— 分别表示卡片的数量和游戏的参数。

每个测试用例的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n(0≤ai≤n0 \le a_i \le n)—— 表示写在卡片上的整数。

保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5。

输出格式

For each test case, output "YES" if Alice wins, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个测试用例,如果 Alice 获胜,则输出 “YES”,否则输出 “NO”。

您可以以任意大小写形式输出答案(大写或小写)。例如,字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。

输入输出样例

  • 输入#1

    5
    4 1
    2 0 0 1
    4 1
    0 1 0 1
    6 2
    1 2 0 1 0 0
    6 2
    0 0 1 1 2 2
    8 2
    0 1 1 0 0 2 0 1

    输出#1

    YES
    NO
    YES
    NO
    YES

说明/提示

In the first example, Alice can take the card showing 11 on her first turn and a card showing 00 on her second turn. Then A=0,1\mathcal{A} = {0, 1} and B=0,2\mathcal{B} = {0, 2}, so mex⁡1(A)=2\operatorname{mex}_1(\mathcal{A}) = 2 and mex⁡1(B)=1\operatorname{mex}_1(\mathcal{B}) = 1. It can be proven that Alice wins regardless of Bob's moves, so the answer is "YES".

In the second example, the players can take cards in the following order: Alice takes 11, Bob takes 11, Alice takes 00, and Bob takes 00. Then A=B=0,1\mathcal{A} = \mathcal{B} = {0, 1} and mex⁡1(A)=mex⁡1(B)=2\operatorname{mex}_1(\mathcal{A}) = \operatorname{mex}_1(\mathcal{B}) = 2. It can be proven that Bob wins if both players play optimally, so the answer is "NO".

在第一个例子中,Alice 可以在第一回合取走显示数字 11 的卡片,在第二回合取走显示数字 00 的卡片。此时 A={0,1}\mathcal{A} = \{0, 1\},B={0,2}\mathcal{B} = \{0, 2\},因此 mex⁡1(A)=2\operatorname{mex}_1(\mathcal{A}) = 2,mex⁡1(B)=1\operatorname{mex}_1(\mathcal{B}) = 1。可以证明,无论 Bob 如何行动,Alice 均获胜,因此答案为 "YES"。

在第二个例子中,双方玩家按如下顺序取牌:Alice 取 11,Bob 取 11,Alice 取 00,Bob 取 00。此时 A=B={0,1}\mathcal{A} = \mathcal{B} = \{0, 1\},且 mex⁡1(A)=mex⁡1(B)=2\operatorname{mex}_1(\mathcal{A}) = \operatorname{mex}_1(\mathcal{B}) = 2。可以证明,若双方均采取最优策略,则 Bob 获胜,因此答案为 "NO"。

输入解题思路,AI测评打分。不知道怎么写?

首页