切換
舊版
前往
大廳
主題

初篇日誌 & ZeroJudge線上程式解題系統 - d923之解題心得

Not In My Back Yard | 2018-07-24 19:43:17 | 巴幣 12 | 人氣 602


這篇日誌是本人的第一篇,打算把之後解題的心得通通放在巴哈上面(但不溯及既往XD)。

2020 / 08 / 07 更新:野心變得更大了,現在的目標是想要建立一個完整的 Zerojudge 題解(過於基本的題目,如 a001 不會出現在這裡)。不過能力有限,不知能做到哪。

--------------------------------分隔線--------------------------------

d923: 規律

這題我有點進去瀏覽好幾次,可是看到一看到表格便一而再,再而三地打退堂鼓。

今天終於有了決心,來完成這個題目。

上方是題目所給的表格,要求規律。

題目所求為:給你兩個正整數R、C,求第R列第C行的值(R、C ≦ 2 ^ 30,且左上角座標為(1, 1))

思維:我們先將表格分成左上、左下、右上、右下四大區塊,如下圖(方便觀察)。


之後,將圖分成如下16個區域,並賦予編號。


著眼於棕色編號,將圖切成新的四等分,一樣給予編號。


由此可以觀察出可以藉由遞迴的方式,將值縮減到我們要的答案。

拿上圖為例子,我們想知道第4列第7行(7,4)是什麼數字。我們知道它的值一定介於1~64之間(因為(7, 4)介於(1,1)跟(8,8),所以最大值是8 * 8 = 64)。

然後取(1,1)和(8,8)中點(4,4)去比較X座標和Y座標,可以發現它位於黃色3的區域裡,值的範圍就縮減為33~48(1~64分成四等分,這裡是第3個等分(右上)。

對於黃色3區域而言,左上座標(5,1)、右下座標(8,4),取中點(6,2)再跟(7,4)做比對,得知它位於棕色10的區域(黃色3的右下),值域為37~40(分四等分,這裡是第二等分)。

同理,得知它在棕色10的左下,值域縮減為40~40,便是我們要的答案了。



此次分享到此為止,如有任何更加簡潔的想法,也煩請各位大大們可以提出來討論。

創作回應

更多創作