P9671 [ICPC2022 Jinan R] Identical Parity 题解

· · 题解

P9671 [ICPC2022 Jinan R] Identical Parity

构造题。感觉中上位黄。

对于 k 为偶数的情况，构造奇偶交替的序列。每次区间向后挪动时，最左边出去的元素和最右边进来的元素奇偶性相同，保证奇偶性不变。这样的序列一定可以构造出来，故 k 为偶数时直接输出 Yes。

对于 k 为奇数的情况，每次区间向后挪动时，为了保证奇偶性不变，必须使最左边出去的元素和最右边进来的元素奇偶性相同。由于每一位都需要这样，所以最后一定是一段长度为 k 的奇偶序列重复多次。

由于 k 为奇数，每一段中必然会有一种奇偶性的数多 1，不如假设奇数较多。如果重复了 m 整段，那么奇数比偶数多 m 个。在剩余的散段中，为了保证奇偶数的差尽量小，我们要优先使偶数在前，补齐这个差值。

注意，由于我们假定偶数比奇数少，所以偶数数量最多为 k 的向下取整的一半。如果剩余的散段在补满了偶数之后任然有空位，那么只能在加入奇数。这里需要分类讨论。

由于最开始是排列，所以奇数和偶数的差不能超过 1。如果经过以上操作之后可以满足这个条件，输出 Yes，否则输出 No。

#include <bits/stdc++.h>
using namespace std;
long long t,n,k;
int main()
{
    scanf("%lld",&t);
    while(t--)
       {
       scanf("%lld%lld",&n,&k);
       if(k%2==0)printf("Yes\n");
       else if(k%2==1)
           {
           if(n%k<=k/2&&(n/k-n%k)<=1)printf("Yes\n");
           else if(n%k>k/2&&(n/k-k/2+(n%k-k/2))<=1)printf("Yes\n");
           else printf("No\n");
           }
       }
    return 0;
}

AC记录