[理工] 110 NTU DS jacksoncsie PTT批踢踢實業坊

作者: jacksoncsie (資工肥宅) 2021-09-22 21:05:52

問這題感恩
https://i.imgur.com/D6aHpNn.png

作者: lienasd126 (迷途の獅子) 2021-09-30 16:23:00

可以問一下下方yi的意義是什麼？

作者: BusterButter (奶油巴斯特) 2021-09-23 00:56:00

這種reduction的題目建議自己去看看proof自己推導一遍，不過我可以告訴你t的most significant digit是3（因為vertex cover size = 3) 其他 digit都是2，所以算出來應該是3754

作者: jacksoncsie (資工肥宅) 2021-09-23 01:34:00

好的感謝提供建議我自己再看一下

作者: joywilliamjo (joywilliamjoy) 2021-09-23 07:47:00

答案是不是也可以是3697呢？

作者: alex391a (麥基) 2021-09-24 16:49:00

這題跟3sat reduce到 subset sum很像簡單來說就是要選三個點然後為了cover所有edge 所以要選到每個至少要1（最多2）所以下面就是為了讓1的那些可以加到2所以答案是322222（四進位）四進位是因為這題用四進位不會進位所以就不用那麼大的數字

作者: jacksoncsie (資工肥宅) 2021-09-24 21:34:00

感恩alex大我戰友有找到類似題目而且解答也差不多不過差一項2 感覺是跟 Graph 的 degree 有關

繼續閱讀