备战蓝桥杯【二维前缀和】
🌹作者:云小逸
📝个人主页:云小逸的主页
📝Github:云小逸的Github
🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前,其次就是现在!学会自己和解,与过去和解,努力爱自己。==希望春天来之前,我们一起面朝大海,春暖花开!==🤟
👏专栏:C++👏 👏专栏:Java语言👏
👏专栏:C语言初阶👏👏专栏:数据结构👏
文章目录
- 前言
-
- 二维前缀和:
- 算法介绍:
- 基本思想:
- 题目1:【子矩阵的和】
- 题目:
- 输入格式
- 输出格式
- 数据范围
- 输入样例:
- 输出样例:
- 做题思路:
- 代码:
- 题目2:K倍区间
- 题目:
- 输入格式
- 输出格式
- 数据范围
- 输入样例:
- 输出样例:
- 做题思路:
- 代码:
-
- 最后
-
-
前言
今天这篇文章接着上一篇【一维前缀和】继续写【二维前缀和】,如果有错误,请私信我,谢谢,望见谅。
——————————————————————————————
首先先写上几句话:献给坚持创作的我和点开这篇文章希望进步的你
1.当身边的一道道风景,变成了回忆 ,才忽然发现,风景依然在,人已是非少年,起初,我们揣着糊涂装明白,后来,我们揣着明白装糊涂。
2.人生百味,情最浓,人生繁华,淡最真,人生一路,一步有一步的风景,一程有一程的感悟,不论时光如何流转,有些东西不会改变,那就是对美好的追求,对真情的渴望,给他人一份善良,给自己一份淡然。
3.如果难过,就抬头望望天空吧,望着望着就忘了,它那么大,一定可以包容你的所有委屈。
4.人生几十年,酸甜苦辣咸,各种滋味都有,打开内心的窗,去呼吸一下外面的新鲜空气。别让自己活得太累。应当学着想开、看淡、学着不强求,学着深藏。适时放松自己,找寻宣泄,给疲倦的内心解解压。
5.关关难过关关过,夜夜难熬夜夜熬,悲喜自渡,他人难悟。悄悄崩溃,默默自愈。
二维前缀和:
算法介绍:
二维前缀和算法是一种用于计算矩阵中任意矩形区域和的算法。
基本思想:
先将矩阵中的每个元素都加上它左上角的元素,然后再将每个元素加上它上面的元素,最后得到一个新的矩阵,这个矩阵中的每个元素都是原矩阵中以它为右下角的矩形区域的和。这样,只要知道矩形区域的左上角和右下角的坐标,就可以很容易地求出矩形区域的和。
题目1:【子矩阵的和】
题目:
输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n,m,q。接下来 n 行,每行包含 m 个整数,表示整数矩阵。接下来 q
行,每行包含四个整数 x1,y1,x2,y2,表示一组询问。
输出格式
共 q 行,每行输出一个询问的结果。
数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例:
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例:
17
27
21
做题思路:
首先将矩阵中的每个元素都加上它左上角的元素,然后再将每个元素加上它上面的元素,最后得到一个新的矩阵,这个矩阵中的每个元素都是原矩阵中以它为右下角的矩形区域的和。然后,循环读取查询的矩形区域的左上角和右下角的坐标,并输出矩形区域的和。
代码:
#include<iostream>
using namespace std;const int N=1010;
int n,m,q;
int a[N][N],s[N][N];int main()
{scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];}}while(q--){int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);}return 0;
}
题目2:K倍区间
题目:
给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。你能求出数列中总共有多少个 K 倍区间吗?
输入格式
第一行包含两个整数 N 和 K。以下 N 行每行包含一个整数 Ai。
输出格式
输出一个整数,代表 K 倍区间的数目。
数据范围
1≤N,K≤100000,
1≤Ai≤100000
输入样例:
5 2
1
2
3
4
5
输出样例:
6
做题思路:
首先将数组中的每个元素都加上它前面的元素,得到一个新的数组,然后用一个数组cnt记录每个余数出现的次数,最后遍历数组,累加每个余数出现的次数,即可得到答案。
代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;const int N=100010;
int n,k;
long long s[N],cnt[N];int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&s[i]);s[i]+=s[i-1];}long long res=0;cnt[0]=1;for(int i=1;i<=n;i++){res+=cnt[s[i]%k];cnt[s[i]%k]++;}printf("%lld\n",res);return 0;
}
最后
十分感谢你可以耐着性子把它读完和我可以坚持写到这里,送几句话,对你,也对我:
1.太多的事,慢慢地就不能做了;太多的人,渐渐地就不见了。成长似乎是一个丢失的过程。青春,就是注定了要颠簸,要有眼泪和汗水,有委屈、不甘和失败。后来,慢慢知道一切该发生的就是会发生,一切会错过的就是会错过。
2.趁自己还不老,走自己想走的路。没有理由,不去闯!时间,抓起了就是黄金,虚度了就是流水;理想,努力了才叫理想,放弃了那只是妄想!努力,虽然不一定会获得,但不努力,就一定一无所获。
3.趁自己还不老,走自己想走的路。没有理由,不去闯!时间,抓起了就是黄金,虚度了就是流水;理想,努力了才叫理想,放弃了那只是妄想!努力,虽然不一定会获得,但不努力,就一定一无所获。
4.我一直以为人是慢慢变老的,其实不是,人是一瞬间变老的。
5.随着年龄的增长,我们愈加发现,或许我们并不是失去了一些人,而是更加懂得到底谁才是最重要的人。
最后如果觉得我写的还不错,请不要忘记点赞✌,收藏✌,加关注✌哦(。・ω・。)
愿我们一起加油,奔向更美好的未来,愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油,为自己点赞!
相关文章:
备战蓝桥杯【二维前缀和】
🌹作者:云小逸 📝个人主页:云小逸的主页 📝Github:云小逸的Github 🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前…...
阿里P6细谈Python简易接口自动化测试框架设计与实现,我直呼内行
1、开发环境 操作系统:Ubuntu18 开发工具:IDEAPyCharm插件 Python版本:3.6 2、用到的模块 requests:用于发送请求 xlrd:操作Excel,组织测试用例 smtplib,email:发送测试报告 l…...
数据库存储
RAID DSL : Domain Spesic Language 专用领域语言 单机存储 一切皆Key-Value 本地文件系统 一切皆文件 Ceph - 分布式存储 关系型数据库通用组件 Query Engine :解析query,生成查询计划Txn Manager :事务并发管理Lock Man…...
hive学习笔记
一、Hive基本概念1.1 hive是什么hive是基于hadoop的一个数仓分析工具,hive可以将hdfs上存储的结构化的数据,映射成一张表,然后让用户写HQL(类SQL)来分析数据tel up down 1383838438 1345 1567 138383…...
7大体系防作弊,牛客放大招了!严肃笔试客户端上线!
如果问起学生对在线笔试的印象,“不公平”和“不服气”占了半壁江山。学生认为很多企业的在线笔试系统并不完善。原因一,不能有效地规避部分学生的作弊行为;原因二,在线考试系统不稳定,bug频出,导致笔试发挥…...
R语言广义可加模型在空气环境污染方面的应用(1)
粉丝私信我希望复制一篇文章的图片,图片来源于文章:Wu C, Yan Y, Chen X, Gong J, Guo Y, Zhao Y, Yang N, Dai J, Zhang F, Xiang H. Short-term exposure to ambient air pollution and type 2 diabetes mortality: A population-based time series st…...
CSDN 编程竞赛二十九期题解
竞赛总览 CSDN 编程竞赛二十九期:比赛详情 (csdn.net) 竞赛题解 题目1、订班服 小A班级订班服了!可是小A是个小糊涂鬼,整错了好多人的衣服的大小。小A只能自己掏钱包来补钱了。小A想知道自己至少需要买多少件衣服。 #include <cstdio…...
基于STM32采用CS创世 SD NAND(贴片SD卡)完成FATFS文件系统移植与测试
一、前言 在STM32项目开发中,经常会用到存储芯片存储数据。 比如:关机时保存机器运行过程中的状态数据,上电再从存储芯片里读取数据恢复;在存储芯片里也会存放很多资源文件。比如,开机音乐,界面上的菜单图…...
K_A12_007 基于STM32等单片机驱动AS608光学指纹识别模块 OLED0.96显示
K_A12_007 基于STM32等单片机驱动AS608光学指纹识别模块 OLED0.96显示一、资源说明二、基本参数参数引脚说明三、驱动说明对应程序:四、部分代码说明1、接线引脚定义1.1、STC89C52RCAS608光学指纹模块1.2、STM32F103C8T6AS608光学指纹模块五、基础知识学习与相关资料下载六、视…...
map和set介绍及其底层模拟实现
致努力前行的人: 要努力,但不要着急,繁花锦簇,硕果累累都需要过程! 目录 1.关联式容器 2.键值对 3.树形结构的关联式容器 3.1set的介绍 3.2set的使用 3.3multiset的使用 3.4map的使用 3.5multimap的使用 4.常见的面试题…...
实现一个比ant功能更丰富的Modal组件
普通的modal组件如下: 我们写的modal额外支持,后面没有蒙版,并且Modal框能够拖拽 还支持渲染在文档流里,上面的都是fixed布局,我们这个正常渲染到文档下面: render部分 <RenderDialog{...restState}visi…...
2023美赛F题思路数据代码分享
文章目录赛题思路2023年美国大学生数学建模竞赛选题&论文一、关于选题二、关于论文格式三、关于论文提交四、论文提交流程注意不要手滑美赛F题思路数据代码【最新】赛题思路 (赛题出来以后第一时间在CSDN分享) 最新进度在文章最下方卡片,加入获取一手资源 202…...
Flutter如何与Native(Android)进行交互
前言 上一篇文章《Flutter混合开发:Android中如何启动Flutter》中我们介绍了如何在Native(Android项目)中启动Flutter,展示Flutter页面。但是在开发过程中,很多时候并不是简单的展示一个页面即可,还会涉及…...
数据库主从复制和读写分离
主从数据库和数据库集群的一些问题 数据库集群和主从数据库最本质的区别,其实也就是data-sharing和nothing-sharing的区别。集群是共享存储的。主从复制中没有任何共享。每台机器都是独立且完整的系统。 什么是主从复制? 主从复制,是用来建立一个和主数…...
Java并发编程面试题——线程安全(原子性、可见性、有序性)
文章目录一、原子性高频问题1.1 Java中如何实现线程安全?1.2 CAS底层实现1.3 CAS的常见问题1.4 四种引用类型 ThreadLocal的问题?二、可见性高频问题2.1 Java的内存模型2.2 保证可见性的方式2.3 volatile修饰引用数据类型2.4 有了MESI协议,为啥还有vol…...
DialogFragment内存泄露问题能不能一次性改好
孽缘 自DialogFragment在Android3.0之后作为一种特殊的Fragment引入,官方建议使用DialogFragment代替Dialog或者AllertDialog来实现弹框的功能,因为它可以更好的管理Dialog的生命周期以及可以更好复用。 然而建议虽好,实用须谨慎,…...
java学习--多线程
多线程 了解多线程 多线程是指从软件或者硬件上实现多个线程并发执行的技术。 具有多线程能力的计算机因有硬件支持而能够在同一时间执行多个线程,提升性能。 并发和并行 并行:在同一时刻,有多个指令在CPU上同时执行并发࿱…...
90后阿里P7技术专家晒出工资单:狠补了这个,真香...
最近一哥们跟我聊天装逼,说他最近从阿里跳槽了,我问他跳出来拿了多少?哥们表示很得意,说跳槽到新公司一个月后发了工资,月入5万多,表示很满足!这样的高薪资着实让人羡慕,我猜这是税后…...
2023美赛C题:Wordle筛选算法
Wordle 规则介绍 Wordle 每天会更新一个5个字母的单词,在6次尝试中猜出单词就算成功。每个猜测必须是一个有效的单词(不能是不能组成单词的字母排列)。 每次猜测后,字母块的颜色会改变,颜色含义如下: 程…...
SpringBoot 集成 Kafka
SpringBoot 集成 Kafka1 安装 Kafka2 创建 Topic3 Java 创建 Topic4 SpringBoot 项目4.1 pom.xml4.2 application.yml4.3 KafkaApplication.java4.4 CustomizePartitioner.java4.5 KafkaInitialConfig.java4.6 SendMessageController.java5 测试1 安装 Kafka Docker 安装 Kafk…...
OpenCV 图像金字塔算子
本文是OpenCV图像视觉入门之路的第14篇文章,本文详细的介绍了图像金字塔算子的各种操作,例如:高斯金字塔算子 、拉普拉斯金字塔算子等操作。 高斯金字塔中的较高级别(低分辨率)是通过先用高斯核对图像进行卷积再删除偶…...
【自学Linux】Linux一切皆文件
Linux一切皆文件 Linux一切皆文件教程 Linux 中所有内容都是以文件的形式保存和管理的,即一切皆文件,普通文件是文件,目录是文件,硬件设备(键盘、监视器、硬盘、打印机)是文件,就连套接字&…...
CUDA C++扩展的详细描述
CUDA C扩展的详细描述 文章目录CUDA C扩展的详细描述CUDA函数执行空间说明符B.1.1 \_\_global\_\_B.1.2 \_\_device\_\_B.1.3 \_\_host\_\_B.1.4 Undefined behaviorB.1.5 __noinline__ and __forceinline__B.2 Variable Memory Space SpecifiersB.2.1 \_\_device\_\_B.2.2. \_…...
为什么重写equals必须重写hashCode
关于这个问题,看了网上很多答案,感觉都参差不齐,没有答到要点,这次就记录一下! 首先我们为什么要重写equals?这个方法是用来干嘛的? public boolean equals (Object object&#x…...
< 每日小技巧:N个很棒的 Vue 开发技巧, 持续记录ing >
每日小技巧:6 个很棒的 Vue 开发技巧👉 ① Watch 妙用> watch的高级使用> 一个监听器触发多个方法> watch 监听多个变量👉 ② 自定义事件 $emit() 和 事件参数 $event👉 ③ 监听组件生命周期常规写法hook写法ὄ…...
数据结构与算法之二分查找分而治之思想
决定我们成为什么样人的,不是我们的能力,而是我们的选择。——《哈利波特与密室》二分查找是查找算法里面是很优秀的一个算法,特别是在有序的数组中,这种算法思想体现的淋漓尽致。一.题目描述及其要求请实现无重复数字的升序数组的…...
训练自己的中文word2vec(词向量)--skip-gram方法
训练自己的中文word2vec(词向量)–skip-gram方法 什么是词向量 将单词映射/嵌入(Embedding)到一个新的空间,形成词向量,以此来表示词的语义信息,在这个新的空间中,语义相同的单…...
ubuntu系统环境配置和常用软件安装
系统环境 修改文件夹名称为英文 参考链接 export LANGen_US xdg-user-dirs-gtk-update 常用软件安装 常用工具 ping 和ifconfig工具 sudo apt install -y net-tools inetutils-ping 截图软件 sudo apt install -y net-tools inetutils-ping flameshot 录屏 sudo apt-get i…...
【1139. 最大的以 1 为边界的正方形】
来源:力扣(LeetCode) 描述: 给你一个由若干 0 和 1 组成的二维网格 grid,请你找出边界全部由 1 组成的最大 正方形 子网格,并返回该子网格中的元素数量。如果不存在,则返回 0。 示例 1&#…...
windows11安装sqlserver2022报错
window11安装SQL Server 2022 报错 糟糕… 无法安装SQL Server (setup.exe)。此 SQL Server安装程序介质不支持此OS的语言,或没有SQL Server英语版本的安装文件。请使用匹配的特定语言SQL Server介质;或安装两个特定语言MUI,然后通过控制面板的区域设置…...
城乡建设学校官方网站/站外推广渠道
卓老师,我有一个信号与系统的问题想请教。按照时域采样定理,采样频率≥2倍的信号频率,才能得到信号全部信息。而以智能车中的编码器测速为例。我们知道测速周期在可接受范围内越小越利于控速,比如2ms。但2ms采样一次速度ÿ…...
wordpress菜单图标插件/百度今日数据统计
编者按:目前虚拟化技术已经突破虚拟内存和虚拟服务器两大空间,延伸到网络虚拟化、微处理器虚拟化、文件虚拟化和存储虚拟化等许多领域。越来越多的企业也已经在内部采用虚拟化技术,那么企业实现虚拟化环境都有哪些优势呢? 尽管现如…...
网页设计教程自学网/广州seo排名外包
外贸跨境电商平台是在国家政策支持下由政府与跨境企业或者进出口电商企业与企业之间进行的建设和运营,在跨境电商网站运营过程中,政府部门在海关、检验检疫、税务、外汇等方面对出口跨境电商平台实施监管政务的服务作用。跨境电商平台也由此区分为跨境电…...
网站前端做报名框/购买友情链接网站
问答题请完成下列Java程序:假设某家银行,它可接受顾客的汇款,每做一次汇款,便可计算出汇款的总额。现有两个顾客,每人都分3次,每次将50元钱汇入。编写一个程序,模拟实际作业。要求实现2个类&…...
室内设计怎么收费的/优化网站搜索排名
本文翻译自:Redirect parent window from an iframe actionWhat JavaScript do I need to use to redirect a parent window from an iframe? 我需要使用什么JavaScript从iframe重定向父窗口? I want them to click a hyperlink which, using JavaScri…...
wordpress 批量分类/百度大数据预测平台
PHP的字符串有三种定义方式:单引号 、双引号 、定界符1、单引号:指定一个简单字符串的最简单的方法是用单引号(字符 )括起来。 在被单引号括起来的字符串中,要再表示一个单引号,需要用反斜线(\)转义,和很多其它语言一样…...