PTT數位生活區 / C_and_CPP (C/C++)

[問題] ACM679寫法的問題

看板C_and_CPP (C/C++)作者 (栗子)時間14年前 (2012/05/02 11:30), 編輯推噓4(4推 0噓 7→)
留言11則, 2人參與, 最新討論串1/3 (看更多)
首先這是問題的網頁 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
推
05/02 12:04, , 1F
這題讓我想到霍夫曼編碼 ((痛苦的回憶
05/02 12:04, 1F
→
05/02 12:06, , 2F
可以試試看用畫圖的喔~ 就可以觀察到其實第I顆球
05/02 12:06, 2F
→
05/02 12:06, , 3F
所經過的路徑都是重複的 000 ~ 111 這樣
05/02 12:06, 3F
推
05/02 12:11, , 4F
所以第I顆球整個rotate以後再加上位元數+1的位置補上1
05/02 12:11, 4F
→
05/02 12:11, , 5F
就是他的位置了 0.0 這樣子嘛? 不確定XD
05/02 12:11, 5F
→
05/02 12:12, , 6F
阿 樓樓上那句敘述忘了說"I要-1" = =" 抱歉
05/02 12:12, 6F
推
05/02 12:20, , 7F
那個更看不懂的Code也是一樣的處理方式 不過他是直接Y
05/02 12:20, 7F
→
05/02 12:21, , 8F
對位元進行操控，所以比較難理解，Trace一下就懂囉~
05/02 12:21, 8F
→
05/02 12:21, , 9F
以上小弟個人見解= =" 請純參考勿信以為真= ="
05/02 12:21, 9F
推
05/02 12:29, , 10F
不過為什麼我trace的結果是錯的 XD.......OTZ
05/02 12:29, 10F
→
05/03 07:35, , 11F
位元反轉是因為羅列結果查出規則的。不用太執著。
05/03 07:35, 11F
‣ 更多 Biboy 的文章
文章代碼(AID): #1FeAfJ7s (C_and_CPP)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共3篇)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 Biboy 的文章
文章代碼(AID): #1FeAfJ7s (C_and_CPP)