CSP2022 游寄

· · 个人记录

2022 是整活的一年。

第一轮

day -?

铺天盖地的初赛，铺天盖地的初赛，铺天盖地的初赛！

有些比较 ez，但是引荐的很多，有些计算量很大。

但是台风偷袭，被迫留在学校，做引荐模拟赛。

day 0

完全没有想到初赛在周日呢！

周六看了一眼之前的模拟赛卷，然后复习了一些初赛基础知识。

（然而没有复习完，几次模拟赛考基础知识都错了一堆，我很害怕）

发现晚上有 ABC，打了一打，由于当时比较寻宝所以真的只过了 ABC（棕名号没有下分）然后离场，继续复习初赛。

day 1

上午睡大觉，摆烂。

有引荐教练要求 12：30 到学校机房（考点在学校），但是我 1：00 到。

然后跟机房人员嘴巴，大胆猜测今年的考试题。

毕竟去年的引荐 \verb!base64! 和四毛子阴掉了不少人。

有人在看上午 \verb!J! 组试卷，发现难度大幅度降低，而且在洛谷捉虫（比如如何定义有向图的“连通”，是强连通还是弱连通还是中国联通）。

洛谷上传出了类似于“\verb!ZJ J!组分数线上 90 的（谣言 or 暴论）”，机房里也有人这么认为，我谈笑风生地说：不可能上 90 的。

这个时候大家依然认为 \verb!S! 组的试卷很正常。

下午考试。

考场一堆巨爷。

看了一眼试卷，发现了 time 这种冷门的东西，大概猜了个答案上去。

引荐的在后面。

看到那道“作业”，一眼以为是 C_8^2=28，检查的时候才发现理解错了，但是发现选项里面没有正确答案（害怕），就还是选了 28。

然后就是奇妙的 for(int j=0;j<=i;j*=2) 一开始我还没看出来死循环，当成 log 算，老师改了才反应过来。

宇宙射线真好玩。

发现选择题比去年简单，检查一下后直接进入阅读程序。

第一题手摸后发现挺水的，但是当时认为那个东西复杂度是对的，没有构造出卡成 \Theta(nm) 的数据，白送 3 分。

第二题一眼基数排序，但是块长选错了，白给（今年怎么这么多基数排序）

第三题负数取模，推了好久才发现可以变成 -k 进制表示，一开始十分纠结负数取模的结果。

但是进入完善程序就剩下 15\min 了，害怕，于是后面全部蒙的……

day ？

中间一堆恐怖新闻：\verb!ZJ! 机位减少至 400 个。

我当时害怕极了：因为我是机房垫底。

还好最后变成了：保底 600，最多 1100。

查分 78.5。稳进。

第二轮

day -？

铺天盖地的模拟赛！铺天盖地的模拟赛！铺天盖地的模拟赛！铺天盖地的模拟赛！铺天盖地的模拟赛！铺天盖地的模拟赛！铺天盖地的模拟赛！铺天盖地的模拟赛！铺天盖地的模拟赛！

最好打到 rk10，爆蛋 2 次，但是每次都打的暴力，菜死了。

同机房的猫猫 @lanos212 天天前 5，我狂暴膜拜。

有些模拟赛感觉质量挺高的，有些稍微难一点但挺有意思，有些在 \verb!T1! 放“德州消消乐”，直接爆蛋。

day 0

考试前一天还有模拟赛，害怕。

下午还得订正，害怕。

上午发了个 \verb!CF! 帖，加了一车贡献分。

\verb!CSP rp++!!

day 1

上午摆烂，然后很早就去杭州了。

中午杭师大对面的麦当劳人很多，于是就去旁边吃了鸡米饭，结果撞到了@zqxakioi，聊了一会（没有嘴题），结果发现核酸的阴性报告打的不一样，还去补打了一张。

去路口看上午 J 组考完的人，遇到了@fisheadAKIOI 和 @Gold14526 ，但是马上就润了捏。

看了一眼 J 组题目，怎么又有模拟（，不过大部分人都自我感觉良好，而且@Tx_Lcy 1\min 嘴巴 AK 了,我很害怕。

没有遇到本来想找我面基的@husy 和 @Aslf_Ek ，但是碰到了 xzy（单调队列人）。

考场门口很热闹，一车绍一人，有人还锕起来了，害怕。 没有嘴巴因为比较菜没什么好嘴的，但是押了一手 T4 图论，顺便聊了几个 trick（吗，真的吗）。

杭师大门口的小河，很干，很让人流泪，有一种心碎的感觉，如果爆蛋了还可以直接一跃解千愁。 不过旁边的几颗柳树依旧温暖人心，石拱桥拱起了考生们心中的希望，远处的楼宇以柳枝拂面，若隐若现，虽处大学之中，仍有古城小巷之韵。

因为怕饿所以蹭了点别人吃的。

进考场。

绕了好久才找到自己的座位，中途发现了@Laser_Crystal 。

但是杭师大的老师怎么这么喜欢叭叭，重复不知道多少遍没用的话。

考场很明亮，很宽敞，丝毫不压抑，在这里面考人不会感受到紧张，除非刚开赛你就听到狂暴如雨的代码声。

2:30，开题！

密码是 Belief2022，结果大小写错了，乐，回来查了一下百度发现 Belief 是“相信”的意思，CCF 居然鼓励大家了，泪目。

大致看了一眼题，怎么 T1，T3 都是图论，T4 是一棵树，只有 T2看上去另类一点，图论比赛最大的好处就是容易爆搜骗分（雾）。

开 \verb!T1!，一开始以为是“总转车次数不超过 k”，心想我怎么 T1 都要挂了，结果手玩样例才发现是“最大转车次数不超过 k”，白白花费了近 20\min。

先光速打了个 n轮 bfs全源最短路，然后把问题拍成：求一个包含 1 号节点的五元环使得点权和最大，打了一个奇怪的东西，结果算重了，白给。

想了一会没有想到在 O(n^2) 左右的算法，于是愤怒地把所有出边按照点权从大到小排序，然后加了一手卡时，过了大样例。

据说结论是取前几大的点更新，那这个卡时只要没有 \verb!TLE! 应该能草过去（吧）。

开 \verb!T2!，一开始看到题面我只想说博弈论是 9 级内容！，发现好像是个 \verb!RMQ! 板子题，猜了一手结论，当场上了 4 个 \verb!ST! 表维护 \max,\min。

结果小样例就萎了，重新手玩后发现 4 个不够，而且可能需要引荐分类讨论，于是又一怒之下开到了 8 个，由于不想写分类讨论，于是直接把所有情况装到一起暴力算，喜提 25 倍常数，关了同步后本地不开 \verb!O2! 0.6s 过大样例，海星，不知道用线段树维护的有没有爆常数。

看 T3：

你说的对，但是 \verb!CSP! 是一款由 \verb!CCF! 开发的星际战略游戏，在这里名叫“考生”的玩家需要操控星际战舰，抵御宇宙射线，维护自己的据点，防御来自敌军战舰的轰炸，并在虫洞之间来回穿梭，对敌军发动反击，实现全面大反攻。

题面那么长读了半天

发现操作实际上就是：

  1. 删，加边
  2. 删，加某个点的入边

并询问是否每个点的出度都是 1。

第一个操作直接乱搞就可以了，但是想不到第二个操作怎么维护，无奈之下只能暴力删加边。不过我用了 DS 维护全局出度，因此询问复杂度没有问题。

我们要相信官方数据，即使你的算法会被卡，我们也要坚信数据足够水，我认为，官方数据绝对不可能卡满菊花图，必然会存在随机的图。而这样，我们就能获得比预期更高的分数！

滑稽，能打正解还是要打正解。

但是我是时间混乱 die 师，您猜怎么着？我 \verb!T4! 只剩下 30\min 了！

原因：\verb!T1! 读错题浪费时间，\verb!T2! 猜错结论浪费时间，\verb!T3! 修改时没有 & 传引用没看出来，浪费不少时间。真正打题的时间只有一点点。

于是挑战速通 $\verb!T4!$ 暴力，结果修完编译就到时间了，当场去世。 说句闲话，考场上有个人左顾右盼，被警告了。 出考场时碰到了@ethan090328 和 @fisheadAKIOI，他们说自己考的都不好。@djwj223 说自己 $\verb!T1!$ 的 $O(n^2\log n)$ 死活卡常卡不进去，有点震惊。 回家时顺便载上 @cyfff 发现他前三题都会，但是一直都说要fst，我很害怕。 路上看了一眼 $\verb!QQ!$，@Mine_King 一开始说自己 $300+$，然后又说自己 fst 了，然后自测又出来 $\verb!T1!\ 95$，害怕。 但是看了一会手机就没电了，焯。 蹭了一下 @cyfff 的手机，顺便路上嘴了不少东西，发现他把我吊起来打。 回家估分，@Tx_Lcy 说他$\verb!T2!$ 把 $n,m$ 打错了，f 光了，默哀。 群上一车 $300+$，白给。 自测：$70/100+100+60+0=230/260$（infoj 怎么把我$\verb!T1 TLE!$了![](https://啧.tk/jk)） 又垫底了。 ### day 3 可爱的@Mine_King 像一只波特一样挨个问所有人的成绩，发现我真的垫底了。 ### day ？ 出分了： $100+100+60+0=260

跟预期一样，但是完全没有吃到 \rm CCF 的数据红利。

但是 2022 是整活的一年