备战蓝桥杯【一维前缀和】
🌹作者:云小逸
📝个人主页:云小逸的主页
📝Github:云小逸的Github
🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前,其次就是现在!学会自己和解,与过去和解,努力爱自己。==希望春天来之前,我们一起面朝大海,春暖花开!==🤟
👏专栏:C++👏 👏专栏:Java语言👏
👏专栏:C语言初阶👏👏专栏:数据结构👏
文章目录
- 前言
-
- 前缀和:
- 什么是前缀和
- 题目:
- 输入格式
- 输出格式
- 数据范围
- 输入样例:
- 输出样例:
- 做题思路:
- 代码:
- 截断数组
- 题目:
- 输入格式
- 输出格式
- 数据范围
- 输入样例1:
- 输出样例1:
- 输入样例2:
- 输出样例2:
- 输入样例3:
- 输出样例3:
- 解题思路:
- 代码:
- 最后
-
-
前言
今天这篇文章是备战蓝桥杯的第五篇文章,这一篇文章是写的是一维前缀和和二维前缀和的相关算法问题,如有错误,请私信并告知,十分感谢!!!
———————————————————————————————————————————
首先先写上几句话:献给坚持创作的我和点开这篇文章希望进步的你
1.所谓现实就是,人没有钱就不如鬼,汤没有盐就不如水,慢慢地你就会发现,一颗好的心,比不上一张好的嘴。
2.不要总怪别人对你以貌取人,毕竟别人的心太远,打脸就在眼前。
3.假如你现在不满意你所做的工作,要么请你辞职,要么请你闭嘴。
4.俗话说,热水不能包治百病,情话不能陪你过一生,人民币都有造假,请远离那些对你忽冷忽热的人。
5.你总以为你放不下的人同样会放不下你,其实不是,鱼没有了水会死,水没有了鱼会变得更清澈。
前缀和:
什么是前缀和
前缀和指一个数组的某下标之前的所有数组元素的和(包含其自身)。前缀和分为一维前缀和,以及二维前缀和。前缀和是一种重要的预处理,能够降低算法的时间复杂度。
例如:
数组: a[1], a[2], a[3], a[4], a[5], …, a[n] 下标从1开始
前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i]包含其自身
这里的下标从1开始,这样便于理解,不用进行下标的转换,省着在做题的时候,容易把自己绕糊涂。
s[0] = 0
s[1] = a[1]
s[2] = a[1] + a[2]
题目:
输入一个长度为 n 的整数序列。接下来再输入 m 个询问,每个询问输入一对 l,r。
对于每个询问,输出原序列中从第 l 个数到第 r 个数的和。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数,表示整数数列。
接下来 m 行,每行包含两个整数 l 和 r,表示一个询问的区间范围。
输出格式
共 m 行,每行输出一个询问的结果。
数据范围
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000
输入样例:
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例:
3
6
10
做题思路:
使用一个预处理数组s来存储从a[1]到a[i]的和,然后使用s[r]-s[l-1]来计算从a[l]到a[r]的和。
代码:
#include<iostream>
using namespace std;const int N=100010;
int n,m;
int a[N],s[N];int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];//数组下标从零开始while(m--){int l=0,r=0;scanf("%d%d",&l,&r);printf("%d\n",s[r]-s[l-1]);//这里要注意区间间的运算}return 0;
}
截断数组
题目:
给定一个长度为 n 的数组 a1,a2,…,an。
现在,要将该数组从中间截断,得到三个非空子数组。
要求,三个子数组内各元素之和都相等。
请问,共有多少种不同的截断方法?
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
输出一个整数,表示截断方法数量。
数据范围
前六个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤105,−10000≤ai≤10000。
输入样例1:
4
1 2 3 3
输出样例1:
1
输入样例2:
5
1 2 3 4 5
输出样例2:
0
输入样例3:
2
0 0
输出样例3:
0
解题思路:
解题思路是使用前缀和来求解。首先,通过输入n个数,构建一个前缀和数组s,其中s[i]表示前i个数的和。然后,判断s[n]是否能被3整除,如果不能,则输出0,表示无解。如果能,则遍历s数组,计算s[i-2]和s[n]-s[i-1]是否等于s[n]/3,如果相等,则表示存在一个子数组,其和为s[n]/3,最后输出符合条件的子数组的个数。
代码:
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N=100010;
int n=0;
int s[N];int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&s[i]);s[i]+=s[i-1];}if(s[n]%3){puts("0");return 0;}long long res=0;for(int i=3,cnt=0;i<=n;i++){if(s[i-2]==s[n]/3) cnt++;if(s[n]-s[i-1]==s[n]/3) res+=cnt;}printf("%lld",res);return 0;
}
最后
十分感谢你可以耐着性子把它读完和我可以坚持写到这里,送几句话,对你,也对我:
1.当你的能力不能取代的时候,你自身的弱点才有可能被人忽视。
2.请你擦亮自己的眼睛,看清楚这个现实的社会,有用的时候,你在别人的手中就是一块宝,没有用的时候,你在别人的手中就是垃圾,随处可扔。
3你身边一定有不少这样的人,平时看起来人畜无害,遇到事的时候,就先给你捅刀子。
4.这人一走,茶也跟着凉,这是自然规律,这人还没走,茶还跟着凉,这是世态炎凉。
5.不要以为别人事事都拿你当回事,其实,你在他们眼里,你只配给他们舔鞋。
最后如果觉得我写的还不错,请不要忘记点赞✌,收藏✌,加关注✌哦(。・ω・。)
愿我们一起加油,奔向更美好的未来,愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油,为自己点赞!
相关文章:
![](https://img-blog.csdnimg.cn/f3381d255f194ddbabed51eb9e34642e.png#pic_center)
备战蓝桥杯【一维前缀和】
🌹作者:云小逸 📝个人主页:云小逸的主页 📝Github:云小逸的Github 🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前…...
![](https://img-blog.csdnimg.cn/img_convert/76dbb0fd2b8c3488d8b0499251bca483.png)
研报精选230214
目录 【行业230214艾瑞股份】中国增强现实(AR)行业研究报告【行业230214国信证券】信息安全深度剖析5:密评和信创双催化,密码产业开启从1到N【行业230214民生证券】磁性元器件深度报告:乘新能源之风,磁性元…...
![](https://img-blog.csdnimg.cn/50b8a6d9cd73410c8cf7a58ec07b4964.png)
【SSL/TLS】准备工作:证书格式
证书格式1. 格式说明1.1 文件编码格式1.2 文件后缀格式2. xca导出格式1. 格式说明 1.1 文件编码格式 1. PEM格式: 使用Base 64 ASCII进行编码的纯文本格式。后缀为“.pem”, ".cer", ".crt", ".key" 2. DER格式 二进制编码格式,文件…...
![](https://img-blog.csdnimg.cn/370ebc538e874e669ba0b2d8c724222c.png)
Linux常用命令---系统常用命令
Linux系统常用命令场景一: 查看当前系统内核版本相关信息场景二: sosreport 命令场景三: 如何定位并确定命令?场景四:查看当前系统运行负载怎场景五: 查看当前系统的内存可用情况场景六:查看网卡…...
![](https://www.ngui.cc/images/no-images.jpg)
C 结构体
C 数组允许定义可存储相同类型数据项的变量,结构是 C 编程中另一种用户自定义的可用的数据类型,它允许您存储不同类型的数据项。结构用于表示一条记录,假设您想要跟踪图书馆中书本的动态,您可能需要跟踪每本书的下列属性ÿ…...
![](https://img-blog.csdnimg.cn/4335d809b6d64b0a88a9f967e947b09d.png)
手语检测识别
论文:Real-Time Sign Language Detection using Human Pose Estimation Github:https://github.com/google-research/google-research/tree/master/sign_language_detection SLRTP 2020 手语识别任务包括手语检测(Sign language detection&a…...
![](https://img-blog.csdnimg.cn/a1d4b71862664df2ac4aed5308b6b3a4.png)
android fwk模块之Sensor架构
本文基于Android 12源码整理,包含如下内容: 通信架构应用层实现使用方式SensorManager抽象接口具体实现fwk层的实现native中的SensorManager的初始化流程native中的消息队列初始化与数据读取sensorservice实现HAL层的实现通信架构 应用层实现 涉及代码&…...
![](https://img-blog.csdnimg.cn/aa61578497414de2a438c851f63f2501.png)
安装less-loader5出现webpack版本不兼容
今天遇到一个问题: 安装less-loader5之后其它包提示peerDependencies WARNING,意思是包版本不兼容。 【难题】 虽然NPM已经很自动化了,但依赖问题真的是一个难题,无法自动解决,需要人工干预调整。 【解决办法】 去查…...
![](https://www.ngui.cc/images/no-images.jpg)
Java 网络编程
1.UDP和TCPUDP和TCP是传输层协议中最核心的两种协议他们的特点分别是UDP: 无连接,不可靠传输,面向数据报,全双工TCP: 有连接,是可靠传输,面向字节流,全双工有无连接有连接:就好比两个人打电话,打电话的一方发出连接请求,被打电话的一方选择确认连接,此时双方才能进行通话无连接…...
![](https://www.ngui.cc/images/no-images.jpg)
BEV学习记录
近期可能要经常性的开展BEV工作,打算把自己觉着不错的网站拿出来记录一下。 首先贴上来我还没有细读的一篇觉着不错的文章。 自动驾驶感知新范式——BEV感知经典论文总结和对比(上)_苹果姐的博客-CSDN博客_bev视角 开山之作--LSS ECCV 202…...
![](https://www.ngui.cc/images/no-images.jpg)
Webrtc Native C++切换音频输入源
modules/audio_device/audio_device_impl.cc #include “api/audio_options.h” #include “modules/audio_device/include/factory.h” // 创建一个 AudioDeviceModule 对象 auto audio_device_module = webrtc::AudioDeviceModule::Create( webrtc::AudioDeviceModule::kPl…...
![](https://img-blog.csdnimg.cn/ea48c1dc15804d2a965dcd5c0b0969c2.png)
裸辞5个月,面试了37家公司,终于找到理想工作了
上半年裁员,下半年裸辞,有不少人高呼裸辞后躺平真的好快乐!但也有很多人,裸辞后的生活五味杂陈。 面试37次终于找到心仪工作 因为工作压力大、领导PUA等各种原因,今年2月下旬我从一家互联网小厂裸辞,没想…...
![](https://www.ngui.cc/images/no-images.jpg)
Mybatis-plus@DS实现动态切换数据源应用
目录1 DS实现动态切换数据源原理2 不可在事务中切换数据库分析解决3 原因解析1 DS实现动态切换数据源原理 首先mybatis-plus使用com.baomidou.dynamic.datasource.AbstractRoutingDataSource继承 AbstractDataSource接管数据源;具体实现类为com.baomidou.dynamic.d…...
![](https://img-blog.csdnimg.cn/img_convert/761e86e81055470f8b1cdedeafd50bb6.png)
SpringBoot的创建和使用
SpringBoot是什么?SpringBoot诞生的目的就是为了简化Spring开发,而相对于Spring,SpringBoot算是一个很大的升级,就如同汽车手动挡变成了自动挡。Spring:SpringBoot:SpringBoot的优点SpringBoot让Spring开发…...
![](https://www.ngui.cc/images/no-images.jpg)
居家电话客服宝典
客服分类从销售的流程来分,客服分为售前和售后。售前一般都带有销售性质,工资主要靠提成,售后一般是解答问题,工资主要看服务质量和差评量。从工作模式来分,客服分为在线客服和热线客服。在线客服以打字聊天为主&#…...
![](https://www.ngui.cc/images/no-images.jpg)
开发方案设计
1、开发流程产品需求设计-->需求粗评-->做设计方案-->粗估时-->需求细评-->排期-->开发-->提测、修bug-->code review-->上线设计方案主要是写实现思路、模块划分code review:完善代码,发现未考虑到的边界问题2、具体实现方案…...
![](https://www.ngui.cc/images/no-images.jpg)
文件路径模块pathlib
文件路径模块pathlib 文章目录文件路径模块pathlib1.概述2.创建路径2.1.创建非windos平台路径2.2.动态拼接路径joinpath2.3.替换文件名称 with_name2.4.创建固定目录2.5.创建文件夹和文件1.创建多级目录mkdir2.创建空文件3.路径解析3.1.根据路径分隔符解析路径parts3.2.获取父级…...
![](https://img-blog.csdnimg.cn/00f49e81117040918d74664fe046f2cf.png)
spring cloud篇——什么是服务熔断?服务降级?服务限流?spring cloud有什么优势?
文章目录一、spring cloud 有什么优势二、服务熔断2.1、雪崩效应2.2、DubboHystrixCommand三、服务降级四、服务限流4.1、限流算法4.2、应用级限流4.3、池化技术4.4、分布式限流4.5、基于Redis 功能的实现限流4.6、基于令牌桶算法的实现4.6.1 、Java实现一、spring cloud 有什么…...
![](https://img-blog.csdnimg.cn/img_convert/056e5053ca69d31604a568453bb78991.png)
Tomcat构建
软件架构C/S:Client/Server.需要安装才能使用。B/S:Brower/Server。有浏览器就可以。资源分类动态资源:每个用户访问相同的资源后,得到的结果可能不一样,称为动态资源。动态资源被访问后,先转换为静态资源,再被浏览器解…...
![](https://img-blog.csdnimg.cn/eb7ddd00a79e435f979e0f0bb9b5ba2c.png#pic_center)
入门深度学习——基于全连接神经网络的手写数字识别案例(python代码实现)
入门深度学习——基于全连接神经网络的手写数字识别案例(python代码实现) 一、网络构建 1.1 问题导入 如图所示,数字五的图片作为输入,layer01层为输入层,layer02层为隐藏层,找出每列最大值对应索引为输…...
![](https://img-blog.csdnimg.cn/img_convert/39cef06a269afab72e13fb9fdfa8e4c4.png)
预算砍砍砍,IT运维如何降本增效
疫情短暂过去,一个乐观的共识正在蔓延:2023年的互联网,绝对不会比2022年更差。 “降本”是过去一年许多公司的核心策略,营销大幅缩水、亏损业务大量撤裁,以及层出不穷的裁员消息。而2023年在可预期的经济复苏下&#…...
![](https://img-blog.csdnimg.cn/2088790f58614ec9902029a4e3fe16df.png)
10.Jenkins用tags的方式自动发布java应用
Jenkins用tags的方式自动发布java应用1.配置jenkins,告诉jenkins,jdk的安装目录,maven的安装目录2.构建一个maven项目指定构建参数,选择Git Paramete在源码管理中,填写我们git项目的地址,调用变量构建前执行…...
![](https://www.ngui.cc/images/no-images.jpg)
2023新华为OD机试题 - 相同数字的积木游戏 1(JavaScript)
相同数字的积木游戏 1 题目 小华和小薇一起通过玩积木游戏学习数学。 他们有很多积木,每个积木块上都有一个数字, 积木块上的数字可能相同。 小华随机拿一些积木挨着排成一排,请小薇找到这排积木中数字相同且所处位置最远的 2 块积木块,计算他们的距离。 小薇请你帮忙替她…...
![](https://lucas-default-bucket.oss-cn-hangzhou.aliyuncs.com/imgbed/image-20230131195507602.png)
重构之改善既有代码的设计(一)
1.1 何为重构,为何重构 第一个定义是名词形式: 重构(名词):对软件内部结构的一种调整,目的是在不改变「软件可察行为」前提下,提高其可理解性,降低修改成本。 「重构」的另一个用…...
![](https://www.ngui.cc/images/no-images.jpg)
Kotlin data class 数据类用法
实验数据 {"code":1,"message":"成功","data":{"name":"周杰轮","gender":1} }kotlin数据类使用方便提供如下内部Api: equals()/hashCode()对 toString() componentN()按声明顺序与属性相…...
![](https://img-blog.csdnimg.cn/b64ec2c7b615411eb78e9a79206095df.jpeg)
随笔-老子不想牺牲了
18年来到这个项目组,当时只有8个人,包括经常不在的架构师和经理。当时的工位在西区1栋A座,办公桌很宽敞。随着项目的发展,入职的人越来越多,项目的工位也是几经搬迁。基本上每次搬迁时,我的工位都是挑剩下的…...
![](https://img-blog.csdnimg.cn/a005782838df46fbb558876269d43e78.png#pic_center)
三种查找Windows10环境变量的方法
文章目录一.在设置中查看二. 在我的电脑中查看三. 在资源管理器里查看一.在设置中查看 在系统中搜索设置 打开设置,在设置功能里,点击第一项 系统 在系统功能里,左侧菜单找到关于 在关于的相关设置里可以看到高级系统设置 点击高级系…...
![](https://img-blog.csdnimg.cn/img_convert/fa65d350ae0201a1f3f9aebc354a7f61.jpeg)
STM32单片机DS18B20测温程序源代码
OLED液晶屏电路接口DS18B20电路接口STM32单片机DS18B20测温程序源代码#include "sys.h"#define LED_RED PBout(12)#define LED_GREEN PBout(13)#define LED_YELLOW PBout(14)#define LED_BLUE PBout(15)#define DS18B20_IO_IN() {GPIOA->CRL&0XFFFFFFF0;GPIOA…...
![](https://img-blog.csdnimg.cn/28a9e2c97d164aad9e65aabfd24504a7.jpeg)
java日志查看工具finder介绍
目录 一、finder介绍 二、单节点部署 1、服务器需要安装Tomcat,以2.82.16.35为例 2、进入Tomcat下目录webapps下,创建FIND目录,进入FIDN目录 3、下载findweb插件,解压缩 4、登录页面,配置 5、添加日志路径 三、…...
![](https://www.ngui.cc/images/no-images.jpg)
手写现代前端框架diff算法-前端面试进阶
前言 在前端工程上,日益复杂的今天,性能优化已经成为必不可少的环境。前端需要从每一个细节的问题去优化。那么如何更优,当然与他的如何怎么实现的有关。比如key为什么不能使用index呢?为什么不使用随机数呢?答案当然…...
![](/images/no-images.jpg)
做感恩网站的图片素材/短视频推广公司
【转】超时,可以用Java线程池ExecutorService类配合Future接口来实现在Java中,如果需要设定代码执行的最长时间,即超时,可以用Java线程池ExecutorService类配合Future接口来实现。 Future接口是Java标准API的一部分,在…...
![](/images/no-images.jpg)
深圳做网站比较好/什么软件可以免费发广告
import csv#从文件读取reader csv.reader(file(srcFilePath,rb))for line in reader: #忽略第一行 if reader.line_num 1: continue #line是个list,取得所有需要的值 type line[0]#写入文件writer csv.writer(open(targetFile,"wb"…...
![](https://img-blog.csdnimg.cn/img_convert/ad1b06ad09d887417d1de5903a6bce7f.png)
未及时取消网站备案/营销网络的建设怎么写
转自:https://blog.csdn.net/morixinguan/article/details/51799668 作者:Engineer-Bruce_Yang就像下面的这个表之前写过上面这个标题的一篇文章,讲的是以位移的方式去遍历表中的数据,效率非常高,但是,如…...
![](/images/no-images.jpg)
郑州响应式网站制作/百度首页百度一下
Xamarin基础命名空间Microsoft.SqlServer.Server 该命名空间包含大量的类、接口和枚举,用于操作微软SQL Server数据库。该空间支持Xamarin.iOS和Xamarin.Android,不支持WinPhone和Forms。在使用的时候,需要先引入System.Data.dll。转载于:htt…...
![](http://www.easydarwin.org/skin/easydarwin/images/wx_qrcode.jpg)
网站收录500多页/苏州seo网站优化软件
前言 随着Android系统的不断更新和发展,现在越来越多的硬件产品选择用安卓系统作为运行环境,电视机,机顶盒、门禁、行车记录仪、车载系统、单兵设备等等,Android系统底层还是Linux,但对上层的开发和维护就变得容易很多…...
![](https://img-blog.csdnimg.cn/20210129185004328.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQxNzI2,size_16,color_FFFFFF,t_70)
网页设计与制作摘要/南宁seo标准
Spring——IOC(控制反转) 文章目录一、IOC容器 1、什么是IOC(控制反转) 2、IOC底层 3、Spring提供的IOC容器实现的两种方式(两个接口) 4、ApplicationContext接口的实现类(具体根据API文…...