时间安排
7:35-8:00
正序开题，20 min 写完 T1。
8:00-9:30
想 T2。先打了爆搜，然后想怎么 DP。设计了一个状态，转移是 \(O(n^3)\) 的。
9:30-10:30
假了。想了很长时间，去掉了一个错误转移，大概是对了。并把时间复杂度搞到了 \(O(n^2)\)，但是空间复杂度还是 \(O(n^3)\);
10:30-11:00
输出是样例的两倍，而且手造了几组小数据输出也是正确答案的几倍。打表找规律发现最后除以一个组合数就行了，能过样例。
11:00-11:30
转移只需用到上一次的结果，因此使用滚动数组优化。但是滚动数组没清空调了 20 min。
11:30-11:50
看 T3，T4。写了 T4 的链。
总结反思
- 每次 DP 题花费的时间都特别长，最不擅长的就是 DP。
题解
A.Stern-Brocot Tree
简单题。
B.礼物
不算很难的 DP。
C.魔法世界
把询问挂在右端点，考虑左端点的情况，使用主席树维护。
D.捡球
记录最低点和初值（0）的差值 \(p\)，以及终值和最低点的差值 \(g\)。
维护 \(x\) 子树内，最优秀的联通块序列,它同时满足以下三个条件：
• 是按照拓扑序排列的，即我们可以按顺序依次访问。
• 每个联通块都满足 \(g\)>\(p\)。
• \(p\) 从小到大单调
dus on tree。