CSP-S 2024 睡着了记

· · 生活·游记

Day -7

就从今天开始写游记啦！

上午睡大觉，中午起床，发现洛谷有比赛，于是开打！于是获得了 T1 的一血并在 T2 中耗费 2.5h

晚上 AtCoder，直接渊深启东！简单 T4 被我调 25min，带着 5 的罚时，喜提 \blue{1600} perf，好好好好又掉大分了，CSP 前最后一场 ABC 都打不好是吧。然后 CF div2 和 ABC 之间间隔高达 25 min，紧急补了一顿晚饭，然后 div2 打起来向赤石，15 min 切完 ABC 之后在 D 上写了 6K 的大粪桃，但是切了之后 perf 有 \orange{2200}，优势在我，睡觉

Day -6

起床之后发现 perf 只剩 \purple{2050} 了，十分 /fn/fn/fn，但是因为上 CM 了所以【】

然后手滑把一个题的标签给删了

下午 div1 忘打了，哈哈哈，joker

Day -5

上午随机刷 CF，然后模拟赛启动，25 min 切前两题，发现后面椿石，十分恶心，直接跑路，喜提模拟赛导医！

欧欧欧，CSP-S 也能拿导医就太棒了，诸法了

Day -4

距离 CSP-S 还有 4 天。

线段树板子写挂一个晚上，我真厉害。

包括但不限于：

喜提 14 发罚时，太有实力了。

===============================================

达成成就：

一个月内通过 200 题祭。

Day -3

距离 CSP-S 还有 3 天。

学习模拟退火，学不会！做 CF，一题不会做！！！

下午模拟赛，30 min 切 T1 T2，然后发现 Xu Liu 搬运了整整一套原题，且这套原题的题全是搬的，于是直接开摆！！！

upd：T2 原题是 P3488，怎么来的紫。

Day -2

得知 Day -3 的模拟赛又挂分了，怎么回事呢？

哦原来是 cin/cout 不关同步流被卡常了。这不得不怪 aimat 了 300\to 230。

下午就不得不原神启动了，，某位性刘名旭的教练找到了两套“普及组模拟赛”并让机房里所有人在 2.5h 内 AK，结果第二套全都不会，并且还因为某些原因挂了至少 110 ：（

某位教练：有返回值的函数一定要 return

我：好的

当天的模拟赛：有返回值的函数没有 return

然后被某位教练线上单杀了

Day -1

补了一上午的觉，下午坐车去日照。

然后在日照迷路了，获得成就：围着路口转了 \red 5 圈。

晚上试机，考场是 C301 28 号，靠着门和 KID2695，但是我找错位置了，找到了 18 号（大雾 打了快读板子、线段树板子、最短路板子和线性基板子然后被轰出了考场

话说今年怎么没有虚拟机啊/fn 怒怒怒

出考场遇到了可爱的 aimat 姐姐，真的十分可爱/se/se/se

晚上打了 15 个板子，然后十分的困就睡觉了/shui

Day 0

没有 Day 0。

Day 1

早上七点半起床，然后发现困的要命（\blue 1），但是忍着爬了起来打了另外 10 个板子和模拟退火，并顺着 CF 刷了几道 1900 和 2100（下一道是 CF1799D2），但是困*困**困*困，

听了一遍《小幸运 OI》，没这么困了

（此处省略一段文字）

下午两点入场了，在入场的队伍里看到了可爱的 lemon_qwq 柠檬姐姐，在考场里看到了可爱的 KID2695 姐姐（就在左边的左边），开心/se

话说进场怎么不安检啊（

两点半比赛开始，看 T1

？？？我怎么不会啊？？？

再看一遍，

？？？我怎么还是不会啊？？？

再看一遍，

……

！！！我读错题了！！！

然后想到了一个简单的做法：

将所有卡牌从小到大排序，然后考虑维护两个指针 i=2，j=1，若 i 卡牌可以攻击 j 卡牌，那么就攻击，令 i\leftarrow i+1，j\leftarrow j+1，否则 i\leftarrow i+1 直到 i 卡牌可以攻击 j 卡牌。总的时间复杂度为 O(n\log n)，使用 aimat 排序可以做到 O(n)。

写写写，怒写 1K，用了 2 min，一遍过大样例，好耶

Time: 14:33 Score: 100pts

看 T2，看不懂，看 T3，想到了一个简单的 dp：

设 f_{i,j,k} 表示当前前 i 个卡牌，上一个红色为 j，上一个蓝色为 k，最大值是多少。转移简单。时间复杂度为 O(n^3)。

但是只能获得 35 分（怒）

继续挖掘性质，发现一个 dp 状态是合法的，当且仅当 \max(j,k)=i-1 且 j\neq k，此时合法 dp 状态为 O(n^2) 量级：

设 f_{i,j,0/1} 表示当前前 i 个卡牌，上一个不同于 i-1 所染颜色的位置为 j，当前卡牌染为红色 / 蓝色，转移仍然简单，但是需要分 4 类讨论。

这样是 O(n^2) 的，能获得 50 分了（喜）

然后发现有 15 分 a_i\le 10，于是考虑数据淀粉质然后按值域 dp，可以获得 65 分了（大喜）

Time: 14:35

然后开始写，写了 5 分钟，又是一遍过所有样例？？？感觉这回 rp 有点高（

Time: 14:40, Score: 165pts

回去看 T2，然后发现这 T2 不是水题？（看错题了）我一开始认为所有车的开始点都是 1，于是最坏情况下只需要保留第一个摄像头和最后一个摄像头，直接四种情况分类讨论即可（喜

然后看大样例：？？？这性质怎么不对啊？？？

重新读题：乐乐乐乐，开始点不一样（怒

于是我决定先考虑第一问：

对每一辆车的加速度 a 分类讨论：

  • 若 a\ge0，则选择最后一个摄像头时不超速则一定不超速。
  • 若 a<0 则找到其能找到的第一个摄像头，若此时不超速则一定不超速。

第一类情况可以直接找，第二类情况直接对下标二分即可。

然后是第二问：

考虑对于每一辆会被记录为超速的车，计算出其会被计算为超速的摄像头的范围。考虑对时间为 x 轴当前顺时速度为 y 轴建系，则每一辆车都在平面上成为一条直线。将平面满足 y>L 的部分保留，其余部分删除。则当前每一条直线剩余的部分要么不存在，要么是一段连续的区间。这个区间可以直接二分求解，时间复杂度为 O(Tn\log n)。

然后问题变为给定一些线段 [L_i,R_i]，要求找出尽量少的点满足每一个线段上至少存在一个点（包含端点），可以对右端点贪心之后排序。总的时间复杂度仍然为 O(Tn\log n)。

然后出了一个小插曲就是说我在考场上推了 20 min 求包含加速度的顺时速度，结果发现题目最后面给了（大悲

然后开始写，出乎意料的一遍写对了（

Time: 15:10, Score: 265pts

然后高兴的上了个厕所，回来之后忽然觉的头晕，（内心os）要不先趴一会儿（然后就在桌子上睡着了！！！）鉴定为 rp 过低导致的

Time: 17:00

我也不知道具体是什么时候醒过来的，差不多就是这个时候（悲

（内心 os 已被删除）

Time: 17:05

想到了 T4 的一个简单做法。

考虑对于每一个人 i 判定其是否能获胜：

  • 若 i 不是被加上的人员，则令所有被加上的人员的值为 0。
  • 若 i 是被加上的人员，则令自己的值为 INT_MAX，其余人的值为 0。

然后直接判断当前人是否是最后的赢家即可。

算了一下可以拿到 32 pts，于是开写。

Time: 17:50, Score: 297pts

犯了一些很南崩的错误，然后浪费了大量的时间（

忽然感觉会有不少人获得 100+100+100+0=300，所以决定再拿 4\sim 8 分（

Time: 18:05

忽然发现 A 性质本质不同的数的数量为 \log 级别，所以说暴力也能过？

Time: 18:15

调过了（好耶

Score: 305pts

Time: 18:30

考试刚一结束可爱的 KID2695 姐姐就跳了过来告诉我她 T3 过了，但是 T2 没过（雾，问我 T2 怎么做，她说她的思路是：

对每一辆车的加速度 a 分类讨论：

  • 若 a\ge0，则选择最后一个摄像头时不超速则一定不超速。
  • 若 a<0 则找到其能找到的第一个摄像头，若此时不超速则一定不超速。

第一类情况可以直接找，第二类情况直接对下标二分即可。

然后是第二问：

考虑对于每一辆会被记录为超速的车，计算出其会被计算为超速的摄像头的范围。考虑对时间为 x 轴当前顺时速度为 y 轴建系，则每一辆车都在平面上成为一条直线。将平面满足 y>L 的部分保留，其余部分删除。则当前每一条直线剩余的部分要么不存在，要么是一段连续的区间。这个区间可以直接二分求解，时间复杂度为 O(Tn\log n)。

然后问题变为给定一些线段 [L_i,R_i]，要求找出尽量少的点满足每一个线段上至少存在一个点（包含端点），可以对左端点贪心之后排序。总的时间复杂度仍然为 O(Tn\log n)。

（此处省略 10^5 字）

出来楼又看到了最可爱的 _Nancy_ 姐姐，她说她 T1 过了但是 T2、T3 没过

Day inf

最后怎么了。

【数据删除】