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

以题为例 浅谈前缀和算法

前缀求和算法是什么

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

前缀和典型代码

	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;
}

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

相关文章:

以题为例 浅谈前缀和算法

前缀求和算法是什么 前缀和算法就是以空间去换取时间&#xff0c;可用于快速求数组的区间和&#xff0c;它可以用于一维数组和二维数组&#xff0c;但我现在只接触了一维数组并没有接触二维数组&#xff0c;所以在这里先介绍一维数组前缀和相关的知识 前缀和典型代码 for(int…...

【Python】进阶学习:OpenCV--一文详解cv2.namedWindow()

【Python】进阶学习&#xff1a;OpenCV–一文详解cv2.namedWindow() &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&#x1f448; 希望…...

【嵌入式】字体极限瘦身术:Fontmin在嵌入式UI中的魔法应用(附3500常用汉字)

&#x1f9d1; 作者简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟。提供嵌入式方向的学习指导、简历面…...

蓝桥杯递推与递归法|斐波那契数列|数字三角形|42点问题|数的计算|数的划分(C++)

递归是用来做dfs&#xff0c;是搜索算法的基础 递推是用来做dp部分&#xff0c;及部分其他算法&#xff0c;复杂度较低&#xff0c;不会出现爆栈问题递推法&#xff1a; 递推法是一种在数学和其他领域广泛应用的重要方法&#xff0c;它在计算机科学中被用作一种关键的数值求解…...

遗留系统现代化:理解、策略与案例

文章目录 一、什么是遗留系统二、遗留系统的特点三、改造遗留系统的方法四、案例4.1 重构4.2 替换4.3 封装4.4 服务化 五、总结 一、什么是遗留系统 遗留系统&#xff08;Legacy System&#xff09;是指在组织中已经存在一段时间&#xff0c;通常是几年或更长时间的信息系统。…...

2024.3.9 C++启航 梦开始的地方

一.基本格式: #include<iostream>using namespace std;int main() {return 0; } 二.注释 1.当行注释: 同C语言//描述信息 2.多行注释: /*描述信息*/ 三.输入输出 既可以使用scanf和printf 也可以使用标准输入流对象cin和标准输出流对象cout,且cin cout更安全和方…...

Ubuntu平铺左、右、上、下、1/2、1/4窗口(脚本)

前言 之前因为一直在用Ubuntu 18或者Ubuntu 20然后发现装了GNOME插件后&#xff0c;电脑在使用过程中&#xff0c;会时不时的卡死&#xff08;鼠标没问题&#xff0c;键盘输入会有10-20秒的延迟&#xff09;频率基本是一小时一次&#xff0c;因为这种卡顿会很容易打断思路&…...

深度学习+感知机

深度学习感知机 1感知机总结 2多层感知机1XOR2激活函数3多类分类总结 3代码实现 1感知机 是个很简单的模型,是个二分类的问题。 感知机&#xff08;perceptron&#xff09;是Frank Rosenblatt在1957年提出的一种人工神经网络&#xff0c;被视为一种最简单形式的前馈神经网络&…...

爬虫练习:获取某招聘网站Python岗位信息

一、相关网站 二、相关代码 import requests from lxml import etree import csv with open(拉钩Python岗位数据.csv, w, newline, encodingutf-8) as csvfile:fieldnames [公司, 规模,岗位,地区,薪资,经验要求]writer csv.DictWriter(csvfile, fieldnamesfieldnames)writer…...

Java对接腾讯云直播示例

首先是官网的文档地址 云直播 新手指南 可以发现它这个主要是按流量和功能收费的 价格总览 流量这里还只收下行的费用&#xff0c;就是只收观看消耗的流量费 其它的收费就是一些增值业务费 &#xff08;包括直播转码、直播录制、直播截图、直播审核、智能鉴黄、实时监播、移动直…...

free pascal 调用 C#程序读 Freeplane.mm文件,生成测试用例.csv文件

C# 请参阅&#xff1a;C# 用 System.Xml 读 Freeplane.mm文件&#xff0c;生成测试用例.csv文件 Freeplane 是一款基于 Java 的开源软件&#xff0c;继承 Freemind 的思维导图工具软件&#xff0c;它扩展了知识管理功能&#xff0c;在 Freemind 上增加了一些额外的功能&#x…...

在Blender中清理由Instant-NGP等几何学习技术生成的网格

使用布尔运算: 创建一个大的立方体或其他简单几何体包裹住全部网格。使用布尔修改器对两个网格进行“差集”运算。这将移除超出包裹体之外的多余网格部分。 手动选择并删除: 进入编辑模式&#xff08;按Tab键&#xff09;。按A键取消选择所有顶点。按B键并拖动以选择您想要删除…...

【重要公告】BSV区块链上线TypeScript SDK,未来将支持更多开发语言

​​发表时间&#xff1a;2024年2月21日 BSV区块链协会宣布上线JavaScript和TypeScript SDK&#xff08;即“标准开发工具包”&#xff09;。TypeScript SDK旨在为开发者提供新版统一核心代码库&#xff0c;以便利开发者在BSV区块链上开发能够任意扩容的应用程序。新上线的SDK替…...

【工具使用-VScode】VScode如何设置空格和tab键显示

一&#xff0c;简介 在提交代码的时候&#xff0c;行末尾的tab和空格不符合规范&#xff0c;但是如果在vscode中不显示tab和空格的话&#xff0c;不能及时的查看到并改正&#xff0c;导致提交代码之后还需要再次进行修改&#xff0c;效率比较低。 代码编辑界面如图所示&#…...

【原理图PCB专题】Cadence 17.4版本原理图及PCB Mudule复用

在我们设计复杂板卡的时候,往往会遇到一部分电路被反复使用的情况。虽然使用复制黏贴我们很快的做出相同的设计,但由于不同工程师能力水平不同,有时可能存在部分电路被漏掉导致重大异常。尤其对于大规模复杂设计,如果设计者浪费时间制作相同模块上,这无疑是对于工程师精力…...

llama-index调用qwen大模型实现RAG

背景 llama-index在实现RAG方案的时候多是用的llama等英文大模型&#xff0c;对于国内的诸多模型案例较少&#xff0c;本次将使用qwen大模型实现llama-index的RAG方案。 环境配置 &#xff08;1&#xff09;pip包 llamaindex需要预装很多包&#xff0c;这里先把我成功的案例…...

基于springboot的医院信息管理系统(程序+代码+文档)

** &#x1f345;点赞收藏关注 → 私信领取本源代码、数据库&#x1f345; 本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目&#xff0c;希望你能有所收获&#xff0c;少走一些弯路。&#x1f345;关注我不迷路&#x1f345;** 一、研究背景…...

【环境配置】Linux MySQL8 忘记密码解决措施

本片博客介绍 Linux 操作系统 Ubuntu 下&#xff0c;MySQL8 忘记密码怎么重新设置&#xff0c;笔者亲测有效&#xff0c;分享给大家。 查看 MySQL 版本 $ mysql --version停止 MySQL 服务器&#xff0c;并查看状态是否变更为 Server shutdown complete # 等价命令sudo syste…...

MySQL-锁:共享锁(读)、排他锁(写)、表锁、行锁、意向锁、间隙锁,锁升级

MySQL-锁&#xff1a;共享锁&#xff08;读&#xff09;、排他锁&#xff08;写&#xff09;、表锁、行锁、意向锁、间隙锁 共享锁&#xff08;读锁&#xff09;、排他锁表锁行锁意向锁间隙锁锁升级 MySQL数据库中的锁是控制并发访问的重要机制&#xff0c;它们确保数据的一致性…...

docker 使用官方镜像搭建 PHP 环境

一、所需环境&#xff1a; 1、PHP&#xff1a;7.4.33-fpm 的版本 2、Nginx&#xff1a;1.25.1 的版本 3、MySQL&#xff1a; 5.7 的版本 4、Redis&#xff1a;7.0 的版本 1.1、拉取官方的镜像 docker pull php:7.4.33-fpm docker pull nginx:1.25.1 docker pull mysql:5.7 do…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...