2024/04/26(#34)：我要这水挡不住归途 我要天地都为我让步

原来一无所有 就叫做 齐天大圣。

时间真的还够吗。

前辈们做得很好，我能够做得到吗。

现在真的摆完了啊，怎么才能彻底清醒。

他们都好厉害。

我也想，做到啊。

所以，今天的任务做完有奖励！

29 六省联考 2017 分手是祝愿

只会做水题。

30 AGC047F Rooks

Portal.

太精彩啦！

一个暴力做法是，枚举每个 $s$ 求答案，然后用一个 $O(n^2)$ 的区间 DP 代表吃掉 $[i,j]$ 内的车。

但是我们不需要对于每个起点都求一遍答案，直接将整个区间 DP 的过程倒过来即可。也就是说，预处理出每个点能走到的区间，然后扩展这个东西。

状态数是 $O(n^2)$ 的，似乎是尽头？否！观察转移的形式，一定形如下图：

状态数只有 $O(2n)$，直接转移即可。

31 UVA11671 Sign of Matrix

差分约束，然后发现求中位数就是解。

复习整体 DP，树上启发式合并（长链剖分）等内容！