Codeforces Rounds

Codeforces Round #680 Div. 2

做出 ABC,D 是结论,想不到。

DP

这部分重在思维。

DP 题,目前质量的维度无法表示,于是反过来,乘上系数即可。

看上去 DP,实际上模拟退火调调参就可以过。

区间 DP,想了半天 $\mathcal O(n^3)$ 枚举第一个数线性 DP,没发现这样就是枚举了所有区间...

关于联通块的 DP,想不到。题解

序列 DP 再套一个背包。其中序列 DP 部分有劣 $\mathcal O(nm^2t)$ 做法可吸氧过,优做法 $\mathcal O(nmt)$,利用了贡献可分离的性质。

数位 DP 模板。感觉挺套咯。

DS

这部分重在所有会的都复习一遍。

树上和 DFS 序上可持久化 01trie 求异或 kth(最大值)模板。

线段树板子,但是不知道复杂度有没有保证。

线段树板子,复习用。

正解树状数组,但是没想到,于是当 Splay 复习了。但是不 Splay 也能过

线段树合并裸题。但是可并堆是正解,被吊打。

线段树合并,但是合并时要算逆序对。自己做出来,感动。题解

三维偏序板子,复习 CDQ 分治。

左偏树。接近板子,和上面 P1552 相似。

数论

这部分补充还不会的基础算法。

不知道多少倍经验题。莫反初步复习。

没有高深知识。题解

莫反套路题。题解 但是完全自己做出来,挺感动。

顺便复习了 exgcd。

得到分块 + 卷积的式子,但是卷积是有一定限制的。

因此离线从小到大询问,每次树状数组上插入算卷积。

感觉挺神仙的。而且筛 $\sigma$ 都不怎么会。题解

数数/期望

这部分重在思维。

非常基础的数数式子,但是高精... 屑 出题人 屑

基础计数题。

Burnside 引理,套一个简单的 DP。

图论

这部分直接爬了。

杂项

一年前的坑,其实是比较简单的维护二次函数和的方法。

但是还是卡了几下。