Codeforces Round #646 (Div. 2) A. Odd Selection(思维/分类讨论)

A. Odd Selection

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Shubham has an array aa of size nn, and wants to select exactly xx elements from it, such that their sum is odd. These elements do not have to be consecutive. The elements of the array are not guaranteed to be distinct.

Tell him whether he can do so.

Input

The first line of the input contains a single integer tt (1≤t≤100)(1≤t≤100) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers nn and xx (1≤xn≤1000)(1≤x≤n≤1000) — the length of the array and the number of elements you need to choose.

The next line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1000)(1≤ai≤1000) — elements of the array.

Output

For each test case, print "Yes" or "No" depending on whether it is possible to choose xx elements such that their sum is odd.

You may print every letter in any case you want.

Example

Input

Copy

5

1 1

999

1 1

1000

2 1

51 50

2 2

51 50

3 3

101 102 103

Output

Copy

Yes

No

Yes

Yes

No

 

这题还是有点思维量的。

首先paichu掉几种特殊的情况:

  1. 数组里全是偶数
  2. 数组里全是奇数且要求选出偶数个数(偶数个奇数的和还是偶数)
  3. n==x的话如果数组里奇数的个数是奇数是可以的,否则不可以。

然后剩下的情况一定都是可以的,因为此时x<n,且数组里有奇数有偶数,这样尽可能多的选偶数,尽可能少的选奇数来动态调整一定能选出来不会证

 

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,x,even=0,odd=0;
        cin>>n>>x;
        int i;
        for(i=1;i<=n;i++)
        {
            int temp;
            scanf("%d",&temp);
            if(temp&1)odd++;
            else even++;
        }
        //和是奇数 
        if(n==even)
        {
            cout<<"NO"<<endl;
            continue;
        }
        if(n==odd&&(!(x&1)))
        {
            cout<<"NO"<<endl;
            continue;
        }
        if(n==x)
        {
            if(odd&1)
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
            continue;
        }
        cout<<"YES"<<endl;
    }
    return 0;
}

 

上一篇:Java常见经典算法详解-选择排序(Selection Sort)


下一篇:提取EXCEL文字中的链接