日记

上午#

依旧是考试，依旧是头昏脑胀，睡了 $15$ min，被祝老叫醒。T1上来就是一道博弈论，但是还是比较简单，T2是一个二分答案（真这么简单吗）。T3感觉能做。

考试链接 题解在此

upd：反方向的rank5

T1：它说 dogwang 取的区间里不能包含 dogenya 删除的数，我们考虑在区间内循环查找 dogenya 删除的点，使得删除之后，剩下两段的和的最大值最小，然后如果删除的点左边的区间和更大，就把这一段给 dogwang 加上去，右边继续重复以上的操作；反之亦然。

时间复杂度 $O(n^2logn)$ ，$500$ 轻松过。（会不会做法假了）

upd：就是做法假了，正解是区间dp;

T2：注意到（依旧注意力惊人）当攻击力增加时，能收集到的货物数一定增加（人话：货物数单调递增）。我们就可以想到二分。二分她的攻击力。然后，每次二分，都在树上跑一遍，记录能有多少个货物。

时间复杂度 $O(nlogm)$ ，算了一下大概跑 $3 \times 10^7$ 次，卡下常跑得过。（会不会做法也假了）

upd：这个做法倒没假

T3：在考试结束前10min想出了 $60$ 分做法，当然没时间打咯。

T4：打了个 $O(n^4)$ 暴力，期望得分 $30$ （实际一分没有）。

下午#

照理说该改题的，但是祝老第一节课没来，然后就没有题解，就改不了。所以就切了一道字典树。

P8306 【模板】字典树#

死因：memset 。

T1：这么简单的区间dp，我为啥赛时没想到？？也是没救了。

T3：单调栈？线段树？我写你冯了个福。T4：找你冯福的四元环啊

P4551 最长异或路径#

这tm到底是什么错啊 $\Rightarrow$ 这tm是什么沙比错误啊 $\Rightarrow$ 他们（指出题组）到底是怎么出出来这么水的样例的啊，我tm这么低级的错误都能过。

由于我每天都忘带U盘而我还要把代码和题解拷回家改，于是我决定把所有的代码和题解放到一个仓库里托管到gitee和github上，那样就不怕代码忘了存了，还比存网盘方便。

晚上#

方大把T3讲了，然后我就去打了一个暴力，拿了 $60$ 分，然后就去看方大的 std 。题解里用的单调栈，方大用的单调队列，而这俩，我都不会（我实在是太菜了）。明天不考试，写写字典树，再练练单调栈和单调队列吧（虽然多半没有时间）。

已经看到了，提二分数线一点没降，我只能拿提三，呜呜呜。

晚上回家，发现，学校都上的去 github ，但是在家里上不去，简直是，无法可想。