2024 CSP-S 游记

\color{#00CD00}{高天之歌，与风同唱；听凭风引，且听风吟；千风涤荡，温门永存！}

upd:补充了部分细节

SD，初二某破初中。

-?? Days

初赛。80pts，感觉良好。细节忘了。

-7 Days

全真模拟，难度绿紫蓝紫，写了188pts，可惜挂了15pts，只A了一道绿。以为自己挺好，可是实际上是蒟蒻，有人把T2和T3直接生吃了。

-6 Days

讲解。没大听懂。

-1 Day

12:30从学校出来坐动车去日照。一路比较顺利，除了在火车上睡觉扭到了脖子，没有什么特别的事。

大约4-5点到酒店，吃了点东西去集训（浅浅吐槽一句：酒店的网太拉了）。

晚上去试机，是以个人为单位去，还怪远的，可是脑子抽了，只记了考场和座号，没有带准考证和任何电子设备就去了，只好跟着熟人去（甚至差点迷路），不得不询问值班老师才找到位置，电脑是Win10系统，看了下编译选项，写了两个对拍（A+B problem的暴力做法竟然寄掉了），都没问题。最后有惊无险地回去了。

回去后随便做了点题就去睡觉了。

0 Day

比赛日！

上午去吃酒店的免费自助早餐，评价：豪赤，下次还来。

吃完饭去做题，题单里两个题都是一发过，感觉良好。

中午吃点饭，%了下巴巴托斯，1:20去退房，等了一会就去考场。大约2点多入场，硬是在队列（无端联想queue）前端等了15min，

入场，写对拍，然后等待。2:30准时开题，考场比较安静，没有特殊事件。

考场不知何故非常热，导致我前1h都非常困倦。

T1

先看T1，简单题，秒出正解。于是没看后面的题就开写。我用的是贪心+桶维护，15min调完，过掉大样例了事。

T2

看T2，没看懂。

看T3，出了一个 O(n^2) 或 O(n^3) 的区间dp（虽然明显是错误的），由于不是正解就没写。

看T4，没看懂。

回到T2，由于环境过热，研究了20-30min没有头绪，于是打算先写个暴力再说。暴力写一半，头脑竟然奇迹般地清晰起来，于是想到用式子 A 求出一辆车开始/结束超速时行驶到哪里，再用二分求最先检测到超速的测速点和最后检测到超速的测速点，就得到了所有车的测速序列 P；求的时候判掉检测不到超速的情况，P 的长度就是第一问答案；把 P 按右端点排序，然后贪心就行，复杂度 O(Tn\log m)。

于是把暴力删掉开写，改掉几个若只 Bug 后竟然一下通过了所有样例。可是考场的机子有点神奇，开了 O2 跑大样例直接干到 2s 开外，试图优化未果，感觉复杂度没问题之后就扔下不管了。

T2大约花掉我100+min的时间。

T3

直接开T3，区间dp的思路假了，考虑线型dp。写了几个思路结果都假了。写的时候脑抽给转移式子加了若干个 f，答案过大就老实了。

于是开始研究，然后证出来一个性质：如果一个数对答案做出了贡献，则它匹配的数一定是它前面第一个和它相同的数。于是开写，用桶（为什么这么多桶）记录元素前第一个和它相同的元素的位置 p_i，然后猜式子，猜了几个意识到 f_{i,0/1} 需要从 f_{p_i+1,1/0} 而不是 f_{p_i,0/1} 转移过来，于是用前缀和维护中间 p_i+1 到 i-1 产生的贡献（i=p_i+1 的情况特判），答案显然，复杂度 O(Tm)。

写完发现竟然过掉了大样例，竟然复杂度还是正确的，瞬间感觉这辈子有了。

T4

T4没看懂，而且时间不多了，所以用直接输出法试图骗分。

检查

给T3补对拍，没出问题。T2感觉暴力很难写，而且不会出数据，就没管。这个时候就只剩15min左右的时间了。反复检查若干次文件名、文件读写，期间竟然发现T4的骗分代码出了问题（？？？），改完就交卷了。

因时间紧迫没有玩到小恐龙或扫雷，差评。

出场，听到大多数人估分140-260，信心爆棚。合了个影去赶火车。没有发生特别的事。

+1 Day

先后测了T3，T1，T2，T4(?)，不愧是有着风神庇佑的我，304pts，这辈子有了。再次膜拜巴巴托斯大人，希望不会挂分。

+? Days

听到熊猫要退役的消息，哀悼3秒钟。虽然但是，Venti巴巴托斯是这个世界上最伟大、最可爱、最温柔的神，人活着就是为了巴巴托斯，有了巴巴托斯的庇佑，胜利是必然的。

成绩

T1	T2	T3	T4
预估	100	100	100	4
实际	100	100	100	0

T4没骗到分（悲

这辈子有了。