题解：B3755 [信息与未来 2019] 方格覆盖

chenzefan · 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;
}

撒花。