CF2271B.MEX Game
入门
通过率:0%
时间限制:1.50s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
For a multiset S and a positive integer k, let mexk(S) be the smallest non-negative integer that appears in S fewer than k times. In particular, mex1(S) is the usual mex^{\text{∗}}$ of mathcalS.
For example:
- mex1(0,1,1,2)=3;
- mex2(0,0,1,1,1,3)=2;
- mex2(0,1,1,2)=0;
- mex2(0,0,1,2)=1.
You are given an even integer n, a positive integer k, and n cards. The integer ai is written on the i-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 n cards have been taken, so each player ends up with exactly 2n cards.
Let A be the multiset of integers written on Alice's cards, and let B be the multiset of integers written on Bob's cards. Alice wins if mexk(A)=mexk(B), and Bob wins otherwise.
Determine whether Alice wins if both players play optimally.
∗The minimum excluded (MEX) of a collection of integers c1,c2,…,cm is defined as the smallest non-negative integer x which does not occur in the collection c.
对于多重集 S 和正整数 k,定义 mexk(S) 为在 S 中出现次数少于 k 次的最小非负整数。特别地,mex1(S) 即为通常意义下的 mex∗(最小未出现值)。
例如:
- mex1({0,1,1,2})=3;
- mex2({0,0,1,1,1,3})=2;
- mex2({0,1,1,2})=0;
- mex2({0,0,1,2})=1。
给定一个偶数 n、一个正整数 k 和 n 张卡片。第 i 张卡片上写有一个整数 ai。
Alice 和 Bob 使用这些卡片进行如下游戏:Alice 先手,双方轮流进行操作。在每一轮中,当前玩家从剩余卡片中任取一张。当所有 n 张卡片均被取完时游戏结束,因此每位玩家最终恰好获得 2n 张卡片。
令 A 表示 Alice 手中卡片上所写整数构成的多重集,B 表示 Bob 手中卡片上所写整数构成的多重集。若 mexk(A)=mexk(B),则 Alice 获胜;否则 Bob 获胜。
假设双方均以最优策略进行游戏,请判断 Alice 是否必胜。
∗ 一组整数 c1,c2,…,cm 的最小未出现值(MEX)定义为不在该集合 c 中出现的最小非负整数 x。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The first line of each test case contains two integers n and k (2≤n≤2⋅105, n is even, 1≤k≤n) — the number of cards and the parameter of the game.
The second line of each test case contains n integers a1,a2,…,an (0≤ai≤n) — the integers written on the cards.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。随后是各测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 k(2≤n≤2⋅105,n 为偶数,1≤k≤n)—— 分别表示卡片的数量和游戏的参数。
每个测试用例的第二行包含 n 个整数 a1,a2,…,an(0≤ai≤n)—— 表示写在卡片上的整数。
保证所有测试用例的 n 之和不超过 2⋅105。
输出格式
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 1 on her first turn and a card showing 0 on her second turn. Then A=0,1 and B=0,2, so mex1(A)=2 and mex1(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 1, Bob takes 1, Alice takes 0, and Bob takes 0. Then A=B=0,1 and mex1(A)=mex1(B)=2. It can be proven that Bob wins if both players play optimally, so the answer is "NO".
在第一个例子中,Alice 可以在第一回合取走显示数字 1 的卡片,在第二回合取走显示数字 0 的卡片。此时 A={0,1},B={0,2},因此 mex1(A)=2,mex1(B)=1。可以证明,无论 Bob 如何行动,Alice 均获胜,因此答案为 "YES"。
在第二个例子中,双方玩家按如下顺序取牌:Alice 取 1,Bob 取 1,Alice 取 0,Bob 取 0。此时 A=B={0,1},且 mex1(A)=mex1(B)=2。可以证明,若双方均采取最优策略,则 Bob 获胜,因此答案为 "NO"。
输入解题思路,AI测评打分。不知道怎么写?