2017.4.7

莫名提前的考前综合征让我无法入眠。

我什么都会一点,也可以叫什么都不会,因为总担心自己不会别人会的东西。

这几天……先是在UESTC校赛里被七中大爷和UESTC的三位大爷粉碎,然后又在水水的省选集训里昏昏欲睡,过着醉生梦死的生活。

不知道后天我将怎么面对结果。抑或是成功的喜悦,还是退役后如释重负呢?

我希望是前者。

与其苟延残喘,不如纵情燃烧。

就算再不自信,我也只能尽我全力说着:

SCOI2017,我准备好了。

AK is yzh.






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