PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] UVA 11205 wa問題

看板Prob_Solve (計算數學 Problem Solving)作者 (adreN.)時間6年前 (2018/05/13 16:11), 編輯推噓0(0推 0噓 12→)
留言12則, 2人參與, 6年前最新討論串1/1
各位大大好 這是題目 https://odzkskevi.qnssl.com/024da4f2cba0326ef6e5c067b5ab4d88?v=1525697680 題目說就是有幾個數字與幾個顯示的位元數 看根據題目給的測資可以從中找出最少的需要的位元數來表達數字 我的作法是分別依序省略其中之一的位元數 檢查有沒有重複 如果沒有了話再做遞迴下去 直到所有可能都沒舉完 暴力法的運算符合時間的需求 這我的code http://codepad.org/sBe5PG5E 題目已經用過ubebug的測資測過了udebug沒有找出問題 但是送上virtual judge 會WA 想請教各位 是哪裡有問題還是整個演算法或是output錯誤 謝謝各位 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.28.224 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1526199113.A.CB7.html
→
05/13 21:12, 6年前 , 1F
其實這題是練習位元運算的
05/13 21:12, 1F
→
05/14 00:43, 6年前 , 2F
小弟不才
05/14 00:43, 2F
→
05/14 00:44, 6年前 , 3F
目前問題解決剩TLE問題
05/14 00:44, 3F
→
05/15 00:58, 6年前 , 4F
05/15 00:58, 4F
→
05/15 00:58, 6年前 , 5F
改用位元運算
05/15 00:58, 5F
→
05/15 07:26, 6年前 , 6F
建議把q依照有幾個bit分成15群放在二維vector裡
05/15 07:26, 6F
→
05/15 07:27, 6年前 , 7F
如此這題不需遞迴。這題的正解速度約20ms。
05/15 07:27, 7F
→
05/15 07:29, 6年前 , 8F
產生q的方式預先迴圈從1跑到32767，計算bit分群
05/15 07:29, 8F
→
05/15 07:40, 6年前 , 9F
這題採取廣度優先的算法，p=7先和1bit所有可能運算
05/15 07:40, 9F
→
05/15 07:41, 6年前 , 10F
找到1個成立後往2bit做，在3bit發現都不成立停止
05/15 07:41, 10F
→
05/15 07:43, 6年前 , 11F
答案是7-2=5，p=7不用運算大於等於128的可能
05/15 07:43, 11F
→
05/15 22:21, 6年前 , 12F
謝謝大家 我解出來了
05/15 22:21, 12F
‣ 更多 Henry658 的文章
文章代碼(AID): #1Qz_D9ot (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 Henry658 的文章
文章代碼(AID): #1Qz_D9ot (Prob_Solve)