P3654 First Step (ファーストステップ)(贪心算法)

 

#include<bits/stdc++.h> 
using namespace std;int main() {int r,c,k;cin>>r>>c>>k;char a[105][105];int ans=0;for(int i=0;i<r;i++){for(int j=0;j<c;j++){cin>>a[i][j];}}for(int i=0;i<r;i++){int cnt=0; // 用来记录连续空地的数量for(int j=0;j<c;j++){if(a[i][j]=='.'){cnt++; // 如果是空地,连续空地计数增加} else{if(cnt>=k) ans+=cnt-k+1;// 连续空地数大于等于 K 时,可以放置队员cnt=0; // 重置连续空地计数}}if(cnt>=k){ // 行末还有连续空地的情况,需要处理ans+=cnt-k+1;}}for(int j=0;j<c;j++){int cnt=0;for(int i=0;i<r;i++){if(a[i][j]=='.'){cnt++;} else{if(cnt>=k) ans+=cnt-k+1;cnt=0;}}if(cnt>=k) ans+=cnt-k+1;}if(k==1) ans/=2;// 如果 K == 1,则需要除以 2,因为每个空地计算了两次cout<<ans;}

 水平扫描(按行)

  • 对每一行进行扫描,累积每段连续的空地数量。
  • 当遇到杂物(#)时,检查当前空地段的长度 cnt 是否大于等于 k,如果满足条件,则可以放置队员,且可以从中选 cnt - k + 1 个位置。
  • 对每行扫描完后,检查该行末尾是否存在连续的空地段(例如 ...),并更新答案。

垂直扫描(按列):

  • 对每一列进行类似的操作,累积连续空地并检查可行的站位方式。

注意:如果 k == 1,则每个空地点都会被统计两次。因此,最终答案需要除以 2。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java/Kotlin双语革命性ORM框架Jimmer(一)——介绍与简单使用

概览 Jimmer是一个Java/Kotlin双语框架 包含一个革命性的ORM 以此ORM为基础打造了一套综合性方案解决方案&#xff0c;包括 DTO语言 更全面更强大的缓存机制&#xff0c;以及高度自动化的缓存一致性 更强大客户端文档和代码生成能力&#xff0c;包括Jimmer独创的远程异常 …

ASP.NET Core中Filter与Middleware的区别

中间件是ASP.NET Core这个基础提供的功能&#xff0c;而Filter是ASP.NET Core MVC中提供的功能。ASP.NET Core MVC是由MVC中间件提供的框架&#xff0c;而Filter属于MVC中间件提供的功能。 区别 中间件可以处理所有的请求&#xff0c;而Filter只能处理对控制器的请求&#x…

ASP.NET Core对JWT的封装

目录 JWT封装 [Authorize]的注意事项 JWT封装 NuGet 库 |Microsoft.AspNetCore.Authentication.JwtBearer 9.0.1https://www.nuget.org/packages/Microsoft.AspNetCore.Authentication.JwtBearerhttps://www.nuget.org/packages/Microsoft.AspNetCore.Authentication.JwtBea…

【Uniapp-Vue3】从uniCloud中获取数据

需要先获取数据库对象&#xff1a; let db uniCloud.database(); 获取数据库中数据的方法&#xff1a; db.collection("数据表名称").get(); 所以就可以得到下面的这个模板&#xff1a; let 函数名 async () > { let res await db.collection("数据表名称…

腾讯云TI平台×DeepSeek:开启AI超强体验,解锁部署秘籍

引言 在人工智能飞速发展的今天&#xff0c;AI技术的应用场景已经渗透到我们生活的方方面面。从智能客服到自动驾驶&#xff0c;从精准医疗到金融科技&#xff0c;AI的应用正在不断推动各行业的变革与创新。作为AI领域的领军企业&#xff0c;腾讯云一直以来都在致力于为开发者…

利用 IMU 估计人体关节轴向和位置 —— 论文推导

Title: 利用 IMU 估计人体关节轴向和位置 —— “Joint axis and position estimation from inertial measurement data by exploiting kinematic constraints” —— 论文推导 文章目录 I. 论文回顾II. 铰接关节的约束1. 铰接关节约束的原理2. 铰接关节约束的梯度3. 铰接关节约…

pushgateway指标聚合问题

一 问题现象 一个job有多个实例推送指标&#xff0c;但是从pushgateway上看这个job的instance字段&#xff0c;只显示一个实例的ip&#xff0c;而不是多个实例。导致在grafana上无法正常根据ip查看监控。 应用的prometheus的配置 management:metrics:tags:application: ${spr…

无界构建微前端?NO!NO!NO!多系统融合思路!

文章目录 微前端理解1、微前端概念2、微前端特性3、微前端方案a、iframeb、qiankun --> 使用比较复杂 --> 自己写对vite的插件c、micro-app --> 京东开发 --> 对vite支持更拉跨d、EMP 方案--> 必须使用 webpack5 --> 很多人感觉不是微前端 --> 去中心化方…

Vim 多窗口编辑及文件对比

水平分割 :split 默认使用水平分割的方式。 :split :sp 垂直分割 :vsplit :vs 带文件的分割 :split 文件名 :sp 文件名 在光标所在的窗口&#xff0c;输入分割窗口命令就会对那个窗口进行分割。 切换窗口 Ctrlw 切换正在编辑的窗口 快速分割窗口 Ctrlwn 快速分割当前…

yolov11模型在Android设备上运行【踩坑记录】

0) 参考资料: https://github.com/Tencent/ncnn?tabreadme-ov-file https://github.com/pnnx/pnnx https://github.com/nihui/ncnn-android-yolov5 https://github.com/Tencent/ncnn?tabreadme-ov-file 1) &#xff1a;将xxx.pt模型转化成 xxx.onnx ONNX&#xff08;Ope…

电商平台的设计与实现(代码+数据库+LW)

摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统商品交易信息管理难度大&#xff0c;容错率低&#xff0…

学习笔记:机器学习中的数学原理(一)

1. 集合 集合分为有限集和无限集&#xff1b; 对于有限集&#xff0c;两集合元素数相等即为等势&#xff1b; 对于无限集&#xff0c;两集合元素存在一一映射关系即为等势&#xff1b; 无限集根据是否与正整数集等势分为可数集和不可数集。 2. sigmoid函数&#xff08;也叫…

【翻译+论文阅读】DeepSeek-R1评测:粉碎GPT-4和Claude 3.5的开源AI革命

目录 一、DeepSeek-R1 势不可挡二、DeepSeek-R1 卓越之处三、DeepSeek-R1 创新设计四、DeepSeek-R1 进化之路1. 强化学习RL代替监督微调学习SFL2. Aha Moment “啊哈”时刻3. 蒸馏版本仅采用SFT4. 未来研究计划 部分内容有拓展&#xff0c;部分内容有删除&#xff0c;与原文会有…

互联网分布式ID解决方案

业界实现方案 1. 基于UUID 2. 基于DB数据库多种模式(自增主键、segment) 3. 基于Redis 4. 基于ZK、ETCD 5. 基于SnowFlake 6. 美团Leaf(DB-Segment、zkSnowFlake) 7. 百度uid-generator() 基于UUID生成唯一ID UUID生成策略 推荐阅读 DDD领域驱动与微服务架构设计设计模…

使用Python实现PDF与SVG相互转换

目录 使用工具 使用Python将SVG转换为PDF 使用Python将SVG添加到现有PDF中 使用Python将PDF转换为SVG 使用Python将PDF的特定页面转换为SVG SVG&#xff08;可缩放矢量图形&#xff09;和PDF&#xff08;便携式文档格式&#xff09;是两种常见且广泛使用的文件格式。SVG是…

CV(11)-图像分割

前言 仅记录学习过程&#xff0c;有问题欢迎讨论 图像分割 语义分割不需要区分具体的个体&#xff0c;实例分割需要 反卷积/转置卷积&#xff1a; 它并不是正向卷积的完全逆过程。反卷积是一种特殊的正向卷积&#xff0c;先按照一定的比例通过补0 来扩大输入图像的尺寸&…

封装descriptions组件,描述,灵活

效果 1、组件1&#xff0c;dade-descriptions.vue <template><table><tbody><slot></slot></tbody> </table> </template><script> </script><style scoped>table {width: 100%;border-collapse: coll…

【Elasticsearch】terms聚合误差问题

Elasticsearch中的聚合查询在某些情况下确实可能存在误差&#xff0c;尤其是在处理分布式数据和大量唯一值时。这种误差主要来源于以下几个方面&#xff1a; 1.分片数据的局部性 Elasticsearch的索引通常被分成多个分片&#xff0c;每个分片独立地计算聚合结果。由于数据在分…

Android修行手册-五种比较图片相似或相同

Unity3D特效百例案例项目实战源码Android-Unity实战问题汇总游戏脚本-辅助自动化Android控件全解手册再战Android系列Scratch编程案例软考全系列Unity3D学习专栏蓝桥系列ChatGPT和AIGC👉关于作者 专注于Android/Unity和各种游戏开发技巧,以及各种资源分享(网站、工具、素材…

2、k8s的cni网络插件和基本操作命令

kube-prxoy属于节点组件&#xff0c;网络代理&#xff0c;实现服务的自动发现和负载均衡。 k8s的内部网络模式 1、pod内的容器于容器之间的通信。 2、一个节点上的pod之间的通信&#xff0c;docker0网桥直接通信。 3、不同节点上的pod之间的通信&#xff1a; 通过物理网卡的…