CSP-S 2024 游记

前情提要：NOI 游记。

Day -34

初赛 85.5，有点爆炸。完全没读懂那个树哈希在干嘛。

Day 0

坐高铁回苏州。

什么都不想复习。打了好久 mdt 打了好久音游打了好久雀魂，最后看了一眼匈牙利和 exgcd，一点钟才睡觉。

Day 1

早上十一点钟起床，然后去吃了很久没有吃的奥灶面。

去考场的路上喝了一杯咖啡。

到考场的时候发现完全没有人！原来是上一批带队刚走。这下晚二十分钟进入考场了。

键盘手感还不错，赢。考前敲了个对拍和 a+b。

14:20 下发了压缩包密码。怎么这么早？哦 pdf 还有一层密码。

14:25 观察大样例，duel 和 color 输入只有一个数组，detect 是 n\times 3 个数后面 m 个数，还有两个常数，arena 看不懂。

14:28 发了 pdf 密码。

14:31 诶这个 T1 不就是众数出现次数吗。开写。

14:36 写完了 T1。

14:37 哎哟这个 T2 是啥，大模拟吗。

14:39 好像是要带着小数算一大堆东西啊！！！好烦好烦好烦但是开始写吧！

15:10 写了依托带分数类运算的答辩出来，过不去样例。

15:12 诶我不是可以把每个车的超速区间缩成整数吗？

15:26 怎么又挂了？

15:44 通过了 T2。

15:45 T3 似乎是小清新题？爽！

15:55 我们可以设 f_{i,j} 表示考虑前 i 个数，与 A_i 颜色不同的最后一个数是 A_j 的最大价值，然后就得到了一个优秀的 50 分做法。f_{i,j} 可以转移到 f_{i+1,i} 和 f_{i+1,j}。

16:00 发现 f_{i+1,i} 好像很关键！于是我们直接把 f_i 的定义改成原来的 f_{i,i-1}。这样我们有 f_i=\max\limits_{j=1}^{i-1}(f_j+[A_{j-1}=A_i]A_i+\sum\limits_{k=j}^{i-2}[A_k=A_{k+1}]A_k)。这个已经可以直接全局加做了，但是我们把相邻的相同数提前缩起来就全局加都没有了。

16:05 通过了 T3。

16:06 这个 T4 题面好长啊！！！！但是看起来似乎不是很难？

16:30 是不是可以维护每个新的数加进去的过程...然后在每个子树统计这个子树内可能获胜的点的和......不对，还得分 \log 种，这样是 \log^2 的，正解应该要线性。看看特殊性质有没有什么提示吧。

17:10 这个特殊性质跟正解到底有没有关系啊？不管特殊性质了从头想吧。

17:20 似乎考虑每个点可以贡献到的范围会比较简单......一个点能获胜当且仅当它没有被干掉，也没有自己死掉。

17:33 不是直接维护每个子树最早的形成唯一赢家的时间就行了吗？？？这不是两遍 dfs 做完了？？？

18:01 写完了，但是为什么 WA on arena3.in？？？拍一拍 n=8！！！

18:15 怎么拍不出来？？

18:22 哦怎么挂在了一个不会在小数据出现的情况！改完就过大样例了。

18:28 检查 freopen，统计字节数。

18:30 收卷。

出考场一问大家都不会 T4 线性！那我不是赢麻了？但是我完全没有进行除了测大样例以外的检查。会不会挂分尚未可知。

手搓题解。

回到家一看下发了选手代码，但是压缩包有密码。生气。只能手动重写代码。诶这个 T2 怎么这么简单我场上在写什么东西？

自测过了 T1T2T3，但是不知道有没有什么奇怪的现在没写出来但是场上写出来的锅。

怎么没有 T4 自测？怎么没有 T4 自测？

Day 2

早上起床，很快啊，有 T4 自测了！怎么 1.19s TLE 92pts？？？？

本机造一组，怎么 1120.5377 ms？

CCF 能不能神仙机器发力能不能给我过啊能不能给我过啊！！

Day 10

谢谢 CCF！！！100+100+100+100=400！！！

第一次也可能是唯一一次 AK CSP-S！