题解：P14133 【MX-X22-T4】「TPOI-4D」Another Matrix Problem

wala5456 · 2025-10-03 20:25:05 · 题解

通过构造，无需任何算法就能解决这道题

本题解给出了较为严谨的证明

通过题目，我们可以得知要把 1~n^2 的所有数分成黑白两个部分，两个部分的差最小。我们分 n 为奇数和偶数来考虑。

n为偶数时，显而易见，两个偶数相乘一定是4的倍数，所以数字数量就是 4 的倍数。那就把 1~n^2 每4个分为一组，这里就用 a，a+1，a+2，a+3 来表示吧。把 a+1 和 a+2 放在一个部分，a 和 a+3 放在一个部分，这样就能保证两部分的和永远相同，差直接输出0就行了。

至于 n 为奇数时，把 1 去掉，只看 2~n，数字的数量就变成 n^2-1，拆成 (n+1)\times(n-1)，这样就是两个偶数相乘，依然是4的倍数，就可以用上述偶数的构造法，最后随便找一组加上1就行了，差值最小为 1。

然后就到了构造矩阵的这一步。双层 for 循环，判断行数加列数为奇偶即可。但这样还有一个问题，题目要求的是每行递增输出。解决方法很简单，一列一列的去构造，后一列的永远比前一列大，这样就完美解决了！

AC code

#include <bits/stdc++.h>
using namespace std;
int n;
int a[2005][2005],h[4000005],b[4000005];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    n*= n;
    if(n % 2 == 0){
        for(int i = 1;i <= n/4;i++){
            h[i*2-1] = i*4-3;
            b[i*2-1] = i*4-2;
            b[i*2] = i*4-1;
            h[i*2] = i*4;
        }
        cout << 0 << endl;
    }
    else{
        h[1] = 1;
        for(int i = 1;i <= n/4;i++){
            h[i*2] = i*4-2;
            b[i*2-1] = i*4-1;
            b[i*2] = i*4;
            h[i*2+1] = i*4+1;
        }
        cout << 1 << endl;
    }
    int hi = 0,bi = 0;
    n = sqrt(n);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if((i+j) %2 == 0){
                hi++;
                a[j][i] = h[hi];
            }
            else{
                bi++;
                a[j][i] = b[bi];
            }
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++) cout << a[i][j] << " ";
        cout << endl;
    }
    return 0;
}