以题为例 浅谈前缀和算法

2024-03-10 14:52
文章标签 算法 浅谈 前缀 题为

本文主要是介绍以题为例 浅谈前缀和算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前缀求和算法是什么

前缀和算法就是以空间去换取时间,可用于快速求数组的区间和,它可以用于一维数组和二维数组,但我现在只接触了一维数组并没有接触二维数组,所以在这里先介绍一维数组前缀和相关的知识

前缀和典型代码

	for(int i=1;i<=n;i++){scanf("%d",&t);s[i]=s[i-1]+t;}	

这里一定要求i从1开始计数,当然在这里我们统一的将下表设置为从1开始,具体是要考虑到我们的边界问题,也就是S[1]的求法问题,为了保证我们循环的统一性,我们要将S[0]设置为0,所以我们索性就将下标从1开始设置起,这样也有利于我们后面的初始化,同时也方便了我们的计算;

题例

以题为例见真章

P8649 [蓝桥杯 2017 省 B] k 倍区间

题目链接:[蓝桥杯 2017 省 B] k 倍区间 - 洛谷

题目描述:

给定一个长度为 NN 的数列,A1,A2,⋯ANA1​,A2​,⋯AN​,如果其中一段连续的子序列 Ai,Ai+1,⋯Aj(i≤j)Ai​,Ai+1​,⋯Aj​(i≤j) 之和是 KK 的倍数,我们就称这个区间 [i,j][i,j] 是 KK 倍区间。

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

输入格式:

第一行包含两个整数 NN 和 KK(1≤N,K≤105)(1≤N,K≤105)。

以下 NN 行每行包含一个整数 AiAi​(1≤Ai≤105)(1≤Ai​≤105)。

输出格式:

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

代码

#include<iostream>
using namespace std;
long long a[100005],b[100005],n,k,c,t;
int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>t;a[i]=a[i-1]+t;}for(int i=0;i<=n;i++){c+=b[a[i]%k]++;}cout<<c<<"";return 0;
}

这里解释一下这道题目,以及代码;

题目的题意就是获取这n个数的连续区间之后是不是k的倍数;

代码解释:首先去求前缀和,这是第一个for循环需要做的;

第二个for循环要做的就是求区间,我当时有个疑问就是为什么这样去求区间,在这里解释一下,当两个数去余同一个数并且余数相同那么这两个数之差就是这个数的倍数如:9和17余8都为1,他们相减就是8是8的倍数;这里还需要注意,他这里是先把b[a[i]%k]的值先赋给c之后在自加的,所以当两个数的余数相同时,只会加一个1;还有注意这个i必需从0开始,因为有的数余数肯定为0,那么这个数就可以是一个区间就要相加;

这道题有第二种解法,但感觉太麻烦,我们直接去求这几个和的差,那么第二个就需要两个for循环增加了时间复杂度

第二种方法代码如下

#include<iostream>
using namespace std;
long long a[100005],b[100005],n,k,c,t;
int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>t;a[i]=a[i-1]+t;}for(int i=0;i<n;i++){for(int j=i+1;j<=n;j++){if((a[j]-a[i])%k==0)c++;}}cout<<c<<"";return 0;
}

交上去被提示时间超时了,所以第二种方法时间复杂度太大了

这篇关于以题为例 浅谈前缀和算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/794582

相关文章

浅谈mysql的not exists走不走索引

《浅谈mysql的notexists走不走索引》在MySQL中,​NOTEXISTS子句是否使用索引取决于子查询中关联字段是否建立了合适的索引,下面就来介绍一下mysql的notexists走不走索... 在mysql中,​NOT EXISTS子句是否使用索引取决于子查询中关联字段是否建立了合适的索引。以下

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

正则表达式r前缀使用指南及如何避免常见错误

《正则表达式r前缀使用指南及如何避免常见错误》正则表达式是处理字符串的强大工具,但它常常伴随着转义字符的复杂性,本文将简洁地讲解r的作用、基本原理,以及如何在实际代码中避免常见错误,感兴趣的朋友一... 目录1. 字符串的双重翻译困境2. 为什么需要 r?3. 常见错误和正确用法4. Unicode 转换的

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Java如何根据文件名前缀自动分组图片文件

《Java如何根据文件名前缀自动分组图片文件》一大堆文件(比如图片)堆在一个目录下,它们的命名规则遵循一定的格式,混在一起很难管理,所以本文小编就和大家介绍一下如何使用Java根据文件名前缀自动分组图... 目录需求背景分析思路实现代码输出结果知识扩展需求一大堆文件(比如图片)堆在一个目录下,它们的命名规

浅谈Redis Key 命名规范文档

《浅谈RedisKey命名规范文档》本文介绍了Redis键名命名规范,包括命名格式、具体规范、数据类型扩展命名、时间敏感型键名、规范总结以及实际应用示例,感兴趣的可以了解一下... 目录1. 命名格式格式模板:示例:2. 具体规范2.1 小写命名2.2 使用冒号分隔层级2.3 标识符命名3. 数据类型扩展命

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n