蓝桥杯刷题|03普及-真题

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

题目描述

给定一个长度为 N 的数列,A_{1}​,A_{2},⋯A_{N},如果其中一段连续的子序列 A_{i}​,A_{i+1},⋯A_{j} (i≤j) 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。

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

输入格式

第一行包含两个整数 N 和 K(1≤N,K≤10^{5})。

以下 N 行每行包含一个整数 A_{i}(1≤A_{i}10^{5})。

输出格式

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

输入输出样例

输入 #1

5 2
1  
2  
3  
4  
5  

输出 #1  6

说明/提示

时限 2 秒, 256M。蓝桥杯 2017 年第八届

        对于这个题,先用了暴力枚举来解题,发现只能过两个样例,其他的都超时了,之后看了题解,他们用了前缀和思想,下面我就整理前缀和相关概念和解题方法。

前缀和

前缀和是什么?

通俗理解,前缀和就是任意一个元素前面所有元素的和(包括本身);

例如:这有一个数组arr[3]={1,2,3}

           如果设定一个数组为此数组的前缀和数组perfix[3]={1,3,6}

前缀和的好处

好处就是减少时间复杂度,例如上面的题,要求一段区间的和,用暴力枚举就会超时。使用前缀和,我们只需要用末尾的前缀和减去初位置的前缀和就可以得到该区间的和了;

我们来举个例子吧。定义一个arr[6]={1,2,3,4,5,6},求这个数组的任意一个区间[i,j]的和

暴力枚举

我们肯定会从第一个元素开始,每次往后+1;然后从第二个元素开始,每次往后+1...;

假设要求[i,j]这个区间的和

	for(int t=0;i<t;t++)
        int num1+=arr[t];
	for(int m=j;m<=j;m++)
		int num2+=arr[m];
    int num=num2-num1;

	

前缀和

定义一个 前缀和数组,从头开始求前缀和之后的前缀和就是前一个前缀和加上当前元素

prefix[0]=arr[0];
for(int n=0;n<arr.size;i++)
    prefix[n]=prefix[n-1]+arr[n];
int num=predix[j]-prefix[i-1];

prefix[j]-prefix[i-1]=arr[i]+arr[i+1]+...+arr[j];

因为这个题是一维的,我们就先介绍一维前缀和。

K倍区间解题思路

这个题不仅利用了前缀和还要转换思想,要求K的倍数,也就是是说根据前缀和里面的元素的运算得到的结果,只要没有余数就行,为防止数值溢出,我们可以只给前缀和里面存余数就行,余数如果为0,那么就是k的倍数。

因此这个前缀和数组中存的不是和,而是和的余数。具体操作如下:

prefix[0]=arr[0];
for(int n=0;n<arr.size;i++)
    prefix[n]=(prefix[n-1]+arr[n])/K;

第一步可以直接判断prefix数组里面的值是否0,等于0就是K 的倍数。

第二步就是中间子序列的值是否是K的倍数,令这个子序列的左下标为left,令右下标为right,那么子序列的和可以表示为prefix[right]-prefix[left-1],判断是不是K的倍数就是判断这个子序列的和除于K的余数是否为0。

(prefix[right]-prefix[left-1])%K==0

prefix[right]%K-prefix[left-1]%K==0

prefix[right]%K==prefix[left-1]%K

因此只要判断prefix[right]%K==prefix[left-1]%K就行,换个说法就是要找相同的有几个,假如有a个相同,这些相同的两两组合就可以构成一个子序列,也就是高中学的排列组合,我定义一个cnt数组,里面的数就代表i向同的有几个,然后两两组合,也就是

C_{cnt[i]}^{2}=\frac{cnt[i]*(cnt[i]-1)}{2*1}

最后不要忘了前缀和里面单独余数为0的也是K的倍数,cnt[0]就是余数为0的个数。加上就行。

最后就是注意,记得数据类型定义为long long int

具体代码如下

 #include<iostream>
#include<vector>
using namespace std;
long long int n=1e6+10;
int main()
{
	long long int N,K,num=0,i;
	cin>>N>>K;
	vector <long long int>arr(n);//原数组 
	vector <int>prefix(n);//前缀和数组
	vector <long long int>cnt(n);
	
	for(i=1;i<=N;i++)
	{
		cin>>arr[i];//数组输入
		prefix[i]=(prefix[i-1]+arr[i])%K;//前缀和数组 
		cnt[prefix[i]]++;//统计里面相同的 
		
	}
	
	for(i=0;i<N;i++)
	{
		num+=cnt[i]*(cnt[i]-1)/2;//将相同的进行排列组合 
	}
	cout<<num+cnt[0];//余数为0的本来就是K的倍数 
	return 0;
 } 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

算法设计与分析-动态规划算法的应用——沐雨先生

一、实验目的 1&#xff0e; 掌握动态规划算法的基本思想&#xff0c;包括最优子结构性质和基于表格的最优值计算方法。 2&#xff0e;熟练掌握分阶段的和递推的最优子结构分析方法。 3&#xff0e; 学会利用动态规划算法解决实际问题 。 二、实验内容 1. 问题描述 &#…

Linux之缓冲区与C库IO函数简单模拟

缓冲区 首先, 我们对缓冲区最基本的理解, 是一块内存, 用户提供的缓冲区就是用户缓冲区, C标准库提供的就是C标准库提供的缓冲区, 操作系统提供的就是操作系统缓冲区, 它们都是一块内存. 为什么要有缓冲区? 先举个生活中的例子, 我们寄快递的时候往往是去驿站寄快递, 而不是…

4 个多月的蓝猫吃什么猫粮发腮快?

亲爱的猫友们&#xff0c;你们是不是也在为蓝猫的发腮问题而苦恼呢&#xff1f;&#x1f431; 四个多月的蓝猫正处于生长发育的关键时期&#xff0c;选择合适的猫粮对于它们的健康与美丽至关重要。 &#x1f50d; 在选择猫粮时&#xff0c;我们要关注几个关键点&#xff1a;高…

Elasticsearch从入门到精通-06ES统计分析语法

Elasticsearch从入门到精通-06ES统计分析语法 bucket和metric概念简介 bucket就是一个聚合搜索时的数据分组。如&#xff1a;销售部门有员工张三和李四&#xff0c;开发部门有员工王五和赵六。那么根据部门分组聚合得到结果就是两个bucket。销售部门bucket中有张三和李四&…

window下安装并使用nvm(含卸载node、卸载nvm、全局安装npm)

window下安装并使用nvm&#xff08;含卸载node、卸载nvm、全局安装npm&#xff09; 一、卸载node二、安装nvm三、配置路径和下载源四、使用nvm安装node五、nvm常用命令六、卸载nvm七、全局安装npm、cnpm八、遇到的问题 nvm 全名 node.js version management&#xff0c;顾名思义…

远程桌面安卓版下载 安卓远程控制免费版

远程桌面安卓版下载与安卓远程控制免费版的应用解析 随着移动互联网的快速发展&#xff0c;远程桌面应用逐渐成为了许多用户、特别是技术爱好者和商务人士的必备工具。它们不仅可以在电脑上实现远程控制&#xff0c;还能将这种功能延伸到移动设备上&#xff0c;如安卓手机和平…

Acwing.167 木棒(回溯)

题目 乔治拿来一组等长的木棒&#xff0c;将它们随机地砍断&#xff0c;使得每一节木棍的长度都不超过 50 个长度单位。 然后他又想把这些木棍恢复到为裁截前的状态&#xff0c;但忘记了初始时有多少木棒以及木棒的初始长度。 请你设计一个程序&#xff0c;帮助乔治计算木棒…

年度告警分类统计

1、打开前端Vue项目kongguan_web&#xff0c;完成前端src/components/echart/YearWarningChart.vue页面设计 在YearWarningChart.vue页面添加div设计 <template><div class"home"><div style"margin: 0px auto;height: 100%"><div …

金蝶云星空——单据附件上传

文章目录 概要技术要点代码实现小结 概要 单据附件上传 技术要点 单据附件上传金蝶是有提供标准的上传接口&#xff1a; http://[IP]/K3Cloud/Kingdee.BOS.WebApi.ServicesStub.DynamicFormService.AttachmentUpLoad.common.kdsvc 参数说明 参数类型必填说明FileName字符是…

基于springboot+vue的乡村民宿管理系统

一、系统架构 前端&#xff1a;vue | element-ui 后端&#xff1a;springboot | mybatis-plus 环境&#xff1a;jdk1.8 | mysql | maven | nodejs 二、代码及数据库 三、功能介绍 01. 登录页 02. 注册 03. 管理员-首页 04. 管理员-信息管理-公告信息 05. 管理员…

淘宝|天猫|京东|1688主流电商平台的实时数据返回接口|附Python实例

导读&#xff1a;随着淘宝/天猫直通车功能升级&#xff0c;很多功能越来越白盒化&#xff0c;越来越简化&#xff0c;更方便用户的操作&#xff0c;只需一键即可看出淘宝/天猫直通车存在的问题。淘宝/天猫直通车千人千面后有了实时数据工具&#xff0c;下面通过一个案例告诉大家…

【Android】【Bluetooth Stack】蓝牙电话本协议之同步通话记录分析(超详细)

1. 精讲蓝牙协议栈&#xff08;Bluetooth Stack&#xff09;&#xff1a;SPP/A2DP/AVRCP/HFP/PBAP/IAP2/HID/MAP/OPP/PAN/GATTC/GATTS/HOGP等协议理论 2. 欢迎大家关注和订阅&#xff0c;【蓝牙协议栈】专栏会持续更新中.....敬请期待&#xff01; 目录 1. 协议简述 1.1 PBAP…

Day02-DDLDMLDQL(定义,操作,查询)(联合查询,子查询,字符集和校对集,MySQL5.7乱码问题)

文章目录 Day02-DDL&DML和DQL学习目标1. SQL语言的组成2. DDL2.1 数据库结构2.2 表结构2.3 约束2.3.1 主键约束(重要)(1)特点(2) 添加主键(3)删除主键(了解) 2.3.2 自增约束(1)特点(2) 添加自增约束(3)删除自增约束(了解) 2.3.3 非空约束(1)添加非空约束(2) 删除非空约束 2…

day01_mysql数据类型和运算符_课后练习 - 参考答案

文章目录 day01_mysql_课后练习第1题第2题第3题第4题第5题 day01_mysql_课后练习 第1题 案例&#xff1a; 1、创建数据库day01_test01_library 2、创建表格books 字段名字段说明数据类型允许为空唯一b_id书编号int(11)否是b_name书名varchar&#xff08;50&#xff09;否否…

OLAP数据库选型指南:Doris与ClickHouse的深入对比与分析

码到三十五 &#xff1a; 个人主页 心中有诗画&#xff0c;指尖舞代码&#xff0c;目光览世界&#xff0c;步履越千山&#xff0c;人间尽值得 ! 在当今数据驱动的时代&#xff0c;数据的存储、处理和分析变得尤为重要。为了满足这一需求&#xff0c;市场上涌现出了许多优秀的…

FPGA Vivado环境下实现D触发器

题目要求&#xff1a;使用Verilog HDL语言设计一个D触发器。请提交程序源代码和Word格式的作业文档&#xff0c;作业文档中应给出程序源代码及RTL分析原理图。 D触发器的工作原理&#xff1a; 初始状态下&#xff0c;触发器处于复位状态&#xff0c;输出为复位信号的稳定状态…

Linux笔试题

1. 程序代码如下&#xff0c;请按执行顺序写出输出结果: int main() { pid_t pid1,pid2;if((pid1fork()) 0) {sleep(3);printf(“info1 from child process_1\n”);exit(0);printf(“info2 from child process_1\n”); } else {if((pid2fork()) 0){sleep(1);printf(“i…

排序算法:快速排序(非递归)

文章目录 一、先建立一个栈二、代码编写 !](https://img-blog.csdnimg.cn/direct/870dd101173d4522862e4459b32237a3.png) 先赞后看&#xff0c;养成习惯&#xff01;&#xff01;&#xff01;^ _ ^<3 ❤️ ❤️ ❤️ 码字不易&#xff0c;大家的支持就是我坚持下去的动力…

力扣刷题-砖墙题554

砖墙题 这题一开始没有想到思路&#xff0c;一开始还想着用枚举法做/笑哭 后来看了题解&#xff0c;原来就是哈希表的题目呀。 说到哈希表&#xff0c;这里有个八股需要记一下&#xff1a; HashMap和HashTable的区别 线程是否安全&#xff1a;HashMap线程不安全 HashTable线…

[综述笔记]Flexible large-scale fMRI analysis: A survey

论文网址&#xff1a;Flexible large-scale fMRI analysis: A survey | IEEE Conference Publication | IEEE Xplore 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff0…