洛谷 P1736 分析（别看）

科技起源的小号1

2026-10-02 19:57:23

发布于：天津

2阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

1.2 题目背景、允许、禁止与限制

背景：有一个 $n \times m$ 的 $0/1$ 矩阵，其中 $0$ 代表无鱼， $1$ 代表有鱼
允许：在一个正方形子矩阵的一端下口，将其对应对角线上的所有鱼吸进肚子，求最多能吸多少条鱼
限制：可以从某一角吸该正方形子矩阵当且仅当该对角线全部为鱼且其他地方全部不为鱼

1.3 题目数据范围与猜测

$nm \le 2500 \longrightarrow O(nm)$

1.4 一句话概括题意

有一个 $0/1$ 矩阵，找到其中的一个最长的对角线，使得该对角线对应的正方形子矩阵除此对角线外均为 $0$ 且该对角线上的数均为 $1$
求这个最长的长度

2 题目破题推导

2.1 第一步：分情况考虑

不难发现，吸的情况一共就四种：

从左上往右下吸
从右上往左下吸
从左下往右上吸
从右下往左上吸

而其中，这四种情况有些重复，去除重复就可以看成两种：

从左下往右上吸
从右下往左上吸

之所以这里选择从下到上是因为比较好处理一些

2.2 第二步：大拆小，小组大

一个合格的子矩阵需要具备的条件：

一条对角线上全部为 $1$
这个先不考虑，因为后面直接可以实现
其他地方全为 $0$
首先，在对角线合格的情况下，最大的子矩阵边长 $=$ 对角线长度
因此，一个 $0/1$ 的子矩阵求和之后减去其边长相当于排除对角线其他点的总和
如果这个总和仍然为 $0$ ，那这个子矩阵就是合格的

3 模型匹配

首先求最大子矩阵可以用dp实现--定义dpl代表从左上到右下来看，以 $(i,j)$ 为右下角的最长对角线长度；dpr代表从右上到左下来看，以 $(i,j)$ 为左下角时的最长对角线长度；那最终就是dpr中的最长长度与dpl中的最长长度取max；注意当 $a[i][j]=0$ 时没有符合条件的正方形子矩阵因此是 $0$
然后刚刚说的查询子矩阵的合格状态分两部分--前缀和得到整个子矩阵之和，也就是该子矩阵中的 $1$ 的个数；二分求得子矩阵最长边长（朴素暴力会TLE）

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 定义
int n, m;
const int N = 2555;
int a[N][N];
int dpl[N][N];
int dpr[N][N];
ll sum[N][N];
// 二维前缀和相关函数
void pre_sum(){
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
}
inline ll query(int xs, int ys, int xe, int ye){
    return sum[xe][ye] - sum[xs - 1][ye] - sum[xe][ys - 1] + sum[xs - 1][ys - 1];
}

int main(){

    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            cin >> a[i][j];
        }
    }
    pre_sum();
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            if (a[i][j] == 0){
                dpl[i][j] = 0;
                continue;
            }
            dpl[i][j] = dpl[i - 1][j - 1] + a[i][j];
        }
    }
    for (int i = 1;i <= n;i++){
        for (int j = m;j >= 1;j--){
            if (a[i][j] == 0){
                dpr[i][j] = 0;
                continue;
            }
            dpr[i][j] = dpr[i - 1][j + 1] + a[i][j];
        }
    }
    int left_mx = 0;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            int mx_len = dpl[i][j];
            int l = 1, r = mx_len;
            while(l <= r){
                int mid = (l + r) / 2;
                ll ps = query(i - mid + 1, j - mid + 1, i, j);
                if (ps == mid){
                    left_mx = max(left_mx, mid);
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
    }
    int right_mx = 0;
    for (int i = 1;i <= n;i++){
        for (int j = m;j >= 1;j--){
            int mx_len = dpr[i][j];
            int l = 1, r = mx_len;
            while(l <= r){
                int mid = (l + r) / 2;
                ll ps = query(i - mid + 1, j, i, j + mid - 1);
                if (ps == mid){
                    right_mx = max(right_mx, mid);
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
    }
    cout << max(left_mx, right_mx);
    
    return 0;
}