110 NTU DS

看板Grad-ProbAsk作者 (Nov)時間2年前 (2021/09/22 21:05), 2年前編輯推噓2(2推 0噓 13→)
留言15則, 4人參與, 2年前最新討論串1/1
問這題 感恩 https://i.imgur.com/D6aHpNn.png
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.124.183.43 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1632315954.A.BD8.html ※ 編輯: jacksoncsie (140.124.183.43 臺灣), 09/22/2021 21:10:13 ※ 編輯: jacksoncsie (118.160.145.97 臺灣), 09/22/2021 23:55:54 ※ 編輯: jacksoncsie (118.160.145.97 臺灣), 09/22/2021 23:56:20
→
09/23 00:56, 2年前 , 1F
這種reduction的題目建議自己去看看proof自己推導一
09/23 00:56, 1F
→
09/23 00:56, 2年前 , 2F
遍，不過我可以告訴你t的most significant digit是3
09/23 00:56, 2F
→
09/23 00:56, 2年前 , 3F
（因為vertex cover size = 3) 其他 digit都是2，所
09/23 00:56, 3F
→
09/23 00:56, 2年前 , 4F
以算出來應該是3754
09/23 00:56, 4F
→
09/23 01:34, 2年前 , 5F
好的 感謝提供建議 我自己再看一下
09/23 01:34, 5F
推
09/23 07:47, 2年前 , 6F
答案是不是也可以是3697呢？
09/23 07:47, 6F
推
09/24 16:49, 2年前 , 7F
這題跟3sat reduce到 subset sum很像
09/24 16:49, 7F
→
09/24 16:49, 2年前 , 8F
簡單來說就是要選三個點
09/24 16:49, 8F
→
09/24 16:49, 2年前 , 9F
然後為了cover所有edge 所以要選到每個至少要1（最多2）
09/24 16:49, 9F
→
09/24 16:49, 2年前 , 10F
所以下面就是為了讓1的那些可以加到2
09/24 16:49, 10F
→
09/24 16:49, 2年前 , 11F
所以答案是322222（四進位）
09/24 16:49, 11F
→
09/24 16:49, 2年前 , 12F
四進位是因為這題用四進位不會進位所以就不用那麼大的數
09/24 16:49, 12F
→
09/24 16:49, 2年前 , 13F
字
09/24 16:49, 13F
→
09/24 21:34, 2年前 , 14F
感恩alex大 我戰友有找到類似題目 而且解答也差不多
09/24 21:34, 14F
→
09/24 21:34, 2年前 , 15F
不過差一項2 感覺是跟 Graph 的 degree 有關
09/24 21:34, 15F
※ 編輯: jacksoncsie (114.37.85.220 臺灣), 09/24/2021 21:35:46 ※ 編輯: jacksoncsie (114.37.85.220 臺灣), 09/24/2021 21:36:38
‣ 更多 jacksoncsie 的文章
文章代碼(AID): #1XIoeolO (Grad-ProbAsk)