作者Henry658 (adreN.)
看板Prob_Solve
標題[問題] UVA 11205 wa問題
時間Sun May 13 16:11:49 2018
各位大大好
這是題目
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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1526199113.A.CB7.html
1F：→ pttworld: 其實這題是練習位元運算的 05/13 21:12
2F：→ Henry658: 小弟不才 05/14 00:43
3F：→ Henry658: 目前問題解決剩TLE問題 05/14 00:44
5F：→ Henry658: 改用位元運算 05/15 00:58
6F：→ pttworld: 建議把q依照有幾個bit分成15群放在二維vector裡 05/15 07:26
7F：→ pttworld: 如此這題不需遞迴。這題的正解速度約20ms。 05/15 07:27
8F：→ pttworld: 產生q的方式預先迴圈從1跑到32767，計算bit分群 05/15 07:29
9F：→ pttworld: 這題採取廣度優先的算法，p=7先和1bit所有可能運算 05/15 07:40
10F：→ pttworld: 找到1個成立後往2bit做，在3bit發現都不成立停止 05/15 07:41
11F：→ pttworld: 答案是7-2=5，p=7不用運算大於等於128的可能 05/15 07:43
12F：→ Henry658: 謝謝大家 我解出來了 05/15 22:21