作者jacksoncsie (Nov)
看板Grad-ProbAsk
標題[理工] 110 NTU DS
時間Wed Sep 22 21:05:52 2021
問這題 感恩
https://i.imgur.com/D6aHpNn.png
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.124.183.43 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=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
1F：→ BusterButter: 這種reduction的題目建議自己去看看proof自己推導一 09/23 00:56
2F：→ BusterButter: 遍，不過我可以告訴你t的most significant digit是3 09/23 00:56
3F：→ BusterButter: （因為vertex cover size = 3) 其他 digit都是2，所 09/23 00:56
4F：→ BusterButter: 以算出來應該是3754 09/23 00:56
5F：→ jacksoncsie: 好的 感謝提供建議 我自己再看一下 09/23 01:34
6F：推 joywilliamjo: 答案是不是也可以是3697呢？ 09/23 07:47
7F：推 alex391a: 這題跟3sat reduce到 subset sum很像 09/24 16:49
8F：→ alex391a: 簡單來說就是要選三個點 09/24 16:49
9F：→ alex391a: 然後為了cover所有edge 所以要選到每個至少要1（最多2） 09/24 16:49
10F：→ alex391a: 所以下面就是為了讓1的那些可以加到2 09/24 16:49
11F：→ alex391a: 所以答案是322222（四進位） 09/24 16:49
12F：→ alex391a: 四進位是因為這題用四進位不會進位所以就不用那麼大的數 09/24 16:49
13F：→ alex391a: 字 09/24 16:49
14F：→ jacksoncsie: 感恩alex大 我戰友有找到類似題目 而且解答也差不多 09/24 21:34
15F：→ jacksoncsie: 不過差一項2 感覺是跟 Graph 的 degree 有關 09/24 21:34
※ 編輯: jacksoncsie (114.37.85.220 臺灣), 09/24/2021 21:35:46
※ 編輯: jacksoncsie (114.37.85.220 臺灣), 09/24/2021 21:36:38
16F：推 lienasd126: 可以問一下下方yi的意義是什麼？ 09/30 16:23