一、题目描述

原题链接

令序列的值是其中所有数字的总和。

确定是否存在长度为$n$的排列，使得该排列的所有长度为$k$的子段的值共享相同的奇偶校验。这些值具有相同的奇偶性意味着它们都是奇数或它们都是偶数。

排列的子段是该排列的连续子序列。长度为 $n$ 的排列是一个序列，其中从 $1$ 到 $n$ 的每个整数恰好出现一次。

二、解题思路

  题目汇固定好了子段长度 $k$，说明本身题目是一个长度为 $k$ 的滑动窗口，要构造摆列使所有窗口和奇偶判定相同，对于滑窗运动时数据是一进一出的，再想对于和的奇偶性关系，从数学中我们可以知道若窗口中新进入的元素和滑出元素的奇偶性相同时，和的奇偶性就不会被改变，这是该题一个很重要的结论。

  那么如何构造？对于上面的结论，是以动态的角度分析了数据的特性，那么我们现在想象窗口每次直接动 $k$ 次，会发现什么？根据上面的结论，我们就会知道：下标(从 $1$ 开始)$1、1+k、1+2k...$奇偶性一定相同，$2、2+k、2+2k...$奇偶性一定相同，以此类推······我们发现其实这就是若干个长度为 $k$ 的循环节，下一步就要想如何构造循环节中的数据呢？很显然，循环节中一定要保证奇数和偶数的个数差最小，因为这样才会尽量的避免循环节还没跑完奇数或偶数已经分配完的情况，对于长度为 $k$ 的循环节其中有 $\lceil \frac{k}{2} \rceil$ 个奇数，有 $\lfloor \frac{k}{2} \rfloor$ 个偶数（排列中奇数的数量 >= 偶数数量，多分配偶数只会让其更快消耗完），这样就能保证在满足条件的同时奇偶相差的越小，如果在这一步发现奇数或偶数不够分，很显然在这一步直接回答 $NO$ 就可以。

  在分配完循环节后，下一步就是处理剩下几个数，该怎么分配。对于前面我们只是分配了每个循环节中需要的奇数和偶数数量，并没有具体的排位，这一点就是为了最后几个无法组成循环节的数来服务。我们会发现只要把后面的几个数排列方式确定，那么前面的循环节照着随便排即可，现在就要看怎么排最后几个数是合法的。剩下的数说到底可以算为循环节的一个子集，也就是它会满足循环节的上限条件，绝对不会超过出现上界的情况，再一想前面我们定义的循环节上界：对于长度为 $k$ 的循环节其中有 $\lceil \frac{k}{2} \rceil$ 个奇数，有 $\lfloor \frac{k}{2} \rfloor$ 个偶数，因此只要去看剩下的奇数和偶数有没有超过这两个的其中之一，如果有超过那一定不满足条件，如果没有那一定可以通过组合的方式使前面的循环节按照其规律太排序，满足题目条件，因此题目解决。

为什么 $k\ mod \ 2 = 0$时一定为YES？在 $k$ 为偶数的情况下，每个循环节奇偶使用是稳定相等的，在最后剩余的几个数中，也一定会有足够的奇数和偶数来填满，并且保证不会超过限制。

三、AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void sol(){
    ll n,k;
    cin >> n >> k;
    if(k == 1){
        if(n == 1){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
        return;
    }
    if(k % 2 == 0){
        cout << "YES" << endl;
        return;
    }

    ll z = n / k;//一共有z组
    ll c = n % k;//z组后剩了几个数
    ll zongji = (n + 1) / 2; //n个数中一个有多少个奇数
    ll zongou = n / 2;
    ll zuji = (k + 1)/2; //每组中有多少个奇数
    ll zuou = k / 2;
    ll shengji = zongji - z * ((k+1) / 2); //分了z组后一共有多少个奇数
    ll shengou = zongou - z * (k / 2);
    if(shengji >= 0 && shengou >= 0){
        if(shengji <= zuji && shengou <= zuou){
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        sol();
    }

    system("pause");
    return 0;
}