CF1195E OpenStreetMap 题解
很好的单调队列题。
题目传送门
题目意思:
给定一个 n × m n\times m n×m 的矩阵,求出所有大小为 a × b a\times b a×b 的子矩形中的最小值的和。
思路:
- 通过题目给的要求建立二维数组 h h h。
- 通过单调队列一行一行地扫,将扫出来地一个新的数组另存。
- 再通过单调队列一列一列扫,这一次一边扫一遍求出 a n s ans ans 的值。最后输出即可。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=9e6+10;
int n,m,a,b;
int x,y,z;
int g[N];
int h[3005][3005];
int hh[3005][3005];
int ans;
signed main()
{cin>>n>>m>>a>>b>>g[0]>>x>>y>>z;for(int i=1;i<=N;i++)g[i]=(g[i-1]*x+y)%z;for(int i=1;i<=n;i++)//建造高度数组for(int j=1;j<=m;j++)h[i][j]=g[(i-1)*m+j-1];for(int i=1;i<=n;i++)//扫行{deque<int>q;//双端队列for(int j=1;j<=m;j++){//如果超出窗口的范围了,就出队while(!q.empty()&&q.front()<=j-b)q.pop_front();//如果高度搞过枚举的高度,出队while(!q.empty()&&h[i][q.back()]>=h[i][j])q.pop_back();q.push_back(j);hh[i][j]=h[i][q.front()];//用新建的数组保存新的值}}for(int j=1;j<=m;j++)//扫列{deque<int>q;for(int i=1;i<=n;i++){//超出范围就出队while(!q.empty()&&q.front()<=i-a)q.pop_front();//不符合要求就出队while(!q.empty()&&hh[q.back()][j]>=hh[i][j])q.pop_back();q.push_back(i);if(i>=a&&j>=b)//保存答案ans+=hh[q.front()][j];}}cout<<ans;return 0;
}
完美撒花~
相关文章:
CF1195E OpenStreetMap 题解
很好的单调队列题。 题目传送门 题目意思: 给定一个 n m n\times m nm 的矩阵,求出所有大小为 a b a\times b ab 的子矩形中的最小值的和。 思路: 通过题目给的要求建立二维数组 h h h。通过单调队列一行一行地扫,将扫出来…...
微信营销系统如何使用效果会更好
微信作为中国最大的社交平台之一,已经成为企业私域营销的重要阵地。在这个庞大的社交网络中,如何使用微信营销系统,将直接影响到企业的营销效果。本文将深入探讨如何更好地利用微信营销系统,以实现更好的私域营销效果。 1. 确定营…...
Linux开机启动程序添加root权限
Linux添加开机启动程序 Debain、Ubuntu系列Linux开机之后会执行/etc/rc.local文件中的命令,所以,如果是想添加登陆用户所具有权限的操作,可以在文件中exit 0之前添加开机自动执行的脚本命令。或者将执行脚本的权限修改为当前登录用户具有执行…...

安卓13解决链接问题
作为Android用户,你可能已经注意到了一个问题——Android 13不再支持PPTP协议。但请别担心,作为一家专业的代理供应商,我们将与你分享解决方案,让你轻松解决L2TP问题,享受到高水平的连接体验。本文将为你提供实用的操作…...

《乡村振兴战略下传统村落文化旅游设计 》在2023年畅销榜排名465位
《乡村振兴战略下传统村落文化旅游设计 》在2023年畅销榜排名465位...

实现一个自动保存高CPU占用现场的简易工具
CPU 使用率在系统监控中是一个非常重要的指标。对于大多数 Web 应用来说,它们往往是 IO 密集型的,因此只会在某些时刻可能会出现 CPU 突然飙升的情况,随后很快就恢复正常。然而,当收到报警并想要排查问题时,CPU 飙升的…...

易服客工作室:如何在WordPress网站中举办虚拟活动
您是否正在寻找举办和管理虚拟活动的最佳方式? 也许您想在线举行下一次会议或举办有关您的产品和服务的网络研讨会。您可能担心它太贵,或者您没有技术知识来实现它。 在本文中,我们将列出您所需的在线服务的所有设备,并教您…...

Java IO流(一)IO基础
概述 IO流本质 I/O表示Input/Output,即数据传输过程中的输入/输出,并且输入和输出都是相对于内存来讲Java IO(输入/输出)流是Java用于处理数据读取和写入的关键组件常见的I|O介质包括 文件(输入|输出)网络(输入|输出)键盘(输出)显示器(输出)使用场景 文件拷贝(File&…...
区间覆盖 线段覆盖 二分
4195. 线段覆盖 - AcWing题库 P2082 区间覆盖(加强版) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 做法: void solve() {int n; cin>>n;vector<array<LL,2>> seg(n);for(auto &t: seg) cin>>t[0]>>…...
F#奇妙游(20):主动模式
F#中主动模式的三种形式 F#中有一种特殊的模式匹配,叫做主动模式(Active Pattern)。主动模式可以让我们自定义模式匹配的方式,这样可以让我们的代码更加简洁,更加清晰。主动模式有三种形式,分别是…...

OLED透明屏与传统显示屏的区别:探索未来视觉体验的新里程碑
OLED透明屏作为一种新兴的显示技术,与传统显示屏相比,具有许多独特的特点和优势。 那么,在这篇文章中,尼伽便通过比较OLED透明屏和传统显示屏的区别,包括透明性、对比度、色彩表现力、节能环保等方面,为读…...

打开软件提示mfc100u.dll缺失是什么意思?要怎么处理?
当你打开某个软件或者运行游戏,系统提示mfc100u.dll丢失,此时这个软件或者游戏根本无法运行。其实,mfc100u.dll是动态库文件,它是VS2010编译的软件所产生的,如果电脑运行程序时提示缺少mfc100u.dll文件,程序…...
Python 基础 -- Tutorial(二)
5、数据结构 本章更详细地描述了一些你已经学过的东西,并添加了一些新的东西。 5.1. 更多关于Lists 列表(list)数据类型有更多的方法。下面是列表对象的所有方法: list.append(x) 在列表末尾添加一项。相当于a[len(a):] [x]。 list.extend(iterable) 通过添加可…...
11 迭代器|生成器|协程
文章目录 迭代器可迭代对象可迭代对象的本质iter()函数与 next()函数迭代器 Iterator样例 for...in...循环的本质使用的场景--斐波那契数列list和tuple也可以接收可迭代对象 生成器简介创建生成器方法一方法二总结 使用 send 唤醒 协程协程和线程差异简单实现协程greenletgeven…...

“第三方支付”详解!
第三方支付是什么?第三方支付的解释 中央银行官方解释:是与产品所在国和主要外资银行签订合同、具有一定实力和信誉保障的第三方独立机构提供的交易支持平台。在通过第三方支付平台进行的交易中,买方购买货物后,买方使用第三方平台…...
Rust之泛型、trait与生命周期
泛型是具体类型或其他属性的抽象替代。在编写代码时,可以直接描述泛型的行为,或者它与其他泛型产生的联系,而无须知晓它在编译和运行代码时采用的具体类型。 1、泛型数据类型: 们可以在声明函数签名或结构体等元素时使用泛型&am…...

GPU Microarch 学习笔记 [1]
WARP GPU的线程从thread grid 到thread block,一个thread block在CUDA Core上执行时,会分成warp执行,warp的颗粒度是32个线程。比如一个thread block可能有1024个线程,分成32个warp执行。 上图的CTA(cooperative thre…...

Transformer(一)简述(注意力机制,NLP,CV通用模型)
目录 1.Encoder 1.1简单理解Attention 1.2.什么是self-attention 1.3.怎么计算self-attention 1.4.multi-headed(q,k,v不区分大小写) 1.5.位置信息表达 2.Decoder(待补充) 3.BERT 参考文献 1.Encode…...

回归预测 | MATLAB实现BiLSTM双向长短期记忆神经网络多输入多输出预测
回归预测 | MATLAB实现BiLSTM双向长短期记忆神经网络多输入多输出预测 目录 回归预测 | MATLAB实现BiLSTM双向长短期记忆神经网络多输入多输出预测预测效果基本介绍程序设计往期精彩参考资料 预测效果 基本介绍 MATLAB实现BiLSTM双向长短期记忆神经网络多输入多输出预测&#x…...

使用Dockker创建vwas容器时报错的解决方法
执行命令 docker run -it -d -p 13443:3443 --cap-add LINUX_IMMUTABLE secfa/docker-awvs没有详细看报错之前找了各种各样的解决办法,都无法解决。因此以后在看报错提示的时候耐心一点看关键词Error 后来才发现启动vwas时docker报了这个错: OSError: …...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...

无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...

搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...

Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...