【每日蓝桥】52、一七年省赛Java组真题“K倍区间”

avatar
avatar
云惠网小编
2845
文章
1
评论
2021年4月6日19:19:03 评论 4 次浏览 1646字阅读5分29秒
摘要

你好呀,我是灰小猿,一个超会写bug的程序猿!欢迎大家关注我的专栏“每日蓝桥”,该专栏的主要作用是和大家分享近几年蓝桥杯省赛及决赛等真题,解析其中存在的算法思想、数据结构等内容,帮助大家学习到更多的知识和技术!标题:K倍区间给定一个长度为 N的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj之和是 K的倍数,我们就称这个区间 [i,j]是 K倍区间。你能求出数列中总共有多少个 K倍区间吗?输入格式第一行包含两个整数 N和 K以下 N行每行包含一…

输出样例:

其中有不足或者改进的地方,还希望小伙伴留言提出,一起学习!

感兴趣的小伙伴可以关注专栏!

灰小猿陪你一起进步!

欢迎大家关注我的专栏“每日蓝桥”,该专栏的主要作用是和大家分享近几年蓝桥杯省赛及决赛等真题,解析其中存在的算法思想、数据结构等内容,帮助大家学习到更多的知识和技术!

标题:K倍区间

给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K倍区间。

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

输入格式

第一行包含两个整数 NK

以下 N行每行包含一个整数 Ai

输出格式

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

数据范围

1≤N,K≤100000

,1≤Ai≤100000

【资源约定】

峰值内存消耗(含虚拟机) < 256M

CPU消耗< 1000ms

请严格按要求输出,不要画蛇添足地打印类似: " 请您输人..”的多余内容.

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码.

不要使用package语句。不要使用jdk1.7及以上版本的特性.

主类的名字必须是: Main, 否则按无效代码处理.

提交程序时,注意选择所期望的语言类型和编译器类型.

解题思路:

对于本题在求解的时候可能最先想到的是使用暴力枚举的方法,将每一个区间都列出来进行判断,但是这样的方法虽然可行,但是只针对于小量的数据,对于像题中所给的范围来说,就已经远远的超出了运行时间,所以我们应该想办法在原来暴力枚举代码的基础上对代码进行优化。

所采用的方法就是前缀和的方式,我们可以在输入数据的时候就求出每输入一个数据得到的数据的总和,并且把该总数记录下来,之后我们可以判断总数与K的余数是否为0。如果是,则说明该从第一个数到该数的总数和是k的倍数;同时如果余数不是0,那么我们其实也可以推出来余数相同的两个区间之间的差也一定是K的倍数。这句话要注意理解。利用这一特性,我们就可以求出符合要求的区间数。

答案源码:

package 一七年省赛真题;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Year2017_Bt10 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int K = scanner.nextInt();
int [] arr = new int[N+1];
int [] sumArr = new int[N+1];
sumArr[0] = 0;
int ans=0;
Map<Integer, Integer> maps = new HashMap<Integer, Integer>();
maps.put(0, 1);
for (int i = 1; i <= N; i++) {
arr[i] = scanner.nextInt();//将输入的数据存放到数组中
sumArr[i] = (arr[i] + sumArr[i-1])%K;	//计算前i个数的和与K的mod
//判断前i个数的和与k的余是否存储在map中
if (maps.get(sumArr[i])==null) {
maps.put(sumArr[i],1);
}else {
maps.put(sumArr[i], maps.get(sumArr[i])+1);
}
}
for (int i = 0; i <= K-1; i++) {
if (maps.get(i)!=null) {
//				System.out.println(i + " " + maps.get(i));
ans+=maps.get(i)*(maps.get(i)-1)/2;
}
}
System.out.println(ans);
}
}

你好呀,我是灰小猿,一个超会写bug的程序猿!

本文转自 https://blog.csdn.net/weixin_44985880/article/details/115419964

腾讯云618
avatar
2w 字长文爆肝 JVM 经典面试题!太顶了! java

2w 字长文爆肝 JVM 经典面试题!太顶了!

如果你是中高级程序员,那我相信你一定被面试官问过JVM。下次再被问到JVM,你直接把老周的这篇文章丢给他吧!话不多说,让我们直接进入主题吧。JVM内存结构,常见异常,调优参数,调优...
JAVA初窥-DAY08 java

JAVA初窥-DAY08

JAVA初窥-DAY08面向过程与面向对象实例化及调用方法和成员变量面向过程与面向对象面向过程:注重的是某件事情过程中的每一个步骤的实现。面向对象:把面向过程中的每一个步骤交给一个...
腾讯云618
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: