CSP-S2022 游记

· · 个人记录

Day -1（10.27）

运动会，本来打算第二天出发，结果当晚晚读刚结束就走了。

于是坐大巴。

车上，吃运动会时剩下的运动员福利：吮指原味鸡。

Day 0（10.28）

$2:00$，睡觉。 起来先去做了个核酸。中午进行了贵族餐品的吃。 晚上吃火锅。前后打了几把狼人杀，感觉很猛阿！ ## Day 1（10.29） 起来以后讲解了一下 CSP-S2021 T4、平衡树 以及 单源最短路，很困，全程在水群。 中午吃盒饭，然而发现我没有带帆布袋。 大家很激动，想要面基，结果就帮一个老哥带了瓶水。 ___ 激动，$14:20$ 到考场，然后开始看题！ 先看 T1 阿，感觉很奇怪。于是开始试着写。 令 $dp[i][j]$ 表示路线上第 $i$ 个地点是 $j$ 的最优答案，然后 $O(kn^2)$ 预处理一下就可以开始转移。 复杂度 $O(kn^2)$。 测了下样例，发现读错题了，不能重复，浅维护了一下序列，虽然感觉很不对，但是一发过了小、中样例，就不管了。于是小的暴力，大的暴力 dp。 这时已经 $16:00$ 了，而我刚刚拍完 T1，拍了 2w+ 组，感觉挺舒服的。于是开始 T2。 看完题我感觉很牛逼，因为我一眼 ST 表/线段树，然而我都懒得写。 再看了一下发现要分正负维护，好寄吧牛逼啊我草。 于是我觉得我很牛逼地想出了一个只维护 $B$ 的做法，感觉是 $O(qn\log m)$ 的，很正确。于是马上开始写，大概 $40 \min$ 完成了工作，对拍无误。 然而我 ST 表的查询是带 $\log$ 的分层迭代，令人感叹。 突然发现数据范围是 $10^5$，不敢乱写了！老老实实地写了个维护 $A$ 的。 本来要分讨拿出下面 5 个数的： - 最大（小）正（负）数 和 $0$（特判） 后面一想，懒得分讨，最优答案必定出在它们之间，全部扔了出来。 时间复杂度 $O(wq\log n\log m)$，其中 $w\approx 4.5$。 写完，$17:30$，拍了 1.6w+ 组，感觉很正确，不管了。 还剩一个小时阿，看完 T3T4 用了半个小时，剩下感觉只能莽 T4 暴力了。 然而我写的是 dfs 而不是 bfs，令人感叹。最后摆了，懒得写了。 ___ 回来车上吃了肯德基，测了一下： - Luogu：$100+100+0+0=200

睡觉。

Day 2（10.30）

已经开始返校了。

【更新】 计蒜客：100+100+0+0=200。

Day 3（10.31）

InfOJ & LHQ 测试：85+100+0+0=185，全省 rk19。

Day n（11.07）

出分：90+100+0+0=190。