#26480: TLE 請進


ck1090758@gl.ck.tp.edu.tw (peienwu)

School : 臺北市立建國高級中學
ID : 128355
IP address : [27.247.166.72]
Last Login :
2021-10-16 11:22:04
a249. 00679 - Dropping Balls -- UVa679 | From: [111.241.70.33] | Post Date : 2021-08-09 15:18

這題可以從二進位的編碼方式思考。如果直接以遞迴去模擬球掉落的情況,會TLE

因此如果要過的話必須換一種方法

考慮I = 7的情況,這裏要改用0-base,把I減1,轉換成二進制 I = 110(2)代表說

由低的bit往高的bit,如果是1就往由子樹走,如果是0就往左子樹

因此要左一步、右一步、右一步,如果還沒有走到葉節點就繼續都往左子樹走直到葉節點

大概就是這種概念(之所以會對是因為每一個節點被走到的頻率剛好可以對應到二進位後的每一個bit)

 
ZeroJudge Forum