P4758. 奇偶之选

场次：2026年4月11日-开发岗 · 来源：CodeFun2000 P4758

题目描述

探险家发现了一排共 $n$ 个宝箱，从左到右编号为 $1$ 到 $n$，第 $i$ 个宝箱内装有价值为 $a_i$ 的宝石。探险家需要按顺序将这些宝箱两两划为一组：第 $1$ 和 $2$ 个宝箱为第一组，第 $3$ 和 $4$ 个宝箱为第二组，以此类推。若 $n$ 为奇数，则最后一个宝箱单独成为一组。

探险家计划恰好打开 $x$ 组宝箱，并从每一组被打开的两个（或一个）宝箱中，挑选恰好一个宝箱取出其中的宝石。他的目标是让所有取出的宝石的总价值为奇数。

请你判断是否存在一种选择方案，使得总价值为奇数。

约束条件：

• 测试数据组数 $t$ 满足 $1 \le t \le 10^4$。
• 每组数据中宝箱个数 $n$ 满足 $1 \le n \le 2 imes 10^5$，需要打开的小组数 $x$ 满足 $1 \le x \le \lceil n/2 \rceil$。
• 宝箱内宝石的价值 $a_i$ 满足 $0 \le a_i \le 10^9$。
• 所有测试数据的 $n$ 之和不超过 $2 imes 10^5$。

输入格式

第一行输入一个整数 $t$，表示测试数据组数。 接下来对于每组测试数据，按以下格式给出： 第一行包含两个整数 $n$ 和 $x$，分别表示宝箱数量与需要打开的小组数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个宝箱内宝石的价值。

输出格式

对于每组测试数据，输出一行，若存在一种方案使得取出宝石的总价值为奇数，输出 "Yes"，否则输出 "No"。

示例

示例 1

输入：

4
4 2
1 2 3 4
4 2
1 3 2 4
4 2
1 3 5 7
1 1
2

输出：

Yes
Yes
No
No

说明：

第一组数据：$n=4$，$x=2$，宝箱价值为 1 2 3 4。按顺序分组为 $(1,2)$ 和 $(3,4)$。每组内两个宝箱的奇偶性均不相同（一个奇数一个偶数），属于灵活盒子（mix）。只要存在灵活盒子，就可以通过调整选择来改变总和的奇偶性，因此必定能选出奇数总和，输出 Yes。

第二组数据：宝箱价值为 1 3 2 4。分组为 $(1,3)$ 和 $(2,4)$。第一组两个奇数（odd），第二组两个偶数（even），没有灵活盒子。需要打开 $x=2$ 组，设选择 odd 组的数量为 $k$。总和奇偶性只取决于 $k$ 的奇偶性，因此 $k$ 必须为奇数。由 $x=2$ 和 even 组个数为 1，可得 $k \ge 2-1=1$，且 $k \le \min(2,1)=1$，因此 $k$ 只能取 1，恰为奇数，方案存在，输出 Yes。

第三组数据：宝箱价值为 1 3 5 7。两组均为奇数，odd=2，even=0。打开 $x=2$ 组需要选 $k$ 个 odd 组。此时 $k$ 只能取 2（偶数），无法得到奇数个 odd 组，总和必定为偶数，输出 No。

第四组数据：$n=1$，$x=1$，唯一宝箱价值为 2（偶数）。只能选择该偶数，总和为偶数，无法得到奇数，输出 No。