你好呀，我是灰小猿，一個超會寫bug的程式猿！
歡迎大家關注我的專欄“每日藍橋”，該專欄的主要作用是和大家分享近幾年藍橋杯省賽及決賽等真題，決議其中存在的演算法思想、資料結構等內容，幫助大家學習到更多的知識和技術！
標題：K倍區間
給定一個長度為 N 的數列，A1,A2,…AN，如果其中一段連續的子序列 Ai,Ai+1,…Aj 之和是 K 的倍數，我們就稱這個區間 [i,j] 是 K倍區間，
你能求出數列中總共有多少個 K倍區間嗎？
輸入格式
第一行包含兩個整數 N和 K
以下 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); } }
輸出樣例：
其中有不足或者改進的地方，還希望小伙伴留言提出，一起學習！
感興趣的小伙伴可以關注專欄！
灰小猿陪你一起進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/272874.html
標籤：java