返回

随笔杂谈 | CSP-S 2023 复赛游记

前传

随笔杂谈 | CSP-S 2023 初赛游记

游记

day ~-22

初赛回来后,进行了深刻的反思。

我怀疑我的基础并不是很牢,于是开始尝试去打新手村。

直到国庆节前的这段时间其实大部分时间真的去打了,貌似打了近百道,打到 bfs 了,也不清楚具体打到了多少。(upd:后面才知道原来新手村有题单,一直是对着剪贴板做的)

day -22~-9

国庆后,新手村就先停下了。

倒不是因为我觉得写简单题太无聊,而是因为我洛谷网校在国庆有课,这段时间基本是在跟着秋令营的课和题单慢慢做,慢慢学。

这让我想起来之前多校联训的课也是要补的,基本上我只跟着学了个莫队后基本一直处在挂机状态了。

(upd:这很不对。我不应该这样,花了钱报了课最后又没听进去,最后没有好结果的还是我自己。)

顺带一提,这段时间还拿了一道黑题的最优解,还写了我的第一道题解 P4480 [BJWC2018] 餐巾计划问题,算是一个里程碑了!

其实这段时间没有专心搞 OI,因为这段时间的最后两天要考月考。我一直认为竞赛和 whk 之前不得不有一个平衡,否则两个都搞不好,而我确实没办法承担丢下 whk 后可能带来的后果(upd:停课真爽,不想上学了)。

不得不分心去复习一下,至少 whk 不能丢下太多,想保持在重点班第 5, 6 名左右的位置已经让我感到吃力了,但最后考试结果还是在接受范围内。

day -8~-1

考完试之后,这段时间基本就在停课了。

最初我还是很认真的一直打模板、补充知识点,到后来又出现老毛病了——越到关头越松懈,反而一天天开始摸鱼越来越频繁了。

最开始只是打打音游(说起来,由于换了个网,打不开之前的 4K 音游了,于是换了个 5K 的音游,之前一直不习惯空格,现在已经能打的比较顺了,fc 了 YOASOBI 的两首曲子的中等难度),后来大家在机房里翻到了不知道什么团体之前使用机房留下来的 cs1.6(这个机房没有冰点还原),于是信竞就真的变成电竞了。

当然我还是有保证一定量的做题的。

貌似我初赛之后也是这个样子的?下次绝对不会再这样了。

这段时间我同时还自己出了四道 ds 模板题,拿来出校测,还是蛮有意思的一次出题体验。当然,为了不让题目太板,我每个都在板的基础上加了点需要思考的内容,同时也给自己拓宽了一点想法(比如线段树新增一种特殊的懒标记、树剖搭配树状数组之类的)

后来因为办的不错,教练要求再加一场,于是从洛谷选了四题我自己做过的感觉比较有学习价值(增加了我的 trick 的那种)的题目。

另外这段期间,做了超多模板题,包括 Nim 游戏、各种基础数据结构和图论,以及补了很多提高级范围内的数论!(但最后如我所料,一点没用上)

到最后一天为止,终于完成了我计划内的所有模板题,包括最长的树剖以及最不熟练的 splay,顺带修了下很久之前写的 splay 的错误然后过了数据加强版。(所以现在我觉得我的 splay 熟练很多了,但做题还是不一定看得出来)

day 0

上午又打了一遍 splay,看了一下对拍(直到这个时候我还是觉得我考场上有机会写对拍的)以及各种考前注意事项和骗分导论。

考场还是去年那个,很小,很烂,而且还不能带零食进考场。

开考时解压包密码还输错了一次,属于是开题不利了。

T1 看了几分钟,硬是没看懂题意,不过好在我见过一道类似的题目(给出 $n$ 个约束条件,求出原数的可能种数),还是差不多读明白了(upd:其实并没有)。

后来我注意到,其实只需要 $O(10^5n)$ 枚举然后 check 一下貌似就可以了,换句话说就是时间完全够用,所以立刻就开始动手写了。

然而悲惨的事,我题意有一部分理解错了,我以为他要求 $n$ 个状态都是同时滚两个滚出来的或者都是同时只滚一个滚出来的,这就导致我不仅花费了更多时间,写出来代码连第二个样例都没过,到最后都没想明白为什么第二个样例答案是 $10$。

我一直怀疑那个 $10$ 里面算上了两个状态本身,然而题目说状态本身不正确,所以我一度考虑特判 $n\gt1$ 时算上状态本身,但最后还是没这么写。(upd:谢天谢地我没改)

大约卡了一个半小时后,我决定先停下 T1,先把后面至少写点暴力先,等后面再回来调(upd:根本回不来)。

T2 看到串串题,再见!

T3 一看到题面就猜到大模拟了,虽然很烦但技术含量倒不高,有可能可以做,看了眼 T4 估计只写得出暴力,就打算先写一个小时 T3 了。读完题之后发现这个东西很复杂,但是我意外地没有什么阅读上的问题,都能读得懂,心里也大致对结构有一点想法了,于是就火速开始写。

其实我之所以敢冲大模拟而不是像大部分人一样见到大模拟就跳,是因为我一直以为我写过一道紫色大模拟题 [HNOI2004] FTP服务器 - 洛谷,我觉得这道题貌似没有那道难,最难的部分应该就是考察 STL 的应用以及操作三四的字符串处理了,刚好我都有在别的比赛中写过,感觉是能做的。(upd:后面回到家之后才发现其实那道题我还没写,一直躺在题单里面)

刚开始写,我的想法是维护类型的大小和对其要求以及他的成员,用 map 维护名字到类型 id 的对应,而初始时手动添加四个基本类型即可,很快就写完了操作一,而且操作一是一次性过的。

开始写操作二,一样的做法,维护变量的名字、类型和起始地址,用 map 维护名字到变量 id 的对应,很快写完了操作二,而且很神奇的也一次性过了。

由于莫名其妙的居然一点问题都没有,这时候就整个人是非常有信心的状态。

开始写操作三,这个涉及到一个字符串分割,幸运的是我应该是在最近一个月的某场 ABC 或者 CF 上写过这个,简单调试后很顺利的写出来了,剩下的操作其实就是顺着字符串进行一个递推搜索,累加答案,写完了简单调了会之后过掉了第一个样例,并且把第一个样例的每一个成员都做了下操作三,跟我纸上算出来的一模一样。这时候这一题已经写了超过 1h 了。

开始写操作四,这个也是跟上一题一样的思路,顺着地址进行一个递推,然后路上拼接字符串出答案即可。代码写得很乱,但是逻辑上觉得没问题,就这么写下去,最后调完过掉样例时已经过了 1.5h 了。我还对每一个地址都算了一下操作四,也跟我纸上算的一模一样。

这时候我已经过掉了第一个样例,非常的高兴,结果一测第二个样例,fc 出来好几行不同,当时心态都要崩了,写代码写的很乱,很不好调了已经。

幸运的是,仔细看了下第二个样例,发现还是比较简单的,在纸上模拟出来之后对程序进行了调试,发现是在下标计算啊大小对齐之类的问题,以及操作四判空那里漏判了一种情况。调了 20min,过掉了第二个样例。

这时候我高兴的去测大样例,fc 出来满屏的不同,命令行每滚动一行我的心里就像是被捅一刀,但是仔细看后发现我输出了负数!于是返回代码,把所有大小有关的变量开了llu,顺带还发现操作三漏掉了一个跟地址有关的变量没开llu。迅速的修改完之后,三个样例都过掉了!!!

虽然我很高兴,但高兴的同时时间只剩下 30min 了,而我除了 T3 之外只写了一道 T1,而且还没写出来。

这时候决定全力去冲剩下的暴力,T1 就丢掉了,相信能够拿到部分分。开始写 T2,第一个猜想是跟回文有关,似乎处理出每个点的长度为偶数的回文串的长度,然后对连续的回文串做个前缀就可以了,继而想到我一点也想不起来的 Manacher。

考场上几乎认定这是正解了,于是很难过,前几天想学的时候翻 OI Wiki 的时候想补 Manacher 但看到概念又觉得不会考最后还是放掉了,感觉很后悔。

于是我想着没办法了,打个暴力吧。但是可能是因为悲喜交加、时间紧迫、没有零食,导致我考场严重降智,竟然完全没想到枚举左端点然后用栈可以做到 $O(n^2)$ 的暴力,而是蠢蠢的写了一个 $O(n^2)$ 处理出所有偶数回文串后又 $O(n^3)$ 合并的鬼东西,而且还不知道哪里写错了,连第二个大样例都没过。(upd:考后发现是结论假了,合并做法是错误的)

看完 T4,我感觉有点贪心,因此脑子里也闪过二分的想法(因为刚做过一道三分答案后贪心的黑题,现在对于二分三分+贪心这种简单算法可以出难题是深信不疑的),但是很遗憾时间只剩几分钟了,于是我飞速的打了一个骗分,特判了一下 $n=1$ 的情况,其余就输出样例。

最后比赛结束的时候,一度感觉 AFO 了。毕竟本来是为了弥补去年的遗憾,才希望今年复赛拿个 1= 的,结果这次感觉考的比上次还差。

在校车上明白了 T1 我理解错的点了,发现如果我理解正确的话我写代码的时间应该还能短一半,感觉很亏。虽然确实是我的问题,但我还是强烈谴责 CCF 不给大样例,并且第二个样例没有任何解释,我觉得他哪怕给我一个 $10=8+2$ 我都能想出来。顺便我才发现 $n=1$ 的时候答案必定为 $81$,那我相信我能保下这个部分分,不爆零就意味着 NOIp 还有机会。(upd:今年高中生不是有分就行了,好在我最后考的还不算差)

另外 T2 我也觉得我能拿点部分分,不过看到有大佬的线性做法,感觉很震惊,但是看不懂代码!

发现很多人都跳了 T3,并且很多人说自己 T3 挂了,很害怕自己 T3 也挂分。

发现 T4 确实是排序后贪心,我宣布我精神上做出了 T4。

回家路上搞懂了 T2 的线性做法,类似于一个接受回文串的状态机,同时维护了连续回文串的数量(这里还是在坚持我的那个想法),到家后已经十点多了,今天可是周六耶?

考后估分:$30+20+100+0=150\text {pts}$,和去年一样的分数,估计没 1= 了。

后日谈

  • 10.21:回家后拿到代码自测了,T1 莫名奇妙在各大 OJ 都跑到了远超我预期的分数,T2 也很稳定都都反向挂了五分,T3 也运行的很稳没有挂,T4 也稳定的一分都没骗到!目前云斗估分:$90+25+100+0=215\text {pts}$,核桃估分:$80+25+100+0=205\text{pts}$,洛谷和小图灵还没出完整数据。

  • 10.22:洛谷估分:$70+25+100+0=195\text{pts}$,小图灵估分:$80+20+100+0=200\text{pts}$。没想到 T3 意外地很稳,一点都没挂,T4 依旧一分都没骗到。T2 有一点小浮动但和我预期的差不多,而 T1 就是一直在 $[70,90]$ 漂浮不定,基本是决定我这次的分数了。

  • 10.28:这段时间看了很多游记,同时 AK 了洛谷上的自测并写了些题解。看游记的时候学到了很多做法,同时也发现很多人都和我一样 T2 不会栈做法或者推出错误的结论,松了口气。另外看游记的时候又找到俩估分平台,计蒜客估分:$70+15+100+0=185\text{pts}$,信友队估分:$80+25+100+0=205\text{pts}$。然而 CCF 就是不出分,不知道要拖到什么时候。

  • 10.29:昨晚刚说完,今天一早就出分了:$80+25+100+0=205\text{pts}$,跟核桃和信友队上的估分一模一样。至少是上 $200$ 了,松了一口气。虽然我本就发挥的不好,但现在看来还不算很差。

  • 10.30:把这次比赛四道题的题解写完了。听说今年七级钩线很低,那我岂不是还有希望喜提七级钩!

附录

参考文献

  1. CSP-S 2023 Solutions

  2. 还有许多其他人的游记

版权信息

本文原载于reincarnatey.net,遵循CC BY-NC-SA 4.0协议,复制请保留原文出处。

本博客所有内容无特殊标注均为失迹原创内容,复制请保留原文出处。
Built with Hugo
Theme Stack designed by Jimmy, mod by Korita
© Licensed Under CC BY-NC-SA 4.0