CSP2024 游记

· · 生活·游记

cnblogs

由于洛谷每次提交都要重新审核，为了减轻审核压力，近期更新都在 cnblogs 里。

Day -1

没啥好写的，唯一要说的就是写了一个很 ex 的题，硬控我三个晚自习。

Day 0

7:00 起床，吃完饭到七点半，whk 生活很难体验到的松弛感。

晃到班级拿了眼镜盒，碰到物理老师打了个招呼，然后发现水杯没拿，又回来拿水杯，拿完水杯就 8:00 了，于是早晨复习计划取消。

8:20 上车，8:30 左右出发。车上试图睡觉多次被吵醒，遂放弃，和一群学弟观看 wmyr 颓 DC。

其实挺感慨的，已经从车上大部分人的学妹变成学姐了。顺便一说，初一小朋友认为我是高一而不是高二的，原因是太矮。生气了。

大概 11:30 到达南航，下车吃饭。吃完饭睡觉，越睡越困，就出去吹风了。看了 J 组题目，口胡 T4。

考场在南航 1 号楼 6C，没碰到熟人，难过。

下午考试，刚到考场非常困，试机打了一个头文件就睡觉了。

密码好像还晚发了几分钟，但没延时。

开 T1，感觉很简单，很明显就是从小的开始发动攻击，打严格比自己小的。但是一开始写错了，但是只错了最后一个大样例。用时不到 0.5h。

开 T2，很快明白 T2 就是要求一些线段选一些点，要求每个线段中至少有一个点。想了一个贪心做法，证明了对于没有包含关系的情况是对的。然后发现包含另一个区间的区间可以不用考虑，也很快写出来了。此时总用时在 1.5h 不到。

觉得有 200 分可以摆烂了，于是想着 T3 部分分怎么写。但是只想出了 n^3 的 dp。考虑换一种状态，发现只有一段的开头颜色会受到前面的影响，f_i 表示有一个颜色段以 i 开头的最大贡献，枚举上一段的开头 j，预处理连续颜色的贡献 s 就可以很快计算。

这样 dp 状态数 $O(n)$ 很有优化前景。观察 dp 式子发现只要对每种颜色记录一个 $f_j-s_j$ 的最大值就可以 $O(1)$ 转移。 觉得拿到 300 分之后就可以摆烂了。但是还有 $1.5h$，怎么会是呢。 然后开始看 T4，读了几遍题真的不想写。后来瞎写了一个 $O(n^2)$ 的假做法准备骗点分，结果发现它可以过性质 A，B 的样例。 不管了，能拿多少分随缘吧。 你说得对，但是我浪费了 $1.5h$。 估分 $100+100+100+?=300+?$，后来发现 $?$ 大概会在 $20$ 左右。 qhj 320，拜谢 --- 回去的车上吃了 KFC，开心。 本来想睡觉的，但是似乎没有人在睡，于是就和周围小朋友聊天了。 回家后看到有自测，花了一个小时复刻 $T1-3$ 代码。担心 T2 没清空，害怕。 --- ### Day 1 复刻了 T4，洛谷数据比较水，获得了 $36pts$。 目前洛谷估分 $100+100+100+36=336$，如果 CCF 数据也这么水就好了。