前缀和+双指针,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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/727670.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

java读取wps嵌入式图片思路

这个只写了思路具体代码在文章最后&#xff0c;不想了解得直接去拿代码 了解Excel数据结构 Excel 文件格式后缀xls,xlsx 其实是一个压缩文件&#xff0c;是由多个文件夹以及xml 文件组合为一个文件&#xff0c;xml文件记录了Excel得内容以及样式等信息。加入在桌面新建一个xls…

MySQL之复制(七)

复制 定制的复制方案 分离功能 许多应用都混合了在线事务处理(OLTP)和在线数据分析(OLAP)的查询。OLTP查询比较短并且是事务型的。OLAP查询则通常很大&#xff0c;也很慢&#xff0c;并且不要求绝对最新的数据。这两种查询给服务器带来的负担完全不同&#xff0c;因此它们需…

一文教你在centos 7.9中安装mysql5.7(超级详细)

##red## &#x1f534; 大家好&#xff0c;我是雄雄&#xff0c;欢迎关注微信公众号&#xff0c;雄雄的小课堂。 一、前言 每当新来一个服务器之后&#xff0c;习惯性的都会安装一个宝塔面板&#xff0c;不为别的&#xff0c;就为了装环境方便点儿&#xff0c;比如常用的jdk,m…

python的赋值运算

# coding:utf-8 x20 #直接复制&#xff0c;直接将20赋值给x y10 xxy #将xy的和赋值给给x print(x) xy print(x)#40 x-y #相当于x-y print(x) #30x*y #xx*y x/y #xx/y print(x) x%2#xx%2 print(x)#0.0 隐式转换 z3 y//z #yy//z y**2#yy**2 #python支持链式赋值 abc100#相当于a10…

【ai】tx2-nx 查看 jetpack 版本信息及对应的tritonserver

3 jtop nvidia@tx2-nx:~$ jtop [WARN] Board missing UNKNOWN (press CTRL + Click) nvidia@tx2-nx:~$ 点击info 可以看到 jetpack是4.6opencv 是4.1.15.1.2 的不适合我 tritonserver2.35.0-jetpack5.1.2-update-2.tgz tritonserver2.19.0-jetpack4.6.1.tgz. 4.6.1<

【已解决】better-scroll在PC端如何开启鼠标滚动以及如何始终显示滚动条

总结 需要安装插件 mouse-wheel 和 scrollbar 在PC端如何开启鼠标滚动? 需要安装官方提供的滚动插件&#xff1a;mouse-wheel https://better-scroll.github.io/docs/zh-CN/plugins/mouse-wheel.html 为了开启鼠标滚动功能&#xff0c;你需要首先引入 mouseWheel 插件&…

华为设备SSH远程访问配置实验简述

一、实验需求: 1、AR1模拟电脑SSH 访问AR2路由器。 二、实验步骤&#xff1a; 1、AR1和AR2接口配置IP&#xff0c;实现链路通信。 2、AR2配置AAA模式 配置用户及密码 配置用户访问级别 配置用户SSH 访问服务 AR2配置远程服务数量 配置用户远程访问模式为AAA 配置允许登录接入用…

Mysql 8.3.0 安装

Mysql 8.3.0 安装地址&#xff1a;MySQL :: Download MySQL Community Server (Archived Versions) 下载链接&#xff1a;https://downloads.mysql.com/archives/get/p/23/file/mysql-8.3.0-linux-glibc2.28-x86_64.tar.xz 解压&#xff1a; tar -xvf mysql-8.3.0-linux-glib…

RS-232协议详解:深入理解与实际应用

RS-232协议详解 RS-232协议&#xff0c;也称为推荐标准232&#xff0c;是一种用于串行通信的标准协议。它在计算机和外围设备之间的通信中广泛应用。本文将详细介绍RS-232协议的各个方面&#xff0c;包括其历史、工作原理、信号类型、连接方式、应用场景等。希望通过这篇文章&a…

代码大模型揭秘:从下载到推理,全流程体验StarCoder

选择模型 模型榜单 大模型的发展日新月异&#xff0c;性能强劲的大模型不断涌现&#xff0c;可以实时关注开源大模型的榜单&#xff0c;选择合适自己的大模型 开源大模型榜单 开源代码大模型榜单 模型网站 目前主流的下载模型的网站就是 huggingface 全球社区&#xff0c;…

(四十三)Vue Router之嵌套路由

文章目录 什么是嵌套路由嵌套路由的使用demo 上一篇&#xff1a;&#xff08;四十二&#xff09;Vue之路由及其基本使用Vue Router 什么是嵌套路由 实际生活中的应用界面&#xff0c;有可能由多层嵌套的组件组合而成。同样地&#xff0c;URL 中各段动态路径也按某种结构对应嵌…

JEnv-for-Windows 详细使用

管理员执行jenv.bat文件 执行正常, 接下来就是按照官网的命令就行了 文件下载地址 https://download.csdn.net/download/qq_43071699/89462664 JEnv 是一个强大的Java版本管理工具&#xff0c;允许开发者在多个Java版本之间轻松切换。以下是一些常用的JEnv命令&#xff0c;这…

JVM常用概念之扁平化堆容器

扁平化堆容器是OpenJDK Valhalla 项目提出的&#xff0c;其主要目标为将值对象扁平化到其堆容器中&#xff0c;同时支持这些容器的所有指定行为&#xff0c;从而达到不影响原有功能的情况下&#xff0c;显著减少内存空间的占用&#xff08;理想条件下可以减少24倍&#xff09;。…

成为AIGC人才,是职场人当下的必修课?

随着科技的飞速进步&#xff0c;人工智能和机器学习技术正逐渐渗透到我们生活的每一个角落&#xff0c;其中&#xff0c;人工智能生成内容&#xff08;AIGC&#xff09;更是以其独特的魅力和广泛的应用前景&#xff0c;成为当下科技领域的热门话题。在这样的背景下&#xff0c;…

Kubernetes容器运行时:Containerd vs Docke

容器化技术笔记 Kubernetes容器运行时&#xff1a;Containerd vs Docke - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this arti…

Postman Postman接口测试工具使用简介

Postman这个接口测试工具的使用做个简单的介绍&#xff0c;仅供参考。 插件安装 1&#xff09;下载并安装chrome浏览器 2&#xff09;如下 软件使用说明

鸿蒙开发通信与连接:【@ohos.rpc (RPC通信)】

RPC通信 本模块提供进程间通信能力&#xff0c;包括设备内的进程间通信&#xff08;IPC&#xff09;和设备间的进程间通信&#xff08;RPC&#xff09;&#xff0c;前者基于Binder驱动&#xff0c;后者基于软总线驱动。 说明&#xff1a; 本模块首批接口从API version 7开始支…

lucene原理

一、正排索引 Lucene的基础层次结构由索引、段、文档、域、词五个部分组成。正向索引的生成即为基于Lucene的基础层次结构一级一级处理文档并分解域存储词的过程。 索引文件层级关系如图1所示&#xff1a; 索引&#xff1a;Lucene索引库包含了搜索文本的所有内容&#xff0…

C语言中字符串处理函数

目录 前言 1. strlen 测字符串长度函数 2.字符串拷贝函数 2.1strcpy 2.2 strncpy 3.strcat字符串追加函数 4. strcmp/strncmp 比较函数 5.字符查找函数 5.1 strchr 5.2 strrchr 6.atoi/atol/atof字符串转换数值 总结 前言 从0开始记录我的学习历程&#xff0c;我会尽…

ppt模版免费下载网站大全

PPT是我们传达信息、分享知识、展示项目和进行商务沟通的重要工具。一个设计精美、布局合理的PPT不仅能吸引观众的注意力&#xff0c;还能有效提升演讲者的专业形象。PPT模版可以帮助我们高效制作出精美的PPT&#xff0c;下面小编就来和大家分享一些免费无需注册登录就可以直接…