UOJ Logo immortalCO的博客

博客

NOIP2018 D2T3 题解 + 关于动态 DP 等科技的一些总结

2018-11-12 11:29:08 By immortalCO

利益无关:猫锟不是本题的命题猫。

算法一

最小权覆盖集 = 全集 - 最大权独立集

强制取点、不取点可以使用把权值改成正无穷或负无穷实现。

接下来就是经典的“动态最大权独立集”了,这题的题解在我之前博客有,洛谷上也可以提交。

$O(n\log n)$。

算法二

考虑修改的两个点 $a,b$ 构成这条链。

可以把操作看作是:先在这条链伸出去的每棵子树上 DP,最后再在这条链上 DP。

伸出去的子树以及链的中间的点和修改无关,因而可以整合起来高效处理,因为它们的转移是不受影响的;但是 $a$ 和 $b$ 的转移是受影响的,需要单独处理。

因此可以先预处理出每个子树的 DP 值,然后用倍增或树剖维护“从一个点往上按照通用规则 DP 到另一个点的结果”,这样只需要特殊处理修改的点,其他地方只需要直接倍增。

$O(n\log n)$。

算法三

如果不想写倍增,也可以写这样一个算法:把所有的询问放在一起处理。

也就是说,由于每条链中间的 DP 转移全部相同,因而我们可以批量地对所有需要进行这一转移的 DP 进行转移,从而加快速度。

这个算法虽然实现较容易,但理解较为困难,因而不再叙述。

$O(n\log n)$。

总结

本题的三个做法对应着动态 DP、虚树计算和整体 DP 的思想,体现了三个算法(在一定条件下)的等价性。

动态 DP $\Rightarrow$ 虚树计算:动态维护被修改的点构成的虚树(可能会增加复杂度);

虚树计算 $\Rightarrow$ 动态 DP:一个一个加入虚树中的点;

动态 DP $\Rightarrow$ 整体 DP:每个修改看作时间的区间,用线段树批量应用修改(不一定可行);

整体 DP $\Rightarrow$ 动态 DP:一个一个询问进行处理,依次加入对称差(可能会增加复杂度);

虚树计算 $\Rightarrow$ 整体 DP:按询问分组批量进行;

整体 DP $\Rightarrow$ 虚树计算:通过 整体 DP $\Rightarrow$ 动态 DP $\Rightarrow$ 虚树计算 进行转化(不一定可行)。

可以看出,动态 DP 和整体 DP 具有很强的适用面,都有各自才能解决的问题;而虚树计算的能力则是最弱的,常常可以等复杂度地转化为另外两者(一些例外是需要在虚树上点分治的问题)。

评论

zx2003
可不可以toptree上倍增然后O((n+q)loglogn) @negiizhao
zx2003
话说树链矩阵积能不能用tarjanLCA类似物优化到O(n alpha(n))?感觉有结合律的信息不太好按秩合并啊。
duliu
毒瘤NOIP2018 D2T3 题目 + 关于卡常动态 DP 等sxbk科技的一些膜拜
duliu
毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO毒瘤immortalCO

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。