CSP-S 2024 游记

9.21

考前非常自信，目标 AK。

进考场，诶，怎么全是小学生？发现桌子很矮，竟然可以调高，调高了感觉舒服多了。

70min 做完了所有题，20min 检查了一遍，啥都没检查出来，直接睡觉。

结束之后发现错了 4 个，92 虽然比去年低但还可以吧，无所谓了。

10.24

和 @wangsiyuanZP duel 100 回合，成功掉成 CM。

10.25

学校春游秋游请了假，在家睡到 10:30。下午做了信友队模拟赛，T4 猜错结论喜提 100+100+60+50=310，题目过于抽象所以没有补。

晚上看了一下 NOI 大纲，学习复习了一些算法，20min 写过了平衡树，23:00 左右睡觉。

10.26

CSP-S 2024 RP++！

大概 14:20 到考场，见到了 wdm,wzc,lhq 等人，还有我们班的一些大佬。进考场，试了一下键盘，感觉还可以。

14:30 开题，T1 弱智，为了防止挂，证明了一下，14:40 过。

开 T2，发现物理公式忘了，手推了一下，结果发现样例解释里给了。但我做麻烦了，用了 set 动态维护，15:15 过。

开 T3，打了一个很一眼的暴力 O(nw)，其中 w=\max\limits_{i=1}^na_i。思考了一下，发现可以优化状态，然后维护每个 a_i 对应的 dp 最大值，15:50 过。

接下来就到了 T4。花了十几分钟理解了一下题意，试图思考 O(m\log n) 无果。后来发现可以一个一个加入，想到了一个 O(n\log^2n) 的做法，具体每个节点需要维护一个 vector。

大约 17:20 的时候调出了这个并卡了卡常，发现大样例复制 128 次只跑了 3.35s，这样就有 84 分。

我试图把这个优化到 O(n\log n)，但我的想法是只对有修改的修改，导致写的巨恶心还没调出来，当然调出来了好像也不一定能过。赛后发现可以直接状压，我是小丑。

不过赛后发现 ylx 也没有过，那应该问题不大，希望 CCF 神机跑快点。

upd：复杂度其实就是 O(n\log n)，我以为每个点可能有多个已确定选手夺冠，开了一个 vector，实际上每个 vector 里只存了一个元素，所以是大常数单 log……要是赛时发现这个卡卡可能就过了（？）

upd：好像左右可以互换，那这个结论是错的，唐完了。。。

估分：100+100+100+[76,92]=[376,392]。

洛谷：100+100+100+76=376。

云斗：100+100+100+80=380。

信友队：100+100+100+76=376。

upd：把 vector 换成数组就可以在三个平台上获得 84 分了，赛时一直在调 O(n\log n) 没卡常……

11.4

出分了，100+100+100+76=376，输！