做网站中的镜像是什么,免费推广的途径与原因,网站营销方法有哪些内容,品牌网站建设 2蝌蚪小一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
131F - Present to Mom 二、解题报告
1、思路分析
很经典的一种把列看作cell 来进行双指针/递推的题型
我们考虑#xff0c;可以预处理出原矩阵中的所有star
然后我们去枚举矩形的上下边界#xff0c;把…一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
131F - Present to Mom 二、解题报告
1、思路分析
很经典的一种把列看作cell 来进行双指针/递推的题型
我们考虑可以预处理出原矩阵中的所有star
然后我们去枚举矩形的上下边界把边界内的每列当成一个格子的话问题就变成了求和至少大于等于k的子数组的数目
这个经典问题我们双指针可以搞定
而快速计算列和可以预处理前缀和
2、复杂度 时间复杂度 O(n^2m)空间复杂度O(nm) 3、代码详解
#include bits/stdc.h
using i64 long long;
using i128 __int128;
using PII std::pairint, int;
const int inf 1e8 7, P 1e9 7;/*
预处理star枚举高 - 和 k 的子数组个数
two pointers
*/void solve() {int n, m, k;std::cin n m k;std::vectorstd::string g(n);for (int i 0; i n; i ) std::cin g[i];std::vectorstd::vectorint f(n, std::vectorint (m));std::arrayint, 5 dir { 1, 0, -1, 0, 1 };for (int i 1; i 1 n; i )for (int j 1; j 1 m; j ) {if (g[i][j] 1) {bool flag true;for (int k 0; k 4; k )if (g[i dir[k]][j dir[k 1]] 0)flag false;f[i][j] flag; }}std::vectorstd::vectorint pre(f);for (int i 1; i n; i )for (int j 0; j m; j )pre[i][j] pre[i - 1][j];i64 res 0;for (int lo 0; lo n; lo ) {for (int hi lo 2; hi n; hi ) {int l 1, r 1, cur 0;while (l 1 m) {while (r 1 m cur k)cur pre[hi - 1][r] - pre[lo][r], r;if (cur k) break;res (m - r);cur - pre[hi - 1][l] - pre[lo][l]; l;}}}std::cout res;
}int main(int argc, char** argv) {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int _ 1;// std::cin _;while (_ --)solve();return 0;
}
