CF1363A Odd Selection题解

__shadow__ · 2021-02-22 19:32:51 · 题解

【问题分析】

因为要求和是奇数，所以可以想到想到以下定律：

• 1+0\equiv1(\bmod2)
• 1+1\equiv0(\bmod2)
• 0+0\equiv0(\bmod2)

所以不管什么数加上偶数，它的奇偶性都不会改变。

因此我们发现偶数只有凑数量的作用，只有奇数可以对结果的奇偶性产生影响。

同时由上面的规律还可得奇数必须由奇数个奇数和任意个偶数组成，所以我们就先统计出可使用奇数的个数（因为是奇数个奇数，所以如果总共有偶数个的话就要减去 1 ）。

之后分成几种情况：

• 判断有无奇数；
• 判断需要的数字个数大于可用奇数个数时，偶数够不够补上；
• 判断需要的数字个数小于可用奇数个数时，是否要奇数个数，或者要偶数个数时有无偶数；

【设计程序】

#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<queue>
using namespace std;
int n, x, t, sum;//sum是奇数个数 
int main()
{
    int Q;//Q是数据组数 
    scanf ("%d", &Q);
    while (Q--)
    {
        sum = 0;//奇数个数归零 
        scanf ("%d%d", &n, &x);//n是有几个数  x是要取几个数 
        for (int i = 1;i <= n; i++)
        {
            scanf ("%d", &t);//输入这个数 
            if (t % 2 != 0)//如果是奇数 
                sum++;//sum 加一 
        }
        if (!sum)//如果没有奇数，肯定不行 
        {
            printf ("No\n");
            continue;
        } 
        if (sum % 2 == 0)//如果有偶数个奇数 
        {
            sum--;//奇数个数减一 
            n--;//因为要用（n-sum）算偶数个数，所以n也要减一 
        }
        if (x >= sum && (x - sum) <= (n - sum))
        //如果x比sum大，并且偶数数量足够补空 
        {
            printf ("Yes\n");//输出可行 
            continue;
        }
        if (x < sum)//如果x比sum小 
        {
            if((n - sum) > 0 || x % 2 != 0)
            //当有一个偶数或要奇数个数时 
            {
                printf ("Yes\n");//输出可行 
                continue;
            }
        }
        printf ("No\n");//剩下的情况输出不行 
    }
    return 0;
}

有错误欢迎私信指出。