[問題] ACM679寫法的問題

[Biboy (栗子)]

首先這是問題的網頁
http://luckycat.kshs.kh.edu.tw/homework/q679.htm

剛開始我是用直觀的方式去寫

每一筆輸入就創一個tree去跑

然後就被UVA大量的測資弄成TLE...

後來有找到使用位元移動方法來寫

主要的觀念是將I轉成二位元，然後將高低為原反過來

根據這觀念寫出的的code已經AC了 http://pastie.org/3846836

雖然知道作法，但還是不太懂要將位元反轉的原理...


在找尋說明的時候又發現一個更精簡的code http://pastie.org/3846831

但是這個code就真的看不懂了... 尤其是24行為什麼要這要做??

雖然寫出來了，但是不懂原理就覺得好像沒有寫出來一樣...

有寫過這題的前輩可以解釋一下這題的做法的原理嗎? 謝謝!


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.111.129.79
推 lovesnake:這題讓我想到霍夫曼編碼 ((痛苦的回憶
→ lovesnake:可以試試看用畫圖的喔~ 就可以觀察到其實第I顆球
→ lovesnake:所經過的路徑都是重複的 000 ~ 111 這樣
推 lovesnake:所以第I顆球整個rotate以後再加上位元數+1的位置補上1
→ lovesnake:就是他的位置了 0.0  這樣子嘛? 不確定XD
→ lovesnake:阿 樓樓上那句敘述忘了說"I要-1" = ="  抱歉
推 lovesnake:那個更看不懂的Code也是一樣的處理方式 不過他是直接Y
→ lovesnake:對位元進行操控，所以比較難理解，Trace一下就懂囉~
→ lovesnake:以上小弟個人見解= =" 請純參考勿信以為真= ="
推 lovesnake:不過為什麼我trace的結果是錯的 XD.......OTZ
→ bleed1979:位元反轉是因為羅列結果查出規則的。不用太執著。