首页 > 奇奇怪怪的魔法阵
开通博客写题解
头像 issue是云哥的小迷×呀
发表于 2021-10-18 10:10:50
Link 我们要求fT=∑S∈T[S为独立集]f_T=\sum\limits_{S\in T}[S为独立集]fT​=S∈T∑​[S为独立集] 考虑集合TTT的最低位二进制位代表的集合是yyy(这个点设为uuu),其他二进制位代表的是xxx 那么T=x+yT=x+yT=x+y 显然,若SSS集合中不包 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 sigland
发表于 2021-10-20 22:18:48
出题人的题解很简洁，直接dp（S）表示S集合内有多少个独立集子集，然后考察S中随便一个元素i的情况，由之前状态转移过来，复杂度（2^n） 但是事实上这道题可以通过折半枚举的方法优化到(n * 2^(n/2))。 首先，按照题目中的说法一个一个求每个集合T内独立子集个数肯定不能找到更快的算法，因为此时 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”