当前位置: 首页 > 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建立相对简…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...