当前位置: 首页 > news >正文

【蓝桥集训】第一天——前缀和

作者:指针不指南吗
专栏:Acwing 蓝桥集训每日一题

🐾输出的时候,注意数据类型🐾

文章目录

    • 1.截断数组
    • 2.前缀和
    • 3.子矩阵的和
    • 4.k倍区间

1.截断数组

给定一个长度为 n 的数组 a1a_1a1,a2a_2a2,…,ana_nan

现在,要将该数组从中间截断,得到三个非空子数组。

要求,三个子数组内各元素之和都相等。

请问,共有多少种不同的截断方法?

输入格式

第一行包含整数 n。

第二行包含 n个整数 a1a_1a1,a2a_2a2,…,ana_nan

输出格式

输出一个整数,表示截断方法数量。

数据范围

前六个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤10510^5105,−10000≤aia_iai≤10000。

输入样例1:

4
1 2 3 3

输出样例1:

1

输入样例2:

5
1 2 3 4 5

输出样例2:

0

输入样例3:

2
0 0

输出样例3:

0
  • 思路

    • 分三个非空子数组且和相同,即每个子数组的和是s[n]/3;

    • 首先呢,枚举两个节点肯定不行,时间复杂度是 O(n2n^2n2),题里面的数量级太大了

    所以只能尝试枚举一个节点,再把剩下一个表示出来

    • 做法:枚举第二个节点 j ,随着 j 的增加,第一个节点满足 s[n]/3,也会增加,用cnt 存储 j 前面满足条件的第一个节点,当j 也满足条件时,把总的存在 ans 中

    • 注意:结果最大是100010的阶乘,远超int 类型,会爆,开long long

    ​ 考虑特殊请款,不够三个元素,s[n]%3!=0

在这里插入图片描述

  • 代码实现

    #include<bits/stdc++.h>
    using namespace std;int s[100010];
    long long ans;int main()
    {int n;cin>>n;for(int i=1;i<=n;i++){  //计算前缀和scanf("%d",&s[i]);s[i]+=s[i-1];}//考虑特殊情况if(s[n]%3!=0||n<3){cout<<0;return 0;}int cnt=0;for(int i=2;i<n;i++){if(s[i-1]==s[n]/3)  cnt++;  //第二个节点之前,满足条件可以成为第一个节点的个数if(s[i]==s[n]/3*2)  ans+=cnt;  //满足条件,成为第二个节点,加上第一个节点,类似于加法原理}printf("%lld",ans);  //注意数据类型时long longreturn 0;
    }
    

2.前缀和

输入一个长度为 n 的整数序列。

接下来再输入 m个询问,每个询问输入一对 l,r。

对于每个询问,输出原序列中从第 l个数到第 r个数的和。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n个整数,表示整数数列。

接下来 m行,每行包含两个整数 l 和 r,表示一个询问的区间范围。

输出格式

共 m 行,每行输出一个询问的结果。

数据范围

1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000−1000≤数列中元素的值≤1000

输入样例:

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例:

3
6
10
  • 代码实现

    #include<bits/stdc++.h>
    using namespace std;int s[100010];int main()
    {int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];s[i]+=s[i-1];}while(m--){int a,b;cin>>a>>b;cout<<s[b]-s[a-1]<<endl;}return 0;
    }
    

3.子矩阵的和

输入一个 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−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 s[N][N];int n,m,q;int main(){cin>>n>>m>>q;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>s[i][j];s[i][j]+=s[i-1][j]+s[i][j-1]+s[i-1][j-1];}while(q--){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];}return 0;
}

4.k倍区间

题目描述

给定一个长度为 N 的数列,1,2,⋯A1,A2,⋯A N,如果其中一段连续的子序列之和是 K 的倍数,我们就称这个区间 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗?

输入描述

第一行包含两个整数 NK(1≤N,K10510^5105 )。

以下 N 行每行包含一个整数 A i ( 1≤A i10510^5105 ).

输出描述

输出一个整数,代表 K 倍区间的数目。

示例

输入

5 2
1
2
3
4
5

输出

6
  • 代码实现
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const LL N=100010;
LL s[N],cnt[N];int main()
{LL n,k,i,r,res=0;cin>>n>>k;for(i=1;i<=n;i++) cin>>s[i];  //前缀和for(i=1;i<=n;i++) s[i]+=s[i-1];//同余cnt[0]=1;  //包含它本身,初始化为1for(r=1;r<=n;r++) {LL u=s[r]%k; res+=cnt[u];cnt[u]++;}cout<<res<<endl;return 0;}

相关文章:

【蓝桥集训】第一天——前缀和

作者&#xff1a;指针不指南吗 专栏&#xff1a;Acwing 蓝桥集训每日一题 &#x1f43e;输出的时候&#xff0c;注意数据类型&#x1f43e; 文章目录1.截断数组2.前缀和3.子矩阵的和4.k倍区间1.截断数组 给定一个长度为 n 的数组 a1a_1a1​,a2a_2a2​,…,ana_nan​。 现在&…...

2022-03-19青少年软件编程(C语言)等级考试试卷(六级)解析

青少年软件编程(C语言)等级考试试卷(六级) 一、编程题(共4题,共100分)T1.多项式相加 我们经常遇到两多项式相加的情况,在这里,我们就需要用程序来模拟实现把两个多项式相加到一起。首先,我们会有两个多项式,每个多项式是独立的一行,每个多项式由系数、幂数这样的多个…...

[JavaScript 刷题] 特殊数组的特征值, leetcode 1608

[JavaScript 刷题] 特殊数组的特征值, leetcode 1608 这道题在一个列表上看到的&#xff0c;刚开始用暴力解想过了就过了&#xff0c;不过后面看了一下关键字&#xff0c;发现解法……非常有趣。 时间复杂度可以从 O(n2)O(n^2)O(n2) 降为 O(nlog(n))O(n log(n))O(nlog(n))&am…...

各种素材网站大全【全部倾倒,福利倒计时-JS,HTML,游戏素材,UI,图片素材等

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! 本文由 秩沅 原创 收录于专栏&#xff1a;解忧杂货铺 ⭐各种素材网站大全⭐ 文章目录⭐各种素材网站大全⭐&#x1f3b6;大家必逛的四大天王…...

影片自由,丝滑流畅,Docker容器基于WebDav协议通过Alist挂载(百度网盘/阿里云盘)Python3.10接入

使用过NAS(Network Attached Storage)的朋友都知道&#xff0c;它可以通过局域网将本地硬盘转换为局域网内的“网盘”&#xff0c;简单理解就是搭建自己的“私有云”&#xff0c;但是硬件和网络成本都太高了&#xff0c;有点可望而不可及的意思。Alist开源库则可以满足我们&…...

【新】华为OD机试 - 数组的中心位置(Python)| 运气好,这就是原题

数组的中心位置 题目 给你一个整数数组nums,请计算数组的中心位置。 数组中心位置是数组的一个下标,其左侧所有元素相乘的积等于右侧所有元素相乘的积。 数组第一个元素的左侧积为1,最后一个元素的右侧积为1。 如果数组有多个中心位置,应该返回最靠近左边的那一个。 如果数…...

小米电视安装 Plex 打造家庭影院

背景 最近突然想重温教父&#xff0c;本来想着直接投屏就可以&#xff0c;后来看了别人搭建的基于 NAS 的家庭影院很动心&#xff0c;也想依葫芦画瓢做一个&#xff0c;跟对象申请经费的时候被拒了&#xff0c;理由是有这钱还不如开个会员直接看。 我寻思不同电影在不同的平台…...

Elasticsearch:Combined fields 查询

有时一个匹配项可以覆盖多个文本字段。 在这种情况下&#xff0c;你可以使用 combined_fields 查询来搜索多个文本字段&#xff0c;就好像它们的值实际上已被索引到一个组合字段中一样。 除此之外&#xff0c;combined_fields 的主要好处是强大且易于理解的评分算法。这种做法也…...

uart 子系统

串口硬件储备知识&#xff1a; uart 在Linux 应用层的体现及使用 uart 就是串口&#xff0c;它也是属于字符设备中的一种&#xff0c;众所周知 字符设备都会在/dev/ 目录下创建节点&#xff0c;串口所创建的节点名都是以tty* 为开头&#xff0c;例如下面这些节点&#xff1a…...

SpringBoot 整合EasyExcel详解

一、概述 Java解析、生成Excel比较有名的框架有Apache poi、jxl。但他们都存在一个严重的问题就是非常的耗内存&#xff0c;poi有一套SAX模式的API可以一定程度的解决一些内存溢出的问题&#xff0c;但POI还是有一些缺陷&#xff0c;比如07版Excel解压缩以及解压后存储都是在内…...

VScode+cuda编程:常见环境问题

VScodecuda&#xff1a;常见环境配置问题1、VScode终端问题(PS)2、编译问题(CUDA版本过低)3、nvcc编译问题(arch架构)1、VScode终端问题(PS) 问题描述&#xff1a; 在VScode下打开终端执行nvcc指令&#xff0c;发现执行不了&#xff0c;但是在外部终端powershell和cmd都可以。…...

简单实用的内网穿透实现教程

内网穿透&#xff0c;字面理解就是网络地址穿透&#xff0c;是一种比较常用的将内网地址转换成公网地址的方式。通过内网穿透&#xff0c;可以将本地内网局域网提供给外网公网上访问&#xff0c;在外网也能连接访问内网主机和应用&#xff0c;当用户有日常远程和异地外网访问的…...

makefile案例学习

makefile案例学习 很多时候&#xff0c; 我们在git clone完一个project之后&#xff0c;就会让我们使用make命令进行项目的构建。这个make命令的背后就是按照了Makefile文件定义的格式去完成项目构建。 因此Makefile的作用就是帮助程序员进行项目的构建&#xff0c;它按照项目…...

MySQL性能优化六 事物隔离级别与锁机制

概述 我们的数据库一般都会并发执行多个事务&#xff0c;多个事务可能会并发的对相同的一批数据进行增删改查操作&#xff0c;可能就会导致我们说的脏写、脏读、不可重复读、幻读这些问题。 这些问题的本质都是数据库的多事务并发问题&#xff0c;为了解决多事务并发问题&#…...

四数之和-力扣18-java排序+双指针

一、题目描述给你一个由 n 个整数组成的数组 nums &#xff0c;和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] &#xff08;若两个四元组元素一一对应&#xff0c;则认为两个四元组重复&#xff09;&#xff1a…...

操作系统开发:BIOS/MBR基础与调试

这里在实验之前需要下载 Bochs-win32-2.6.11 作者使用的是Linux版本的&#xff0c;在Linux写代码不太舒服&#xff0c;所以最好在Windows上做实验&#xff0c;下载好虚拟机以后还需要下载Nasm汇编器&#xff0c;以及GCC编译器&#xff0c;为了能够使用DD命令实现磁盘拷贝&#…...

华为OD机试真题JAVA实现【数组合并】真题+解题思路+代码(20222023)

🔥系列专栏 华为OD机试(JAVA)真题目录汇总华为OD机试(Python)真题目录汇总华为OD机试(C++)真题目录汇总华为OD机试(JavaScript)真题目录汇总文章目录 🔥系列专栏题目输入输出示例一输入输出示例二输入输出解题思路核心知识点...

说说Real DOM和Virtual DOM的区别?优缺点?

说说Real DOM和Virtual DOM的区别&#xff1f;优缺点&#xff1f;Real DOM(真实的DOM)真实dom的优缺点&#xff1f;Virtual DOM(虚拟的DOM)虚拟dom的优缺点&#xff1f;两者的区别Real DOM(真实的DOM) 在页面渲染出的每个节点都是一个真实的DOM结构 <div class"root&…...

使用脚本以可读的 JSON 格式显示 curl 命令输出

在我们经常调试微服务或者使用 Elasticsearch API 时&#xff0c;经常会使用curl 来进行调试。但是有时我们的输出不尽如意。显示的不是一 pretty 格式进行输出的。我们有时还必须借助于其他的一些网站工具&#xff0c;比如 Best JSON Formatter and JSON Validator: Online JS…...

计算机网络9:HTTP和HTTPS的区别

1.HTTP和HTTPS的区别 &#xff08;1&#xff09;安全性 HTTP是超文本传输协议&#xff0c;信息传输存在安全问题HTTPS是安全套接字超文本传输协议&#xff0c;在TCP和HTTP之间加入了SSL/TLS安全协议&#xff0c;进行加密传输 &#xff08;2&#xff09;连接步骤HTTP建立相对简…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...