题解：B4293 [蓝桥杯青少年组省赛 2022] 奖品

Dongze2010 · 2025-05-20 17:38:27 · 题解

B4293 奖品

题目大意

给你一个 n \times m 的二进制矩阵，找到一个最大的正方形，使得这个正方形对角线所对应的数都为 1。

题目分析

不用前缀和，直接查找的时间复杂度约为 O(N^5) 。

所以最好使用前缀和。我们可以通过前缀和或动态规划，将复杂度降至 O(N^3) 或更低。（其实标签里面就有前缀和。）

若有二维 a_{i,j} 数组。

二维前缀和计算。

cin >> a[i][j]; //输入
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
//计算二维前缀和

输入并计算前缀和。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 114;
int n,m,a[maxn][maxn],sum[maxn][maxn];
int main(){
    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            cin >> a[i][j];
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
        }
    }
    return 0;
}

接下来的判断怎么写呢？

我们可以从正方形的对角线入手。

因为一个点若在正方形的对角线上，它就既可以当做这个正方形的左上（下）点，或右上（下）点。这里为遍历方便，只考虑正方形的左上和右上点。

当 a_{i,j}=1 且为这个正方形的左上角时，设 x,y 是它的右下方、正方形对角线上的点。若 x,y 没越界且为 1 时，贪心一下，继续往下找。

while (x <= n and y <= m and a[x][y]
    and sum[x][y] - sum[i-1][y] - sum[x][j-1] + sum[i-1][j-1] == tot + 1){
    tot++; x++; y++; // && = and 个人习惯
}

当 a_{i,j}=1 且为这个正方形的右上角时，寻找左下方符合条件的点。

while (x <= n and y > 0 and a[x][y]
    and sum[x][j] - sum[i-1][j] - sum[x][y-1] + sum[i-1][y-1] == tot + 1){
    tot++; x++; y--;
}

最后记得保存最大奖品数量。

res = max(res,tot);

恭喜你，完成啦！

（记得 return 0; 哦）

AC Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 114;
int n,m,a[maxn][maxn],sum[maxn][maxn],res = -1,tot; // res 设为一个小于0的，方便后面max
int main(){
    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            cin >> a[i][j];
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
        }
    }
    //前缀和

    if (!sum[n][m])  {cout << 0 << endl; return 0;}  // 特判

    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            if (!a[i][j]) continue; //优化
            else {
                int x = i,y = j;
                while (x <= n and y <= m and a[x][y] and sum[x][y] - sum[i-1][y] - sum[x][j-1] + sum[i-1][j-1] == tot + 1){
                    tot++; x++; y++;
                }
                res = max(res,tot);
                tot = 0; x = i; y = j;
                while (x <= n and y > 0 and a[x][y] and sum[x][j] - sum[i-1][j] - sum[x][y-1] + sum[i-1][y-1] == tot + 1){
                    tot++; x++; y--;
                }
                res = max(res,tot);
                tot = 0;
            }
        }
    }
    cout << res << endl;
    return 0;
}

（管理员别卡555）。

第一次写题解，给个赞，谢谢了。