Codeforces 1363A - Odd Selection

日常一道算法题。

翻译

有一个长度为 n 的数组，想要正好挑选出 x 个元素，使他们的和 为 奇数。

输入格式

输入整数 t 表示测试用例组数，每个测试用例输入两行：

第一行输入 n， x，第二行输入 n 的数字，用空格分隔。

输出格式

输出 Yes 或者 No 表示能构造出答案或者不能构造出答案。

分析

稍微有一丢丢难度的构造题，错了几次，然后为了写题解又简化了一次代码。

先统计奇数数量和偶数数量，然后用 k - 偶数数量，如果结果为偶数需要判断偶数数量是否大于 0，最后使 k 为尽量小的奇数。

因为结果要奇数，所以奇数数量必须为奇数，所以上面要使 k 为奇数。

然后，判断 k 是否是奇数 并且 k 小于等于 奇数数量即可。

代码(PyPy3)

# https://codeforces.com/problemset/problem/1363/A

import sys
import os
import heapq
import math

try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass

t = int(input())

def printd(value):
    # print(value)
    pass

def case():
    arr = list(map(int, input().split(" ")))
    n, k = arr[0], arr[1]
    arr = list(map(int, input().split(" ")))

    odd = 0
    even = 0
    for number in arr:
        if number % 2 == 1:
            odd += 1
        else:
            even += 1

    k = max(1, k - even)
    if k % 2 == 0 and even > 0:
        k += 1
    
    if odd >= k and k % 2 == 1:
        print("Yes")
    else:
        print("No")

for _ in range(t):
    case()

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.06.03 长春