P8783 [蓝桥杯 2022 省 B] 统计子矩阵题解
keep_eating
·
·
题解
P8783 [蓝桥杯 2022 省 B] 统计子矩阵题解
题目样例太水，纯暴力都能得80分
咳咳，题目难度中规中矩，算是一道水题，不过做对还是有一定难度的。
OK，废话不多说，看题
[doge]
最终代码
题目概述
对于 n \times m 的矩阵 a，求有多少个子矩阵满足此子矩阵中所有数之和不大于 k。
但是，我们来看看约定
1<N,M<500
0<a_ij<1000
**OK呀，题目大致就是这个意思，下面来看思路**
## 思路讲解
### 首先，来讲一讲80分的代码
**可以很容易的想到：使用二维前缀和，在初始化矩阵数组做前缀和的预处理。**
**然后再去判断子矩阵与 $k$ 的关系，统计答案输出即可。**
**时间复杂度:$O(n^4)$**
**OK，代码如下**
[真·代码](http://www.luogu.org/)
[空](https://www.luogu.com.cn/paste/bo4juutk)
### 100分做法
**我相信你们已经得了80分了，接下来，我来讲一讲100分做法**
**很显然，只用二维前缀和是AC不了的，所以，我们可以使用双指针$two-pointer$。**
[不会双指针点这里](https://oi.wiki/misc/two-pointer/)
**我们可以用矩阵中遍历的所谓左上角的点行和列都小于右下角的点，在不满足条件的同时做遍历。**
**我们可以定义4个指针，分别代表左上角和右下角，使它满足 $i <j 且 l<r$，遍历所有的情况，用$ans$计入个数**
**好了，代码如[下](https://www.luogu.com.cn/paste/lvmtyh9e)。**
[代码](https://www.bilibili.com/video/BV1uT4y1P7CX/?spm_id_from=autoNext&vd_source=b211052b1a22c3c38da2b7c470765c4d)
