C！S！P！2！0！2！5！游！记！！！

· · 生活·游记

Day -n

做了若干模拟赛，每场模拟赛都只能稳定切出一下较为简单的题，菜完了。

Day -6 至 Day -4

做了若干分治题，感觉脑子快被分成二的若干次方份了。

Day -3

学习 slope trick，切分治水题，爽。

Day -2

Fish touching。一整天只做了一些简单树形背包。

Day -1

上午看了一下动态 DP 如何能做到一只老哥，发现全局平衡二叉树上面维护矩阵还是太过于困难了，遂学习 Toptree。这玩意是真好用，就是如果要处理点的问题需要特殊考虑有点麻烦，下午&晚上 Fish touching。

Day 0

额啊啊啊啊啊，怎么考试了？What should I do？想不懂那就不干了。上午啥都不想干，看球看了一会，看画画教程又看了一会，切一个 Toptree 水题，题目看错导致代码重构了一遍 qwq，学习 SATT 未遂，然后颓废到了下午。

饿啊，站在考场外不知道干啥。饿啊！！！饿，就要吃饭，薅了同学一包零食吃。吃吃喝喝，机机房房，考考试试，嗯？怎么开始考试了。我不会爆零吧？那样的事情，不要啊！

开局直接以迅雷不及掩耳之势开 T1。哎呀？怎么回事，不会！！！想了 10 分钟发现我是一个一个物种，which 不是人类，切掉，总耗时 17min。

开 T2，啥啊这是，不会口牙。怎么办怎么办怎么办？看看数据范围，啧，这么一看，暴力好像挺能过啊。然后直接枚举选哪些农村城市化改造，乱做，然后被如何归并十个边集卡住了，最后选择直接用 priority_queue，写了个魔怔的时间复杂度为 O(nk2^k(\log_2k + α(n))) 的神秘做法。

开 T3，唔，怎么这么简单直接写，写了个 hash+trie+二维数点，因为弄混变量名调了 1.5h，代码 4.5k，应该没有人的做法跟我一样魔怔了，场上咋没想到 AC 自动机啊，只能说得了一种一看到字符串就想 hash 的病。

此时 5:50，T4 看了一下，不似我能做出的，打个暴力下播，懒得想特殊性质，反正 CSP。

此时 6:00，得分 100+[80,100]+100+20=[300,320]，下播，懒得打了。

剩下的时间魔怔了一会，想出来一个求数组最多取 k 个值能取得最大和的方法。

我们设 f(k) 为数组取 k 个数能取得的最大值，我们发现这个东西是凸的，遂可以 wqs 二分，时间复杂度 O(n \log k)。

出考场发现大家大多不会 T2 我就放心了，太困难了 T2，不可战胜的，然后听了大家的 T3 做法发现我是个唐诗，而且 T4 有些特殊性质特别简单我没打，也是我的传统了，去年我 CSP 与 NOIP 就没打特殊性质。不管了下播。

upd on 2025.11.2 0:23

哈？你跟我说 T3 询问数组的长度不一定等？那我说白了，大样例跟数据不一个强度的不好评价。