CSP-S 2022 游记

· · 个人记录

前言

GX蒟蒻OIer

今年第一次考 CSP-S ，当然也是高中生涯的最后一次。（弱省是这样的）

写点东西纪念一下。

Day 0

最后一场小模拟赛，教练挑了一场普及组的给我们考。

AK倒是AK了，但内心很紧张，因为去年我们学校 CSP 成绩并没有同省别的学校好，再加上那天被班主任恶心了，导致晚上整个人都是麻的，随手敲了几个边双点双的板子就去睡觉了。

Day 1

上午也不知道干啥，打了会 florr ，敲了份 splay ，打了点图论算法板子，中午甚至午觉也没睡。

由于我们考的模拟赛大部分都没有出图论，当时和同学打趣说：“没准今年 CSP 就考图论呢 ”，没想到还真挺多图论。

考试那地方离我们学校挺远，教练租了辆车，开了半小时才到。索性在车上听着音乐眯了一会，虽然因为太颠并没有睡得很深。

下午到考场，考场电脑质量挺高，不逊于本校机房的电脑。

发现兄弟学校来的人真的多，大概是我们学校的 1.5 倍吧，看来今年确实是来势汹汹。

T1

刚开考看 T1 ，发现写不出来 O(n^2) ，就先开了其他题。

后来觉得大概要写个暴力，本来想枚举两边的点再对中间的点进行判定，瞪了一会发现不可做，是 O(n^4) 的，于是就改变思路枚举中间两个点。

但是想不到如何进行判定中间两个点合法，只好写了个 O(n^3) floyd 拿 70 分。（赛后和同机房大佬交流才想起来对每个点 bfs 预处理只用 O(nm) ）。

然后两边的点判定写的是枚举的，记录最大点和次大点，总复杂度也是 O(n^3) 。

调了差不多一个小时才出来，luogu 上 70，infoj 上挂到 55。

赛后感觉记录第三大可以做到 O(n^2)。

同机房的人套了个堆带 log 估计是过了。

T2

实际上先开的这题，线段树维护区间正负最大最小值，对零特判，写了 40 分钟吧。

一测四个样例都过了就丢一边没管，以为期望得分 100 。

谁知晚上到 infoj 测只有 40 ，一看原来是有个字母打错了。

改过以后才是 100 。

所以说 CCF 的样例是真的弱。

但是 luogu 民间数据也跑了 100。

说不定 CCF 脚造数据还能多骗点分？

T3

上来看题目发现是找环，开始没看样例，以为是硬性要求每个点出入度都为 1。

写了十分钟不过样例，一看样例解释才知道只需要出度就行。

正解实在想不到怎么维护，就花半小时写了样例，半小时性质分。

估分 50 到 60 吧，infoj 上 55，不懂哪里写挂了。

T4

写这题时只有一个小时，时间比较赶。

怕写不完，上来先 rush 了一个树上差分得 20 分。

然后我并没有想到 k=3 的时候可以找中转点，以为只是单条链的询问，就写了个树剖维护。

凭手感写的，没怎么调，还有 20 分钟的时候写完，并且过了样例 1。

但是样例 2 死活过不去，我以为是自己树剖写炸了，就搁那瞪代码瞪了 20 分钟瞪不出来，于是心态崩了，以为只剩 20 分。

赛后到 UOJ 群问了树剖正确性，才想到中转点的情况，感觉更寄了。

和省外同学聊了聊，转念一想好像 k=2 和中转点没啥关系。

于是交了 luogu 和 infoj，k=1 和 k=2 都过了，60 分大概。

松了一口气吧。

总结

考场预期 70+100+60+20=250

infoj 55+40+60+60=215

luogu 70+100+60+60 = 290

感觉自己实力内的最理想成绩大概是 100+100+60+20=280 吧，可惜没有如果。

测了本机房，有一位今年考了 NOI 的同学有 270+。

听同学说把同省学校也稍微测了一下，据说考的不错。

感觉有点寄，GX 一等奖可能有，但要在 NOIP 考出成绩还要加油吧。

upd: 在脚造数据下拿到了 301 。