a074. 校長室之謎 - 旦旦解題農場

內容

傳說想要進入校長室需要解開一個鎖，鎖上面有一個數列，已知密碼是該數列某段連續的區間且其總和剛好等於$k$，

但是總和等於$k$的區間可能不只有一個，而且每天只能輸入密碼一次，想請你幫幫忙找到所有區間和等於$k$的數量，

幫助大家知道最多要幾天才可以把鎖打開。

以範測為例，數列為[3 6 1 7 2]且$k$=10，有可能為密碼的序列有[3 6 1]與[1 7 2]兩種。

輸入說明

第一行有兩個正整數$n,k$

第二行有$n$個正整數$a_i$為鎖上面的序列。

$1\le n\le 10^7$ , $1\le k\le 10^9$ , $1\le a_i \le 10^6$

輸出說明

輸出一個正整數，代表最多要幾天才可以把鎖打開

範例輸入

5 10
3 6 1 7 2

範例輸出

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (8%): 1.0s , <1M
公開測資點#1 (8%): 1.0s , <1M
公開測資點#2 (8%): 1.0s , <1M
公開測資點#3 (8%): 1.0s , <1M
公開測資點#4 (8%): 1.0s , <1M
公開測資點#5 (8%): 1.0s , <10M
公開測資點#6 (8%): 1.0s , <10M
公開測資點#7 (8%): 1.0s , >50M
公開測資點#8 (9%): 1.0s , >50M
公開測資點#9 (9%): 1.0s , >50M
公開測資點#10 (9%): 1.0s , >50M
公開測資點#11 (9%): 1.0s , >50M

提示：

演算法筆記AlgorithmDesign

請使用IO優化(cin.tie(NULL),ios::sync_with_stdio(false);)否則會得到TLE

為了卡掉$O(nlgn)$的解法不得已只好卡記憶體，因此請勿開long long int陣列(int陣列足夠解這題)

標籤:

出處:

[管理者：

giver (垃圾)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」