走夜路

[NOI2010]超级钢琴题解

很妙的一道题，用到了 贪心 + 堆 + ST表

先考虑 $k=1$ 的方法。

luogu4755Beautiful_Pair

标签 ：分治 + RMQ + 树状数组 + 启发式

标签

数位dp + 性质

[SHOI2008]仙人掌图II

标签

dp + 树形dp + 仙人掌 + 单调队列

[HEOI2013]SAO

标签

拓扑排序 + 计数 + dp + 树形dp

变进制数

定义

所谓变进制数，就是每一位进制不一定相同的数，形式化的来讲：
对于一个变进制 $A =\{a_1,a_2, a_3 ... a_n\}$ , $a_i$ 表示第 $i$ 位的一个 $1$ 相当于第 $i-1$ 位的一个 $a_i$ .特别的, $a_1 = 1$

前言

这次考试是 $dp$ 场，题都挺妙的，我一道都不会。

关于点分树的一些理解

定义与性质

点分树，就是把点分治中的每一次的重心连起来，构成一棵树。
由于重心的性质，点分治最多有 $\lg n$ 层, 所以点分树的树高最多是 $\lg n$

总结一下数学基础

求和因子法

用途

解形如 $a_i = ca_{i - 1} + b$ 的线性递推式。