K倍區間
題目來源：第八屆藍橋杯省賽Java/C++大學B組
時間限制：\(1000ms\) 記憶體限制：\(64mb\)
題目描述
給定一個長度為 \(N\) 的數列，\(A_1,A_2,…,A_N\)，如果其中一段連續的子序列 \(A_i,A_{i+1},…,A_j\) 之和是 \(K\) 的倍數，我們就稱這個區間 \([i,j]\) 是 \(K\) 倍區間，
你能求出數列中總共有多少個 \(K\) 倍區間嗎？
輸入格式
第一行包含兩個整數 \(N\) 和 \(K\) ，
以下 \(N\) 行每行包含一個整數 \(A_i\) ，
輸出格式
輸出一個整數，代表 \(K\) 倍區間的數目，
資料范圍
\(1 ≤ N,K ≤ 100000\) ,
\(1 ≤ Ai ≤ 100000\)
樣例輸入
5 2
1
2
3
4
5
樣例輸出
6
解題思路
一個經典的前綴和題目
在讀入 \(A_i\) 的時候直接存入前 \(i\) 項和，
求區間 \([i,j]\) 的和的時候，直接用前 \(j\) 項和 \(S_j\) 減去前 \(i\) 項和 \(S_i\) 就得到了，然后對其模 \(K\)，判斷是否為 \(0\) 即可，
直接做會超時，
優化：
如果 \((S_i - S_j) \%k = 0\) ，那么 \(S_i\%k\) 和 \(S_j\%k\) 都等于 \(0\) ，
問題就轉化為了，列舉終點坐標 \(x\) ，求有多少個數模\(k\)的余數是\(S_x\%k\)，即查找某一個數出現了多少次，
開一個 \(cnt\) 陣列， \(cnt[x]\) 表示，余數為 \(x\) 的數的個數，
即求的就是 \(cnt[S_x\%k]\) ，每次算完就讓 \(cnt[S_x\%k]++\) ，
解題代碼-Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int k = input.nextInt();
long[] a = new long[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + input.nextInt();
}
input.close();
long ans = 0;
int[] cnt = new int[n+1];
cnt[0]++;
for (int i = 1; i <= n; i++) {
ans += cnt[(int) (a[i]%k)];
cnt[(int) (a[i]%k)]++;
}
System.out.println(ans);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/255505.html
標籤：其他
上一篇：Zabbix 5.x的Template Module ICMP Ping淺析
下一篇：Lua編程