题解：P14247 [CCPC 2024 Shandong I] 矩阵

· · 题解

思路

我们发现，这题限制较为严格的就是四元组这一块，这个限制简单解释一下就是在你构造的矩阵中，恰有一个子矩阵满足四个角不相同。那既然这个限制比较严格，我们就先考虑这个限制，一种比较简单的处理方法就是让你构造的大矩阵的四个角满足这个限制，四个角从左到右，从上到下分别填 1,2,3,4，接下来我们再去考虑其他限制。

题目要求我们的矩阵元素要包括所有 2n 个数，而我们的矩阵大小是 n \times n，题目又保证 n 最小为 2，说明保证了我们一定有给这 2n 个数全部填上的空间。注意，我这里说有给它们全部填上的空间，为啥这么说，虽然你理论上一定够位置填上这全部 2n 个数，那万一你不满足其他限制呢？所以，做题时，请你也自己注意一下这个问题。不过对于这题而言，我们一定可以找出一种构造方式，至少我想到的一种。

我们确定好四个角后，先不管第一行和最后一行，先考虑第 2 到 n-1 行，这里我的方法是从 5 开始，每行填相同数字，每往下一行填的数字比上一行大 1，但始终保持同一行数字相同。这样就保证四元组限制不会在其他行出现了，以为始终可以保证子矩阵的四个角有重复数字。

最后考虑第一行和最后一行剩下的格子。这里就没啥太大限制了，如果 2n 个数还没填完，就把剩下的数填上去，但始终保持同一列上第一行和最后一行的数相同，如果 2n 个数填完了但格子还没满，那就直接填 2n 就好了，但还是要满足第一行和最后一行的数相同。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=55;
int n,a[N][N];
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n,a[1][1]=1,a[1][n]=2,a[n][1]=3,a[n][n]=4;
    for(int i=2,l=5;i<n;i++,l++)for(int j=1;j<=n;j++)a[i][j]=l;
    for(int i=2,l=3+n;i<n;i++)a[1][i]=a[n][i]=(l<n*2?l++:l);
    cout<<"Yes\n";
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cout<<a[i][j]<<(j==n?"\n":" ");
    return 0;
}