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

蓝桥杯刷题|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;} 

http://www.lryc.cn/news/322281.html

相关文章:

  • 【动态三维重建】Deformable 3D Gaussians 可变形3D GS用于单目动态场景重建(CVPR 2024)
  • 智能驾驶域控制器行业介绍
  • [数据集][目标检测]焊接件表面缺陷检测数据集VOC+YOLO格式2292张10类别
  • 微信小程序的页面制作---常用组件及其属性
  • 什么样的网站不适合使用WordPress?
  • vulhub中GitLab 任意文件读取漏洞复现(CVE-2016-9086)
  • 【爬虫】web自动化和接口自动化
  • 哔哩哔哩后端Java一面
  • Vue.js前端开发零基础教学(二)
  • Bert模型输出:last_hidden_state转换为pooler_output
  • Docker Compose 基本语法
  • 【算法集训】基础算法:贪心
  • Centos7部署单节点MongoDB(V4.2.25)
  • 隐私计算笔记(1)
  • 查询方法需要使用事务吗?
  • 剑指offer面试题40 数组中只出现一次的数字
  • gitLab server version 13.12.1 is not supported
  • 如何在 iPhone 上使用蓝牙鼠标
  • matlab simulink 电力系统同步发电机励磁系统的建模与仿真
  • AI新工具(20240320) AI创作一首属于自己的音乐; 轻松制作具有透明背景的高质量图像
  • IT服务ITIL4 认证:助力企业数字化转型的必杀技!
  • 微软聘请了谷歌DeepMind的联合创始人
  • JavaMySQL高级一(下)
  • HCIA复习
  • 5G里面NR,gNB,en-gNB,ng-eNB是什么意思
  • android 网络检测简单方法
  • 列表(list)篇(二)
  • Python的反射机制
  • Python数学建模-2.9Matplotlib库
  • 【MySQL】数据库的基础概念