本文主要是介绍蓝桥杯历年真题省赛java b组 2017年第八届 k倍区间,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目
k倍区间
给定一个长度为N的数列,A1, A2, ... AN,如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗?
输入
-----
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出
-----
输出一个整数,代表K倍区间的数目。
例如,
输入:
5 2
1
2
3
4
5
程序应该输出:
6
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 2000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是:Main,否则按无效代码处理。
二、代码
package lan2017;import java.util.Scanner;public class Ik倍区间 {/*k倍区间给定一个长度为N的数列,A1, A2, ... AN,如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入
-----
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000) 输出
-----
输出一个整数,代表K倍区间的数目。 例如,
输入:
5 2
1
2
3
4
5 程序应该输出:
6资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 2000ms请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是:Main,否则按无效代码处理。*/
// 给定一个长度为n的子序列,我们用数组来存i位置的前缀和,则两个位置相减就可以得到
//某一段子序列的的和,我们再来看是否是k的倍数,此时我们要遍历所有可能的两个位置,看是否是k的倍数public static void main(String[] args) {//1.键盘录入n和kScanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();//2.定义数组算前缀和int[] arr = new int[n+1];//长度为n+1,即最后一个位置存的是之前所有数的前缀和//存储子序列for(int i = 1; i <= n; i++) {arr[i] = arr[i-1] + sc.nextInt();}//3.遍历所有子区间int count = 0;for(int i = 1; i <= n; i++) { //外层循环遍历所有的可能的子区间的长度for(int j = 0; j+i <= n; j++) { // 内层循环列举到n-1,我们可以理解为当遍历到第j个元素时,当前的j位置加上子区间的长度不超过nif((arr[j+1] - arr[j]) % k == 0) {count ++;}}}System.out.println(count);}
}
三、反思
采用的是暴力枚举的方法,将符合条件的进行计数,将整数的前缀和存储在一个一个数组里,下标从1~n(第一个元素的前缀和就是本身,所以从1开始),
两层for循环,外层遍历所有的区间长度,从1~n,内层循环列举每一个元素,若 区间的右边对应位置的元素 减 区间的对应左边的元素 被k整除,计数器+1
这篇关于蓝桥杯历年真题省赛java b组 2017年第八届 k倍区间的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!