[理工] 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 有关

继续阅读