2017.3.27

未来迷人绚烂总在向我召唤
哪怕只有痛苦作伴也要勇往直前
我想在那最蓝的大海扬帆
绝不管自己能不能回还
失败后郁郁寡欢
那是懦夫的表现
只要一息尚存请握紧双拳
在天色破晓之前
我们要更加勇敢
等待日出时最耀眼的瞬间

Countdown: 11 Days.


树分治-点分治

看到akb在冬令营就切了好多点分治就好慌啊qaq,然后机房里也有一堆人写点分治qaq,然后我就被点分治虐了啊qaq……

树上的点分治是一种针对树上路径统计的问题的算法,通过找到重心使得子问题规模快速下降,再将所有子问题答案合并起来,通常能够将\(O(n ^ 2)\)规模的问题优化为\(O(n \log n)\)或者\(O(n \log ^ 2 n)\)。

先看一道题:
给定一颗\(n \leq 10 ^ 5\)个节点的带权无根树,设\((i, j)\)之间的简单路径边数为\(dis(i, j)\),求所有满足\(dis(i, j) \leq K\)且\(i \lt j\)的数对\((i, j)\)的数量。(CWOJ1201

暴力做法显然,从每个节点开始dfs (bfs是等价的,后文dfs均可以用bfs解决),记录答案即可。时间复杂度为\(O(n ^ 2)\)

但是这样太慢了!我们想要更快的做法。

(更多…)




斜率优化DP – Solutions

斜率优化是将方程看起来非常可推的dp从\( O(n^2) \)优化至\( O(n) \)的优秀方法,这种优化是基于决策单调性的……………………

一句话:都是套路。

关于斜率优化的文章很多,而且我数学贼差QAQ(主要是懒),就直接指向一篇本校神犇HenryPigLi的斜率优化DP,虽然他推得有点乱但是还算能看。
然而他的文章还有一个好,就是底下给的题比其他blog都多,于是我觉得应该把solution发出来。 (更多…)




ˆ Back To Top