前缀和+双指针，CF 131F - Present to Mom

一、题目

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::pair<int, 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::vector<std::string> g(n);for (int i = 0; i < n; i ++ ) std::cin >> g[i];std::vector<std::vector<int>> f(n, std::vector<int> (m));std::array<int, 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::vector<std::vector<int>> 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;
}