2026.02.03
001. CF1066F Yet another 2D Walking（*\(\color{orange}{2100}\)）
难度：\(2/10\)
容易发现在走 \(\max\) 值相等的同一层时，一定只有两种不同的做法：
- 从左上角向右走到右上，然后再向下走到右下。
- 从右下角向上走到右上，然后再向左走到左上。
容易证明其余情况一定都不优。
然后问题就简单了：因为只能从 \(\max\) 小的地方走到 \(\max\) 大的地方，所以考虑直接区间 dp：维护出每一个 \(\max\) 值相同的连续段 \(l_i,r_i\)，然后设 \(f_{i,0/1}\) 表示当前走了前 \(i\) 个连续段，当前位于左上角 / 右下角，最小所需的花费是多少。转移是容易的。
总时间复杂度为 \(O(n\log n)\)，瓶颈在于排序，换个基排可以做到理论 \(O(n)\) 时间复杂度。
002. CF1997E Level Up（*\(\color{orange}{2200}\)）
难度：\(3/10\)
\(O(n\log^3n)\) 的做法的调和级数 + 二分 + 内层 ds 做法是简单的，但是因为 \(n\) 很大所以难以通过。
考虑优化。注意到若 \(k\) 确定为一个值的时候，某个怪物不会逃跑，那么 \(k\) 增大的时候这个怪物一定不会逃跑。同理，若 \(k\) 为一个值的时候某个怪物会逃跑，那么 \(k\) 减小的时候这个怪物一定也会逃跑。因此考虑让 \(k\) 从小到大扫描，然后每次增大处理出二分处理出新的不会逃跑的怪物，用树状数组简单维护即可做到 \(O(nlog^2n)\)。