CSP2024 游记

Day -1

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

Day 0

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

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

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

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

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

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

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

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

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

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

\(f_i=\max (f_j+s_{i-1}-s_j+[a_i=a_{j-1}]\cdot a_i)\).

这样 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 没清空，害怕。