题目大意
一道构造题。
总结一下限制条件：
每行的平均数要在该行中出现；
每列的平均数要在该列中出现；
矩阵内的数字互不相同。
看一眼数据范围，发现 的范围只是 ，而矩阵中的数不大于 即可，所以操作空间还是很大的。
思路
首先可以发现的事情是：如果 是 奇数 的话，直接从上到下，从左到右，从 开始，每次 ，直接填即可（参考样例 ）。并且，如果 为奇数，那么最大为 ，而根据此方法，最后一个数最大，是 ，并没有超过 。
下面是简要证明：
可以发现填完之后，每一行每一列都是一个 等差序列，并且是 奇数 项，那么这就保证了 该序列的平均数一定出现在该序列中。同时，由于每次都 ，所以矩阵中也不会有相同的数。
接下来考虑 偶数。
从 奇数 的角度出发，但是如果直接填的话，虽然还是 等差序列，但是“平均数在序列中出现”这个限制就无法满足了。所以考虑进行一些调整，并且最终尽量缩小序列的值域（为避免超过 ）。
可以发现当 时是 无解 的，因为任意一行，任意一列都只有两个数，如果要使 “平均值出现在序列中” 的话，那么只有在 这两个数相等 的时候才能成立，可是题目又要求不能有相同的数字，所以 无解（换句话说就是根本没有调整的空间）。
那么接下来考虑 的情况。
先只考虑一个序列。如果直接填，可得 ，很明显，平均数不在序列中，于是进行微调。由于是“微调”，所以尽量让平均数还是在靠近中间的位置。那么我们钦定平均数为 （可能有人会问为什么不是 ，原因是如果选了 ，那么比平均数小的就只有一个 ，对平均数负方向的贡献就只有 ，而 的后面还有两个数，无法平衡），那么 和 对平均数负方向的贡献分别为 和 ，那么第 个数对平均值正方向的贡献就必须是 ，所以第 个数就应该是 。于是便得到了如下序列：。
但这只是一个序列，后面还有好多个序列要填，怎么办？
考虑一个很经典的做法，将序列的每一项都乘上同一个数。
正确性还是很显然的，每一项都扩大一个相同的倍数，那么平均数也会扩大相同的倍数，并且肯定也还在序列里（如果读者还是不信，请手玩几个序列）。
同时还可以发现一个性质：将序列的每一项都加上同一个数。
每个数都加上相同的数，那么平均数也会加上相同的数，同时依然还在序列中（这不用再证明了吧）。
那么我们就可以将第一行作为 基底，第二行乘 倍，第三行乘 倍，以此类推。然后我们就会发现，虽然每一行满足条件了，但是每一列却变成了等差数列（公差为第一行对应的那一列的那个数），并且是偶数项，是不满足题意的。
那么我们可以想到，现在每一行已经满足题意了，那么就让每一行之间 相差的倍数 也满足条件即可。
这里提出了“相差的倍数”这么一个东西，是什么意思呢？
举个例子：现在给出一个合法的序列：。计算相邻两项的差，得到 。如果将 差 的序列乘上 倍，再得到的新序列便是 ，可以发现该序列依然合法，并且平均数还是在第 个位置。
那么我们就让每一行之间相差的数也是一个合法的 差 的序列就可以了。
那么我们可以考虑填完第一行之后填第一列，然后根据每一行第一列的数，填完该行剩下的数。
那么整体上，我们要求每一行，小的数在左，大的数在右；每一列，小的数在上，大的数在下。
现在考虑当 时如何填。
首先第一行前面已经讨论过：。
由于数字不可重复，所以第一列中除了 ，不能再有 ，那么为了方便，此处可以暴力一点，直接取 （即为 ），也就是 。如下：
再填第二行（同理，也可以填第二列），（鉴于在第一列，我们已经控制好了每行之间的 差，所以对于每一行，类比于第一行，不用乘倍数，直接按照原始的 差的序列 填即可）。
第三行：。
第四行：。
于是得到了：
1
2
3
4
| 1 2 3 6
7 8 9 12
13 14 15 18
31 32 33 36
|
（最终输出时是不用管缩进的，此处只是为了看起来整齐）
同时我们可以发现，每一列中的某个数都是上面那个数再加上 差的序列 的对应的那一位再乘上第一行最后一个数那么多倍。
本来第一行中 和 之间差 ，但是最后一项是 ，于是第一列中 和 之间就差了 ，相当于是将 差的序列 扩大了 倍。
举几个例子：。
那么这样我们还可以省掉单独填第一列的操作，直接根据第一行填剩下的所有行即可。
这就是一个合法的矩阵，但可能还是会有人质疑为什么这样就一定不会重复。下面简单证明一下（可能说得有些模糊，得感性理解）。
首先每一行填的方法肯定是合法的，那么最右边的数就是这一行的最大值，而下一行的第一个数（也就是在填第一列时已经确定的数）是已经规定要比“最大值”大的。举个例子：第一行为 ，我们规定第二行第一个数是 ，同时第二行是 ，而我们第一行进行了缩放，所以第三行就刚好是 ，也是大于 的。所以，这样填的方法一定是合法的（毕竟我也 了啊）。
但是我们可以注意到一件事，由于 ，同时钦定第 个数为平均数，那么前两个数对平均数负方向的贡献全部由第 个数来承担了，那如果后面不只有一个数呢？也就是 大于 ，并且是偶数的情况。
下面考虑 的情况。
还是先看第一行，我们还是以中间点右边的的那个数作为平均数，即 中的 。那么前三个数对平均数负方向的贡献就是 ，要分给后面两个数承担。但是我们希望最后一个数（也就是最大的数）尽量小，这样才更不会超出 。那么就尽量 均摊。
接下来说明如何进行 均摊。
首先由于不能有相同的数，所以直接分成 是不行的，那么就还是要拆成一个序列。
还是举上面的例子，负方向的贡献分别是 ，但是正方向却只有两个数，那很明显，最好的方法就是将 加到最大的数上面去，变成 （如果加到 上面，就又变成 了）。
那么推广一下，正方向的贡献就应该是从 开始，后面有一段，每次 ，之后还有一个 的（因为把 加上去了）。比如当 ，负方向为 ，那么正方向就为 。
不过当 时是特殊的，只有最后一个数是正方向 。
现在算一下最大值会不会超过 。
奇数的情况前面已经算过了，现在只考虑偶数。那么最大的偶数便是 。第一行中选定的平均数为 ，那么最后一列第一个数就是 。那么最后一行最后一列的数就是 。
实现
首先特判掉奇数和 的情况，然后引入 差分数组，并进行一些微调，最后再根据发现的规律递推填充即可。
差分数组 的好处其实就是大部分相同，操作起来方便。比如当 时，那么 差分数组 就应该是 。只有两个位置是 ，其余都是 （当然要特判 ）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int mp[N][N];
int cha[N];
signed main() {
cin >> n;
if (n == 2) return puts("-1"), 0;
if (n & 1) {
int idx = 0;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ )
cout << ++ idx << ' ';
puts("");
}
return 0;
}
for (int i = 2; i <= n; i ++ ) cha[i] = 1;
if (n == 4) {
cha[n] = 3;
} else {
int mid = (n >> 1) + 2;
cha[mid] ++, cha[n] ++ ;
}
mp[1][1] = 1;
for (int i = 2; i <= n; i ++ ) mp[1][i] = mp[1][i - 1] + cha[i];
for (int i = 2; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
mp[i][j] = mp[i - 1][j] + cha[i] * mp[1][n];
}
}
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ )
cout << mp[i][j] << ' ';
puts("");
}
return 0;
}
|
