HDU多校第三场 1003 Divide the Stones —— 构造

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $n$ 个数字 $1$ ~ $n$ ，分为 $k$ 组
    要求每组数字和相同
    若能分则输出分组的每个数

解题思路：

    讨论可以分的情况，设 $m=n/k$
    则问题转化为了将 $1$ 到 $n$ 填入 $m$ 行 $k$ 列的矩阵，每一列的和相等
    若 $m$ 为偶数，根据等差数列的相关性质，可以蛇形放入

    若 $m$ 为奇数，则很明显不能满足上述要求
    但是可以先处理出前三行，剩下的按照偶数处理
    发现前三行可以按照如下方法构造：
    第一行从 $1$ 到 $k$，第二行从中间开始往右递增，然后从第二行到中间再递增
    第三行根据第一二行构造即可

    如上所示，平均值代表那一行的平均值
    第一行代表前两行的和 与 前两行的和平均值的差值
    这样构造出来的差值不会重复，故可以用差值来构造第三行

核心：规律有点小奥妙

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <ll,int>;
int T, n, k, m;void gao1(){int tot = (1+3*k)*3/2;for(int i=1; i<=k; i++){for(int j=1; j<=m; j++){if(j == 1) printf("%d ", i);else if(j == 2) {if(i >= (k+1)/2) printf("%d ", i-(k+1)/2+k+1);else printf("%d ", i+k+(k+1)/2);}else if(j == 3){if(i >= (k+1)/2) printf("%d ", tot-i-(i-(k+1)/2+k+1));else printf("%d ", tot-i-(i+k+(k+1)/2));} else{if(j & 1) printf("%d ", (j-1)*k+i);else printf("%d ", j*k-i+1);}}puts("");}
}void gao2(){for(int i=1; i<=k; i++){for(int j=1; j<=m; j++){if(j & 1) printf("%d ", (j-1)*k+i);else printf("%d ", j*k-i+1);}puts("");}
}int main() {scanf("%d", &T);while(T--){scanf("%d%d", &n, &k);m = n / k;if(1ll*(n+1)*n/2 % k) {puts("no");continue;}puts("yes");if(m & 1) gao1();else gao2();}
}