Codeforces Rounds
做出 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。
图论
这部分直接爬了。
杂项
一年前的坑,其实是比较简单的维护二次函数和的方法。
但是还是卡了几下。