作者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/cn.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