自动搬运

查看原文

来自洛谷，原作者为

	Dongze2010 这里只留下了二十二个字，记得看主页（标点符号不算）

搬运于2025-08-24 21:18:25，当前版本为作者最后更新于2025-05-20 17:38:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$B4293$ 奖品

题目大意

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

题目分析

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

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

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

其对应的 $sum_{i,j}$ 。 |6|7|10|14| |:-:|:-:|:-:|:-:| |8|13|21|28| |13|19|29|39|

二维前缀和计算。

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）。

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