#19403: 思路


610067@mail2.chshs.ntpc.edu.tw (CHISC_Ray)

學校 : 新北市立中和高級中學
編號 : 96797
來源 : [220.133.8.78]
最後登入時間 :
2019-09-18 21:21:39
c521. 6. 顯微探測 -- 2017高雄市資訊學科能力複賽 | From: [220.133.8.78] | 發表日期 : 2019-09-29 02:27

相信各位看到題目後,應該可以畫出這樣一張圖:

(k = 3, n = 20)
A + B + C + D
A + B + C + D + E
A + B + C + D + E + F
A + B + C + D + E + F + G
B + C + D + E + F + G + H
C + D + E + F + G + H + I
D + E + F + G + H + I + J
E + F + G + H + I + J + K
F + G + H + I + J + K + L
G + H + I + J + K + L + M
H + I + J + K + L + M + N
I + J + K + L + M + N + O
J + K + L + M + N + O + P
K + L + M + N + O + P + Q
L + M + N + O + P + Q
M + N + O + P + Q
N + O + P + Q

(上圖每一行的總和就是一個輸入的數字,不難理解吧?)

並且覺得:我應該可以把它消掉求解吧?

然而否,事實上我們只需要用搜尋的就可以了

不妨試試看從第1行開始看

第零行結尾是E,所以我們從開頭是F的開始繼續。開頭是F的這行結尾是L,開頭是M的結尾恰好就是最後了,因此只要把他們全部加起來就是解答了。
雖然可以用公式解到底是哪行,但是反正這題k到4000,N到200000,複雜度就是 O(K * N / K)  (N/K是把每個項目總合加起來的時間,K是把k從0帶到K+1),所以看起來搜索就可以過了,就不用花心思算數學了(會掉頭髮)

假代碼如下


i 從零帶到 K+1 (含)
總和 = 0
x = i
若 行代號 < N - K - 1 重複執行:
總和 = 總和 + 第x行
x += 2 * K + 1 // 每一固定行的寬度

若 (x == N-1) 或 ((N - K - 1) - x >= 0):
總和 += 第x行
印出 總和
結束程序

// 發生錯誤,程序失敗

 

 
ZeroJudge Forum