CSPS-2024 游记
Day 1
坐校车去的高中园，一开始直接去考场结果被赶去理慧高中等待了。
意外发现创新高中的墙上挂着霍尔海雅，这不是我们明日方舟的角色吗.jpg。
观察座位表发现偶数座位号全是深中的，和 zd，lls 一个考场。
偷看压缩包发现有道题叫 duel，也是押上题了（。
开题 duel 发现很水，一开始以为答案最多只有一半，但是马上发现可以让小的打小的，大的打大的，排序之后用双指针贪心就可以了，大约 5 min 写完，感觉比去年 T1 难。
开 detect，感觉题面好长不想读，于是先看了一遍 T3，T4，T3 又是涂色，初步鉴定为 DP，看完 detect 发现不会匀加/减速运动，还好良心出题人给了公式，照公式套一套应该可以搞出来每辆车的超速区间，如果超速区间里面有检查点，那这辆车就被统计入答案，判断是否有检查点可以用前缀和搞一下，考察第二问，说人话就是选尽量少的点覆盖所有超速区间，是经典贪心，区间按右端点排序，每次选择尽量靠右的检查点保留就行了，用树状数组判断一个区间里面是否有保留的检查点，写完测大样例，发现第三个大样例竟然 RE 了，调了好久发现原来是区间左端点可能是 0，减一变成 -1 树状数组就寄了，于是特判了 \(< 0\) 的情况，过了大样例。
开 color，这时大概过去了 1.5h，考虑了一个神秘 DP，把贡献的计算刻画成红序列和蓝序列后面接数字，那 就可以设计状态 \(dp_{i, j}\) 表示一个序列尾在 \(i\)，令一个在 \(j\)，最大贡献，转移：
\[dp_{i + 1, j} \leftarrow dp_{i, j} + [a_i = a_{i + 1}]a_{i + 1}, \\ dp_{i + 1, i} \leftarrow dp_{i, j} + [a_j = a_{i + 1}]a_{i + 1} \]然后滚掉第一维变成了：
\[dp_{j} \leftarrow dp_{j} + [a_i = a_{i + 1}]a_{i + 1}, \\ dp_{i} \leftarrow dp_{j} + [a_j = a_{i + 1}]a_{i + 1} \]发现第一个加的数和 \(j\) 无关，就是个全局加，第二个转移只需要维护一个桶，存储 \(\max_{a_i = c} dp_i\) 就行了，另外还要存一下全局最大值，全局加维护一个标记就行了。
很快写完并过了所有大样例，这时候大概还有 2h，先去个洗手间先。
在洗手间思考策略，感觉这个 T3 好水可能有很多人切，所以区分度应该都在 T4 上面，所以应该先稳一下前三题然后冲 T4。
回来给 T3 写了个拍子，值域 \(\le 1\) 的都试了，然后和没有滚动数组的暴力拍上了，但是和滚完了的暴力拍不上，手玩发现正解和没滚的都没有转移 \(f_n\)，滚完了的歪打正着转移了 \(f_n\)，改了就拍上了，拍了 1000 组值域 \(\le 10^6\)，测了极限数据只要 0.4s，感觉稳的一批就丢掉了（伏笔），T2 不好写拍子大胆丢了（伏笔），丢 NOI Linux 编译了一下都可以过编。
开 arena，题目读了好几遍，感觉很复杂，\(Tn^3\) 的分好像很多，于是先写了个 \(Tn^3\) 的暴力，把枚举每个询问，把所有没加入的人都设成 0，枚举每个人，如果这个人是已加入的，直接模拟一遍，否则把这个人能力值设成 \(10^9\) 模拟一遍，过了样例 1, 2, 3，样例 4 跑不动了，这个时候还有 1h，开始思考 \(Tn^2\) 怎么做，优化的思路是把同一个询问里的所有人一起处理，感觉可以 dfs 一遍二叉树，然后到叶子上就相当于一些 $\ge $ 的条件，貌似就可以了，感觉细节有点多写了很久，写完过了样例 1, 2, 3，样例 4 WA了，这个时候只有 15min 了感觉调不出来了，数据分治一下开始检查文件，并且重新测了所有的大样例。
考完了估分 100 + 100 + 100 + 32 = 332，和 lls，zd 交流一下，lls 好像 328，zd 说最后没时间测 T4 大样例了，大概 300+。
gjc 说他切了 T4，但是懒得写小恐龙启动了，然后开始对我口胡，我感觉疑似是有点假了，而且带了一只 log，出来没见到其他人，找到了贼猴，贼猴让我们去找别人，我找的时候遇见了鸡西，然后 Fourier 和 zw 从身后钻出来，鸡西冲 T4 没时间写 T3 了，有点可惜，Fourier 也是 300+。
坐车上水 QQ，想起来自己 T3 没清 \(a_{n + 1}\)，寄。
云斗默写一下 T3，没清 \(a_{n + 1}\) 65pts，清了过了，T2 回想起来树状数组里好像没有特判 \(c = 0\)，如果 update 到了那个 \(p = 1\) 的测速点可能会 TLE，炸了，不过感觉这种情况的概率不大，可能会少挂点（心虚。
感觉一下挂成了 100 + [80, 100] + [50, 80] + 32 = [262, 312]。
寄！！！
希望有 CCF你是我爹 环节。
标签：大样,T4,CSPS,T3,2024,感觉,游记,100,dp From： https://www.cnblogs.com/MoyouSayuki/p/18508669