题意简述 给定一个矩阵，求出和非负的最大子矩阵。 分析 据说本题正解为 O(n3log⁡n)O(n^3 \log n)O(n3logn) 的，二维前缀和+二分。 但是我太蒻了，怎么办呢？ 那么我们就打 O(n4)O(n^4)O(n4) 的暴力吧，看数据范围卡卡能A。 枚举时，我们要枚举左上角的坐标和右下角的坐标，显然时间复杂度已经来到了 O(n4)O(n^4)O(n4)。 那么，我们就要想一个 O(1)O(1)O(1) 的方法判断某个子矩阵是否非负。 那么，我们就可以使用二维前缀和了。其实就是一维前缀和的升级版，还是很好理解的。可以去看这篇百科：前缀和 & 差分 于是，我们飞快地打出了这份代码： 先别急，这玩意T了。那么，我们就开始愉快（误）地卡一下常吧~ 我们可以默认 (i,j)(i,j)(i,j) 在右下角，(k,l)(k,l)(k,l) 在左上角当然倒一倒也是可以的。无需判断 (i,j)(i,j)(i,j) 在右上角，(k,l)(k,l)(k,l) 在左下角之类的情况，这样每个矩形会且只会被判断一次。这样，我们大约卡了一个 14\frac{1}{4}41 的常数，速度瞬间飞起。 AC Code（1.50s,1.03MB）： vocal我刚才才发现一个厉害的事情，我这份代码在洛谷上的评测号是 R154314159，末6位是圆周率啊！！！我运气真好！！！