自动搬运

查看原文

来自洛谷，原作者为

	chenzefan 蒟蒻一枚||六年级||五级钩||GESP七级

搬运于2025-08-24 21:14:51，当前版本为作者最后更新于2025-06-06 17:12:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

前言

可以交题解耶！

思路

模拟题。

通过一个 bool 数组，来判断能否选择填矩形。

进行矩阵初始化，除了对角线上连续的 $k$ 个格子初始化为 1，其他都初始化为 0。

形象化的，就是这样：

• 若 $i=j$ 时，即对角线上。

  • 若 $i \le k$ 时，$vis_{i,j}=1$。
  • 若 $i > k$ 时，$vis_{i,j}=0$。

• 若 $i≠j$ 时，$vis_{i,j}=0$。

好了，初始化结束，开始模拟。

如果模拟到的点 $(i,j)$，满足 $vis_{i,j}=0$ ，则可以填，横向纵向分别进行判断，注意要更新 $vis_{i,j}$ 的值，防止重复计算。

模拟结束，输出。

如果 $(i,j)$ 点没有填矩形，输出 0。

否则，输出矩形编号 $id$。

本题有 Special Judge，不需要害怕样例不对，输出其中一种答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,ans[55][55];
bool vis[55][55];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)//初始化 
    	for(int j=1;j<=n;j++)
    		if(i==j&&i<=k) vis[i][j]=1;
    		else vis[i][j]=0;
    int id=1; //矩形的编号，逐步累积 
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=n;j++)
            if(!vis[i][j]){
            	//横向 
                if(j+1<=n&&!vis[i][j+1]) ans[i][j]=ans[i][j+1]=id++,vis[i][j]=vis[i][j+1]=1;//防止越界 
                //纵向 
                else if(i+1<=n&&!vis[i+1][j]) ans[i][j]=ans[i+1][j]=id++,vis[i][j]=vis[i+1][j]=1;//防止越界 
            }
    for(int i=1;i<=n;i++){//输出 
    	for(int j=1;j<=n;j++) printf("%d ",ans[i][j]);
    	printf("\n");
	}
    return 0;
}

撒花。