前言

• 比赛链接

没什么好说的，丫的为啥不用开 \(freopen\) ，我全开了 qwq。

很好的全部爆零，他题面里明明要求 \(freopen\) ，但是标准输入输出，没这个经验，长个见识吧就当。

去了 \(freopen\) 后：

• \(T1\) 大模拟，不好打但肯调就能出。
• 剩下的都不是很会，打到 \(T4\) 愣了半天题面就结束比赛了,\(T3\) 该死的捆绑测试，所以没骗来分。

\(\text{NOIP}\) 模拟赛，头一回做这种难度的，能做出来一道知足了。

T1 小P的2048

• 题意：

  题面挺长的，里面有一些地方不太容易懂，多读几遍理解题意后就没那么难了。

  把图沾过来吧，方便解释：

  

  1. 平移：

     他这个平移不是平移某一个棋子，是把整个棋盘的所有棋子都平移。

     以向上平移为例，就是把所有棋子向上挪直到全部顶到头，\(eg:\)

     

  2. 合并：

     不能连续合并，却能同时合并多对，具体是什么意思？

     \(eg:\)

     

• 数据范围：

  \(2\leq n\leq 8\) ，随便跑就完事了，不用担心时间复杂度。

• 解法：

  按照题意大模拟即可。

  原矩阵为 \(a_{i,j}\) ，定义新矩阵为 \(b_{i,j}\) ，用于存移动后的状况，移动完后另 \(a=b\) ，\(b\) 清空。

  • 处理平移与合并：

    直接看代码理解比较方便：

    0. 上移：

       if(x==0)
       {
           for(int j=1;j<=n;j++)
           {
               int cnt=0;//全部顶到头。
               for(int i=1;i<=n;i++)
                   if(a[i][j]!=0)
                   {
                       if(b[cnt][j]==a[i][j]&&num==0)//合并，不可连续合并。
                           b[cnt][j]+=a[i][j],
                           ans+=b[cnt][j],
                           num++;
                       else 
                       {
                           if(num>0) num=0;
                           b[++cnt][j]=a[i][j];
                       }
                   }
           }
       }
       

    1. 下移：

       else if(x==1)
       {
           for(int j=1;j<=n;j++)
           {
               int cnt=n+1;
               for(int i=n;i>=1;i--)
                   if(a[i][j]!=0)
                   {
                       if(b[cnt][j]==a[i][j]&&num==0)
                           b[cnt][j]+=a[i][j],
                           ans+=b[cnt][j],
                           num++;
                       else 
                       {
                           if(num>0) num=0;
                           b[--cnt][j]=a[i][j];
                       }
                   }
           }
       }
       

    2. 左移：

       else if(x==2)
       {
           for(int i=1;i<=n;i++)
           {
               int cnt=0;
               for(int j=1;j<=n;j++)
                   if(a[i][j]!=0)
                   {
                       if(b[i][cnt]==a[i][j]&&num==0)
                           b[i][cnt]+=a[i][j],
                           ans+=b[i][cnt],
                           num++;
                       else 
                       {
                           if(num>0) num=0;
                           b[i][++cnt]=a[i][j];
                       }
                   }
           }
       }
       

    3. 右移：

       else if(x==3)
       {
           for(int i=1;i<=n;i++)
           {
               int cnt=n+1;
               for(int j=n;j>=1;j--)
                   if(a[i][j]!=0)
                   {
                       if(b[i][cnt]==a[i][j]&&num==0)
                           b[i][cnt]+=a[i][j],
                           ans+=b[i][cnt],
                           num++;
                       else 
                       {
                           if(num>0) num=0;
                           b[i][--cnt]=a[i][j];
                       }
                   }
           }
       }
       

  • 处理新加的点：

    先一遍循环，处理出剩几个空点，按照题面定义 \(s=1+k\bmod sum\) （ \(k\) 见题面，为输入进来的）。

    再来一遍循环，到第 \(s\) 个为 \(0\) 的 \(a_{i,j}\) 改成 \(v\) 即可（ \(v\) 也是输进来的）。

  • 处理何时结束：

    很简单，如果进行过第 \(i\) 遍时 \(a\) 和上一次没有任何变化，那第 \(i\) 次操作就是无用的,也就是共可以进行 \(i-1\) 步，输出，结束程序即可。

    具体只需要在将 \(b\) 复制到 \(a\) 前比较 \(a,b\) 数组即可。

• 代码如下：

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
int n,m,a[N][N],num,ans,sum,b[N][N];
signed main()
{
	#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    read(n),read(m);
    int x,y,z;
    for(int i=1;i<=2;i++)   
        read(x),read(y),read(z),
        a[x][y]=z;
    for(int t=1;t<=m;t++)
    {
        read(x),read(y),read(z);
        memset(b,0,sizeof(b));
        num=0;
        if(x==0)
        {
            for(int j=1;j<=n;j++)
            {
                int cnt=0;
                for(int i=1;i<=n;i++)
                    if(a[i][j]!=0)
                    {
                        if(b[cnt][j]==a[i][j]&&num==0)
                            b[cnt][j]+=a[i][j],
                            ans+=b[cnt][j],
                            num++;
                        else 
                        {
                            if(num>0) num=0;
                            b[++cnt][j]=a[i][j];
                        }
                    }
            }
        }
        else if(x==1)
        {
            for(int j=1;j<=n;j++)
            {
                int cnt=n+1;
                for(int i=n;i>=1;i--)
                    if(a[i][j]!=0)
                    {
                        if(b[cnt][j]==a[i][j]&&num==0)
                            b[cnt][j]+=a[i][j],
                            ans+=b[cnt][j],
                            num++;
                        else 
                        {
                            if(num>0) num=0;
                            b[--cnt][j]=a[i][j];
                        }
                    }
            }
        }
        else if(x==2)
        {
            for(int i=1;i<=n;i++)
            {
                int cnt=0;
                for(int j=1;j<=n;j++)
                    if(a[i][j]!=0)
                    {
                        if(b[i][cnt]==a[i][j]&&num==0)
                            b[i][cnt]+=a[i][j],
                            ans+=b[i][cnt],
                            num++;
                        else 
                        {
                            if(num>0) num=0;
                            b[i][++cnt]=a[i][j];
                        }
                    }
            }
        }
        else if(x==3)
        {
            for(int i=1;i<=n;i++)
            {
                int cnt=n+1;
                for(int j=n;j>=1;j--)
                    if(a[i][j]!=0)
                    {
                        if(b[i][cnt]==a[i][j]&&num==0)
                            b[i][cnt]+=a[i][j],
                            ans+=b[i][cnt],
                            num++;
                        else 
                        {
                            if(num>0) num=0;
                            b[i][--cnt]=a[i][j];
                        }
                    }
            }
        }
        bool flag=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][j]!=b[i][j])
                {
                    flag=1;
                    break;
                }
        if(!flag) cout<<t-1<<endl<<ans,exit(0);
        flag=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][j]!=0)
                {
                    flag=1;
                    break;
                }
        if(!flag) cout<<t-1<<endl<<ans,exit(0);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                a[i][j]=b[i][j];
        sum=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][j]==0)
                    sum++;
        int s=1+(y%sum);
        sum=0;
        for(int i=1;i<=n;i++)   
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]==0) 
                {
                    sum++;
                    if(sum==s) 
                    {
                        a[i][j]=z;
                        break;
                    }
                }
            }
    }
    cout<<m<<endl<<ans;
}

T2 子集

• 题意:

  给定两正整数 \(n,k\) 且 \(k|n\) 。

  已知集合为 \(1\sim n\) ,求出 \(k\) 个互无交集的子集，且子集内元素和均相等。

• 解法：

  打表 。

  设 \(m=\dfrac{n}{k}\) ，表示每个子集中元素的数量。

  • 判无解：

    1. 首先如果 \(n\neq 1,k=n\) ，则一定无解，很显然。

    2. 若 \(n\) 为偶数，且 \(m\) 为奇数，则无解：

       ∵ \(n|m\) ，\(n\) 为偶数，\(m\) 为奇数；设 \(n=2a\times (2b+1)\) 。\(2a=k,2b+1=m\) .

       则 \(\sum\limits_{i=1}^ni=\dfrac{(n+1)n}{2}=\dfrac{[2a(2b+1)+1]\times 2a(2b+1)}{2}\) 。

       则平均到 \(2a\) 个子集，每个子集元素和为 \(\dfrac{[2a(2b+1)+1]\times 2a(2b+1)}{2\times 2a}=a(2b+1)^2+\dfrac{2b+1}{2}\) ，显然这个数不是整数，所以无解。

  • 简单——\(m\) 为偶数：

    显然输出一个 \(i\) ，一个 \(n-i+1\) 就行了，部分分就是这么来的。

  • 难点——\(n,m\) 均为奇数：

    极其巧妙的做法：先按照上面方式搞，直到每一组剩下 \(3\) 个元素未填。

    接下来的问题就转换成如何排这 \(m=3\) 的情况。

    以 \(n=15,k=5\) 为例：

    

    1. 先将最大的 \(k\) 个分别按从大到小顺序排到每一组，因为不会存在这 \(k\) 个中有 \(2\) 个在同一组。（排序是为了方便）。

    2. 根据公式 \(\dfrac{(n+1)n}{2k}\) 求出每个子集元素和 \(sum\) ，那么此时求出放完第一列后，每一组还需要多少，记作 \(val_i\) ，设 \(val_i=a_i+b_i\) ，分别表示 \(2,3\) 列。

    3. 接下来的步骤就变成了如何用剩下两列凑出每个 \(val_i\) ，此处需要分类讨论（接下来思路不易推出，可以结合上面的图）：

       • \(i\) 为奇数：

         为什么要分类讨论呢？

         显然的，\(val_{i+1}-val_i=1\) ，∴ \(val_{i+2}-val_i=2\) ，这样的话就可以使 \(a_{i+2}-a_i=1,b_{i+2}-b_i=1\) 。这样的话 \(a,b\) 分别从 \(1,val_1-1\) 开始递增即可，参考上图。

       • \(i\) 为偶数：

         和上面一样的，但从剩下的数中选，\(a,b\) 从 \(\dfrac{n+3}{2},val_2-(\dfrac{n+3}{2})\) 递增即可，参考上图。

         具体为什么是从 \(\dfrac{n+3}{2}\) 开始，∵ \(n,k\) 均为奇数，那么 \(i\) 为奇数的情况用去了 \(1\sim \dfrac{n+1}{2}\) ，所以到偶数就从 \(\dfrac{n+3}{2}\) 开始轮了。

    好了现在规律找出来了，怎么输出还是个问题。

    所以就需要将上面的规律转化为能用 \(i,k\) 表示的公式，依旧是分类讨论，按照上面的思路来：

    • \(i\) 为奇数：

      1. 输出第一列：\(3k-i+1\) ，在这里 \(3k\) 就是上面 \(n\) 的意思了。
      2. 输出第二列：\(\dfrac{i+1}{2}\) 。
      3. 输出第三列：\(\dfrac{3k+i}{2}\) 。

    • \(i\) 为偶数：

      1. 输出第一列：\(3k-i+1\) ,和上面一样的。
      2. 输出第二列：\(\dfrac{k+i+1}{2}\) 。
      3. 输出第三列：\(\dfrac{2k+i}{2}\) 。

    这里需要解释一下：

    首先在第一列的数为 \(2k+1\sim 3k\) ，第二列为 \(1\sim k\) ，第三列为 \(k+1\sim 2k\) 。

    参照上面的思路与图片，不难发现第二列是 \(i\) 为奇数优先，而第三列是 \(i\) 为偶数优先。

    • 在第二列时：

      奇数优先从 \(1\sim\dfrac{k+1}{2}\) 中选，则转化为 \(i\) 就是 \(\dfrac{i+1}{2}\) 。

      而偶数则是在 \(\dfrac{k+3}{2}\sim k\) 中选，原本按奇数那个来就是 \(\dfrac{i}{2}\) ，但是每一个都对应加上 \(\dfrac{k+1}{2}\) ，就变为 \(\dfrac{k+i+1}{2}\) 。

    • 在第三列时：

      偶数优先从 \(k+1\sim \dfrac{3k-1}{2}\) 中选，则转化为 \(i\) 就是 \(k+\dfrac{i}{2}=\dfrac{2k+i}{2}\) 。

      而奇数则是在 \(\dfrac{3k+1}{2}\sim 2k\) 中选，若按偶数那个来就是 \(\dfrac{i+1}{2}\) ，单是每一个都加上 \(\dfrac{3k-1}{2}\) ，就变为 \(\dfrac{3k+i}{2}\) 。

    • 最后证明：

      由于 \(n,m,k\) 均为奇数，所以 \(i\) 为奇数的情况占 \(\dfrac{k+1}{2}\) ，而 \(i\) 为偶数的情况占 \(\dfrac{k-1}{2}\) ，上面奇偶分别所选范围就是这么来的。

    只需要先把这三列先输出，剩下的按照 \(m\) 为偶数那么来就可以了，当然这两部也可以调换，不过会稍微麻烦一点点，需要找到这三列里第一个数 \(s\) ，把上面的公式都加上 \(s-1\) 即可；若不换就直接用上面公式。

• 代码如下：

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
int t,n,m,k;
signed main()
{
	#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    read(t);
    while(t--)
    {
        read(n),read(k);
        
        int m=n/k;
        if((n%2==0&&m&1)||(m==1&&n!=1)) 
        {
            cout<<"No"<<endl;
            continue;
        }
        cout<<"Yes"<<endl;
        if(k==1)
        {
            for(int i=1;i<=n;i++) cout<<i<<' ';
            cout<<endl;
            continue;
        }
        if(m%2==0) 
        {
            int cnt=0;
            for(int i=1;i<=k;i++)
            {
                for(int j=1;j<=m/2;j++)
                    cout<<++cnt<<' '<<n-cnt+1<<' ';
                cout<<endl;
            }   
        }
        else 
        {
            int cnt=0,s=(n-k)/2-k+1;
            for(int i=1;i<=k;i++)
            {
                for(int j=1;j<=(m-3)/2;j++)
                    cout<<++cnt<<' '<<n-cnt+1<<' ';
                cout<<3*k+s-i<<' ';
                if(i&1) cout<<s+(i-1)/2<<' '<<s+k-1+(k+i)/2<<endl;
                else cout<<s+(k-1)/2+i/2<<' '<<s+k-1+i/2<<endl;//就是上面的公式加上 s-1 。
            }
        }
    }
}