题解 | #数字方阵#

来写一篇随机化做法的题解。

尝试只用一次 std::random_shuffle 草过去，发现在一些小数据上确实挺容易爆炸。

那么考虑这么个事情：当 $nn$ 很大的时候，在整个方阵中重复次数一定不会很多，而想让重复次数很多，就必须让 $nn$ 变小（这样碰撞概率才会大）。

所以我们就得到了如下代码：（注：std::random_shuffle 函数用于打乱一个数组的排列）

#include<map>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e3 + 5;
int n, p[N * N];
bool check(){
    std::map<int, int>map;
    map.clear();
    for (int i = 1; i <= n; ++i) {
        int s = 0;
        for (int j = 1; j <= n; ++j)
            s += p[(i - 1) * n + j];
        if (map.count(s)) return 0;
        map[s] = 1;
    }
    for (int j = 1; j <= n; ++j) {
        int s = 0;
        for (int i = 1; i <= n; ++i)
            s += p[(i - 1) * n + j];
        if (map.count(s)) return 0;
        map[s] = 1;
    }
    int s = 0;
    for (int i = 1; i <= n; ++i)
        s += p[(i - 1) * n + i];
    if (map.count(s)) return 0;
    map[s] = 1;
    s = 0;
    for (int i = 1; i <= n; ++i)
        s += p[(i - 1) * n + n - i + 1];
    return !map.count(s); // 按照题意检验和
}
int main(){
    srand(time(NULL));
    n = init();
    for (int i = 1; i <= n * n; ++i)
        p[i] = i;
    do{
        std::random_shuffle(p + 1, p + 1 + n * n);
    }while(!check()); // 每做一遍 random_shuffle 就 check 一次，保证输出结果的正确性
    for (int i = 1; i <= n; ++i, putchar('\n'))
        for (int j = 1; j <= n; ++j, putchar(' '))
            print(p[(i - 1) * n + j]);
}