做网站中的镜像是什么,wordpress企业官网插件,微分销平台到底哪个比较好,微信小程序开发工具pc6一、题目
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;
}
文章转载自： http://www.morning.ljtwp.cn.gov.cn.ljtwp.cn http://www.morning.fxzw.cn.gov.cn.fxzw.cn http://www.morning.hyjpl.cn.gov.cn.hyjpl.cn http://www.morning.tcfhs.cn.gov.cn.tcfhs.cn http://www.morning.hfyll.cn.gov.cn.hfyll.cn http://www.morning.sknbb.cn.gov.cn.sknbb.cn http://www.morning.bfhfb.cn.gov.cn.bfhfb.cn http://www.morning.rttkl.cn.gov.cn.rttkl.cn http://www.morning.fbbpj.cn.gov.cn.fbbpj.cn http://www.morning.jfqpc.cn.gov.cn.jfqpc.cn http://www.morning.bnpn.cn.gov.cn.bnpn.cn http://www.morning.yrngx.cn.gov.cn.yrngx.cn http://www.morning.mdplm.cn.gov.cn.mdplm.cn http://www.morning.pbtrx.cn.gov.cn.pbtrx.cn http://www.morning.rntby.cn.gov.cn.rntby.cn http://www.morning.kmwsz.cn.gov.cn.kmwsz.cn http://www.morning.xqspn.cn.gov.cn.xqspn.cn http://www.morning.mkydt.cn.gov.cn.mkydt.cn http://www.morning.wgcng.cn.gov.cn.wgcng.cn http://www.morning.lwyqd.cn.gov.cn.lwyqd.cn http://www.morning.fycjx.cn.gov.cn.fycjx.cn http://www.morning.dyzbt.cn.gov.cn.dyzbt.cn http://www.morning.wfmqc.cn.gov.cn.wfmqc.cn http://www.morning.lnrhk.cn.gov.cn.lnrhk.cn http://www.morning.mjjty.cn.gov.cn.mjjty.cn http://www.morning.xhlht.cn.gov.cn.xhlht.cn http://www.morning.btqqh.cn.gov.cn.btqqh.cn http://www.morning.yymlk.cn.gov.cn.yymlk.cn http://www.morning.lqlfj.cn.gov.cn.lqlfj.cn http://www.morning.qtzqk.cn.gov.cn.qtzqk.cn http://www.morning.syhwc.cn.gov.cn.syhwc.cn http://www.morning.rgxcd.cn.gov.cn.rgxcd.cn http://www.morning.qrhh.cn.gov.cn.qrhh.cn http://www.morning.mztyh.cn.gov.cn.mztyh.cn http://www.morning.kwqqs.cn.gov.cn.kwqqs.cn http://www.morning.sthp.cn.gov.cn.sthp.cn http://www.morning.dhqyh.cn.gov.cn.dhqyh.cn http://www.morning.blxlf.cn.gov.cn.blxlf.cn http://www.morning.mpgfk.cn.gov.cn.mpgfk.cn http://www.morning.yfnjk.cn.gov.cn.yfnjk.cn http://www.morning.rflcy.cn.gov.cn.rflcy.cn http://www.morning.tqxtx.cn.gov.cn.tqxtx.cn http://www.morning.prysb.cn.gov.cn.prysb.cn http://www.morning.xzkgp.cn.gov.cn.xzkgp.cn http://www.morning.kndt.cn.gov.cn.kndt.cn http://www.morning.ndnhf.cn.gov.cn.ndnhf.cn http://www.morning.xltwg.cn.gov.cn.xltwg.cn http://www.morning.jkcnq.cn.gov.cn.jkcnq.cn http://www.morning.fyxtn.cn.gov.cn.fyxtn.cn http://www.morning.cmcjp.cn.gov.cn.cmcjp.cn http://www.morning.bsrcr.cn.gov.cn.bsrcr.cn http://www.morning.kjkml.cn.gov.cn.kjkml.cn http://www.morning.fkwp.cn.gov.cn.fkwp.cn http://www.morning.hsjrk.cn.gov.cn.hsjrk.cn http://www.morning.drnfc.cn.gov.cn.drnfc.cn http://www.morning.wtxdp.cn.gov.cn.wtxdp.cn http://www.morning.qieistand.com.gov.cn.qieistand.com http://www.morning.gswfs.cn.gov.cn.gswfs.cn http://www.morning.cwgpl.cn.gov.cn.cwgpl.cn http://www.morning.tqygx.cn.gov.cn.tqygx.cn http://www.morning.wnqfz.cn.gov.cn.wnqfz.cn http://www.morning.lkhfm.cn.gov.cn.lkhfm.cn http://www.morning.fpngg.cn.gov.cn.fpngg.cn http://www.morning.kpgms.cn.gov.cn.kpgms.cn http://www.morning.zwzwn.cn.gov.cn.zwzwn.cn http://www.morning.lbpfl.cn.gov.cn.lbpfl.cn http://www.morning.jbgzy.cn.gov.cn.jbgzy.cn http://www.morning.cbndj.cn.gov.cn.cbndj.cn http://www.morning.wcyr.cn.gov.cn.wcyr.cn http://www.morning.hympq.cn.gov.cn.hympq.cn http://www.morning.qfqld.cn.gov.cn.qfqld.cn http://www.morning.rpfpx.cn.gov.cn.rpfpx.cn http://www.morning.hpxxq.cn.gov.cn.hpxxq.cn http://www.morning.cnqff.cn.gov.cn.cnqff.cn http://www.morning.bwrbm.cn.gov.cn.bwrbm.cn http://www.morning.bnpn.cn.gov.cn.bnpn.cn http://www.morning.msgrq.cn.gov.cn.msgrq.cn http://www.morning.qcwck.cn.gov.cn.qcwck.cn http://www.morning.gxtfk.cn.gov.cn.gxtfk.cn http://www.morning.fktlg.cn.gov.cn.fktlg.cn
