忆 OI 往昔，峥嵘岁月稠（游记+退役文）

Lysra · 2024-10-25 18:47:22 · 生活·游记

Day 0

感觉挺紧张的，明天就是最后一次 CSP 了。

今年换成当天早上去了，没法在酒店里皮了QAQ

希望能够拿到类似于 NOIP2023 的分数，暴力打满，挂分也降到最低。

Day 1

大概早上八点到达机房，跟 qhj 大佬讨论了几道他最近做的题目。

太菜了，一道都不会做，甚至还有一题听不懂。

看了一会儿题目后上大巴，在车上先是用电脑玩 DC （貌似有人觉得噪声大，我个人认为这主要是 zsj 的原因）。

玩了一会儿后一细胞暴毙两次，不想玩了，就拉着 wjy 打坦克动荡，俩人在那儿欢乐互射。

到站后电脑刚好没电，去酒店吃午饭，顺带看了 J 组题目。

T4 题面太长了，于是跟 ljn 研究了一下 T3 正解就没管了。

进考场，本来应该坐在 84 号机位的，但是因为机器故障后来调到了 77 号机位。

考试前上了个厕所，南航厕所挺干净的。考前胡思乱想了一会儿，最后利用这 30min 打了线段树，匈牙利，缩点，dijkstra 以及 LCA。

写完之后真的不知道该干啥了，坐在位置上挺紧张的，就疯狂地刷新桌面，看有没有将密码发下来。于是乎我便成了考场上领先别人 2min 看到题面的人。

先看了眼 T1，太一眼了，甚至都没动笔或者思考，花了不到 3min 打完并测大样例，写完比赛甚至刚刚开始。近几年提高 T1 真是越来越水了。

但下面发生了一件令我无法理解的事情，我到底为什么要紧接着去看 T4 呢？

说实话我也不知道我怎么想的，可能是想到去年 S 组的 T4 比较简单，也可能是因为觉得题面长度与题目难度成反比，看到 T4 题面长就去莽了。

看了一会儿甚至感觉自己会做了，写了一个先建树然后倒序将节点随机化的代码，样例一测不对，才发现题目读错了，要求输出的不是节点数，而是节点编号和。

现在想来真无语啊，要是题目要直接输出节点数，那么 a 数组和 T 多测的意义在哪儿。

个人觉得这才是这场比赛中我最大的问题，没想好就开始实现代码，导致花费很久的时间打一个假做法。

若是谨慎一点，将所有东西都考虑到，发现自己不会 T4 进而去打暴力，那么即使采取首开 T4 的策略，也会比现在多上 32pts 的暴力分。

到目前大概已经是比赛开始 1.5h 了，浪费如此多时间的我不甘心呐，于是便又浪费了一小时，打了个启发式树上 set 合并，最后发现根本不对。

到那时已经比较崩溃了，在官方考场上花费 2.5h 斩获 0 分这种事还是第一次在 OI 生涯中遇到。可以确定，我应该是我校目前得分最低的，2.5h 总计 100pts 已经似透了。

但好在思维没有完全乱掉，也还算清醒，果断将 3KB 的一坨启发式合并删掉，然后去看 T2。

从那一刻起，翻盘开始了虽然好像最后也没翻起什么浪花。

明白自己时间不多，果断抛掉 T2 较为构式的题面，直接去看样例解释，很快理解了题意。

挺板的，T2 也能一眼我是没想到的。当时脑海里大致想法是这样的：

将所有车的 a 按正负分为两部分，a=0 归在正数那一类（不然后面会出现除以 0 的情况）。

先考虑 a 非负的情况，此时车的瞬时速度 v 单调不降，所以若在某一时刻 v>V，则对于后面任意时刻都同样有 v>V，满足要求的测速仪区间就形如 [i,m]，二分即可。

那如果 a 为负呢？此时我们就还要考虑减速为 0 的情况了。

我们可以先二分求出每辆车能够行驶超过的最远测速仪 x，位置位于车前且最小的测速仪 k，满足要求的测速仪就一定处于区间 [k,x] 内。

而又因为车的瞬时速度 v 单调递减，所以若在某一时刻 v>V，则对于前面任意时刻都同样有 v>V，满足要求的测速仪区间就形如 [k,i]，再写个二分即可。

最后存在多少个取值区间，就有多少车是能够被测出超速的。

这样我们就用 O(n\log n) 的时间复杂度附加极大的常数解决了第一问。

下面来看第二问，其实就是个比较经典的贪心模型。

我们考虑将所有区间 [l,r] 按 r 从小到大排序，维护一个变量 R 表示当前拓展到的最右端点，然后按顺序对每个区间 i 执行以下策略：

• 初始 R=0。

• 若 l_i \le R，则跳过。

• 否则令 R \leftarrow r_i，累加答案。

这样做的本质就是尽可能选每个区间最靠右的数（也就是 r_i），那么为什么这样做是最优的呢？

假如说枚举到区间 i，你选择了 r_i-1 号测速点，那么这个测速点就可以被之后的若干区间共用，假设为 i 至 j_0 号测速点。

若你此时选择了 r_i 号测速点，你就会发现能够共用的区间个数变得更多了。若假设为 i 至 j 号测速点，则有 j_0\le j。

所以选择更靠右的点可以保证答案不劣的同时产生新的贡献，自然也就是最优的。

总体时间复杂度 O(n\log n)。

绝对不是从提交失败的 T2 题解抄过来的

可以看出直觉下的思路还是比较繁的，但当时紧迫的时间已经容不得去优化了。最后大概总计花了接近一小时打完了。

此时还剩 40min，我明白这只够我从 T3，T4 中选择一个去做了。

开 T3，关注到部分分给了 O(n^3) 以及 O(n^2)，首先考虑 dp。

紧接着就发现 dp 怎么这么一眼啊（恼），CCF 出的都是什么板子题啊。。。

先设 dp_{i,j,k} 表示前 i 个数字，最近红色数字为 j，蓝色为 k，然后空间优化方式就几乎与蓝书上的这题一模一样了。

首先发现 j，k 中必有一数为 a_i，将其化为 0/1，再发现 0/1 其实根本没啥用，只需知道 a_i 与 j 颜色不同就行，考虑一下转移，发现 i 只与 i-1 有关，滚动数组滚掉，至此空间复杂度 O(n)。

时间复杂度一开始是 O(n^3)，具体想法与题解区中 zyn_ 大佬的想法一致，先是发现最内层循环本质上就是取 \max，使用变量维护即可，然后将整个 dp 翻译一下，发现本质就是若 a_i=a_{i-1}，那么使 dp_{a_{i-1}} 加上 a_i，同时进行特判即可。

其实是可以用懒标记的思想做到 O(n) 的，线段树 O(n\log n) 貌似也能过？

然而可惜，40min 只足够我打 O(n^2) 的做法了。考场上其实已经有 O(n) 的思路了，但还是选择了先写平方做法，仅剩不到 10min，尝试着写了一下线性思路，没过大样例。又尝试用了一下线段树的带 \log 做法（试机时写了线段树），也没过。

我已经知道了，大抵 CSP-S2024 就这样了吧。