P1959 矩形个数 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2025年3月16日 00:01

矩形个数题解：前缀和加滑动窗口，O(r²c)的时间复杂度

P1959

回复 0 | 赞 5 | 浏览 151

#include <bits/stdc++.h> using namespace std; int main() { int r, c, n, k, x, y, sum = 0; cin >> r >> c >> n >> k; vector<vector<int>> a(r, vector<int>(c, 0)); vector<vector<int&g...

2024年9月18日 02:15

矩形个数题解：

P1959

回复 0 | 赞 19 | 浏览 875

二位前缀和重要代码二位前缀和基础知识部分可以参考：https://www.bilibili.com/video/BV1pi4y1j7si res=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]; sum[i][j]=g[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]; 暴力模拟每个可能的矩形，通过二位前缀和，大于等于k的就是合理的答案（这个思路说得比较简略，如果还是不太懂可以参考这个：https://www.acwing.com/solution/con...

题目矩形个数

题解数量2

发布题解在线答疑

热门题解

1 矩形个数题解：

2 矩形个数题解：前缀和加滑动窗口，O(r²c)的时间复杂度