CSP高分说 | 四川大学王鹏超：算法竞赛为人生增添了色彩

我常常追忆过去。

虽然我小学时就了解过一些C#，但是我接触算法竞赛是在初中。那是初一的十月，易娜教练在一节信息技术课堂上说我们会举办信息学奥林匹克竞赛（OI）校队的选拔，会笔试（里面考了类似于栈之类的知识）进行选拔。当时我对于是否报名还有一丝举棋不定，抱着去看一眼题的心态就跟着大家举手报名了。

并不是因为热爱，也不是因为能用电脑打游戏或者家长促使。而是因为偶然，我做出了OI的人生抉择，从而打开了新世界的大门。如同童话里的爱丽丝追逐兔子掉进兔子洞，我走进了如梦似幻的OI。

时光飞逝。一开始的选拔仅我们班就有29人报名，到半年多后我们班只剩下4个人，再到2019年时我们年级只剩下4个人。我也逐渐加深了对新知识的渴望，从求水仙数，到讲完语法课后学习的第一堂课——枚举和模拟，再到报名参加NOIP普及组。在初一初二，虽然教练教学进度稍慢，但是他们带我初次从算法竞赛获得了快乐，我也越来越投入其中。

第一次寒假训练，学习数组前易娜教练布置的作业（截图于2018年2月6日）

一开始除了同机房的选手外我还并未接触算法竞赛社群，直到2019年暑假，我来到了我的高中集训，才发现此前我对算法竞赛的了解不过是管中窥豹。集训过程中，我仿佛大山中的孩子第一次走出来一样，第一次听说树状数组、线段树，也开始使用一些校外的算法竞赛网站，并由此在此后陆续结识到了一些友善的和我同样热衷于算法竞赛的选手。但更多的仍是线下的友谊，比如来自南充高级中学等学校的许多同学也和我一样暑假来集训了，但更著名的是蒋凌宇学长（网名jiangly，IOI 2021候选队，第46届ICPC World Finals总冠军）。他是个奇迹般的人物，我也从同学那里听说过他刚开始学习算法竞赛时也有非常强的学习力，他开始学习算法竞赛时比我大得多，刚开始学习不久就能把模拟赛提前AK（做出所有题目）了，NOIP 2018提高组时在ST（稀疏表）都没学习的情况下就取得了506分的佳绩，而这个暑假他就会去NOI 2019了。结果亦是令人喜悦的，当蒋凌宇学长和潘玉斌教练的捷报从广州传来时，整个机房都沸腾了，大家也备受鼓舞。

这些情谊给了我很大的帮助，也成为了我在遭遇挫折与考验后仍然能坚持算法竞赛的支柱之一。虽然我高中未能在OI中取得理想的成绩，但我大学方才入学就重拾训练准备继续参加算法竞赛，一部分就是为了这些友情。虽然仍然会有比赛发挥不理想而沮丧的时候，但参加比赛前后与同样热爱算法竞赛的网友线下见面团建并一起旅游就非常让人心驰神往。因此，我也报名了许多比赛，包括这次专业级CCF CSP认证以参加接下来的CCSP竞赛（CSP达200分才能报名当年的CCSP）。

2024年ICPC上海站获奖证书，由于种种失误遗憾未能出线（获得参加World Finals的资格），获得了金奖第7名。

在CSP的前一天晚上，我参加了一场Codeforces比赛，那场比赛中，由于许多使用AI作弊的人通过了G题到了榜单前排，导致了我排名很靠后掉了许多分（rating），然后半夜陷入了depressed的状态。我凌晨4点多才睡觉，所幸白天我的状态并未受到影响。

本次认证中，第1题即使相对于往年的第1题来看也偏简单，题面已经给了计算公式，只需要数输入的点中数距离满足要求的点即可。第2题是一道思路比实现简单的与模式匹配有关的题。我首先写了个O(n^5)的做法结果TLE（时间超限）了只有80分，然后试图用std::bitset来优化结果发现效果不佳，还是只有80分，因为std::bitset并不支持快速取出一段来，我试图直接操作整个std::bitset导致的。当我为“怎么取出一段”愁眉苦眼时，我观察到了每次只修改有改变的行的掩码均摊复杂度是可接受的。我实际实现时写了个和Rabin-Karp滚动哈希差不多的代码。通过此题时，我发现了我已经浪费了快20分钟。

第3题是一道大模拟题，不过我的实现较为顺利。所幸我在翻阅题面查看数据时注意到了此题最下面已经给了哈夫曼树的实现，节省了许多时间。我首先写了个不含decode的部分分，交上去验证后便直接开始实现。然后我大约在14:48通过了此题。

通过第3题后我开始阅读第4题。我一开始没看到只在题目背景里一笔带过和最下面的数据范围constraint里的a是permutation，认为需要写个树上莫队（该算法在序列上的版本因莫涛总结其trick提出而得名）或者可持久化线段树（此做法并不正确，我赛后发现基于可持久化线段树的做法是假的，实际上可以作个归约证明没有限制的这个问题是不比矩阵乘法弱的，所以任何试图想出q*polylog(n)的努力基本都是徒劳的）。然后我就先放下去看第5题了。

第5题题意大致如下：现有n对元素(a_i,b_i)，欲准备一道题，第一个人需要选一天i花费a_i的代价出题，第二个人需要选一天j(j>=i)会花费b_j的代价验题，一个人选了一天后就不会再选，求两人代价和<=m(m<=10^18)时最多能准备好几道题。我一上来就发现了这题的凸性，然后头脑里立马浮现起了这类问题的常见建模。这题貌似能用wqs（王钦石）二分以O(n*log(n)*log(m))的复杂度解决，不过最后一个subtask看着跑不过去（实际上赛后我听说其他通过了本题的人大多数写了O(n*log(n)*log(m))的wqs二分），于是我又想到了模拟费用流。建了一下图，发现建的图还挺简单，看着挺像模板题的，但我之前从来没写过模拟费用流相关题目，没直接想到模拟费用流可能就是因为对此的生疏。可能没直接想到模拟费用流是因为我之前从来没写过模拟费用流导致的生疏。于是，我凭借着“这种题要用线段树”的浮光掠影开始“自研”，最后“自研”出了线段树维护的信息以及合并方式，然后剩下的线段树和主函数部分就很好写了。我写完过了样例就交，可是WA（Wrong Answer）了。这种线段树维护的东西一复杂的题写错也难免，而且代码冗长不易观察出错误，所以我尝试编写暴力以进行对拍（即stress testing）。所幸是IOI赛制，我暴力写错了很多次，不过因为能实时看到第一个子任务的结果所以能借助评测机在拍之前知道自己写的暴力对不对。在拍的时候我也发现我犯了许多低级错误，比如因为草稿纸上有个地方a和b画反了导致有个地方的式子写的驴唇不对马嘴，看来之前没写过模拟费用流的题很生疏真的很吃亏。最后大概在16:40通过了本题。

然后回到之前未解决的第4题。我一直在冥思苦想有无更好写的做法，直到时间快不够了决定先写暴力。在写暴力途中，我往下翻阅子任务的数据范围时才看到a是permutation的constraint。这类套路十分经典，我在第48届ICPC国际大学生程序设计竞赛区域赛杭州站还亲眼所见过，不过那次的题面和输入格式里都有句加粗的“All the values are pairwise distinct”，导致我当时一眼就发现了。不过在做这题的时候我并未发现，在最后时刻才发现，可惜写不完了，只写了个基于std::bitset的50分暴力，很遗憾地与本次CSP认证的满分失之交臂。

第39次CSP认证考试成绩部分截图

为什么有的算法竞赛选手在短短的时间内就鹤立鸡群，取得了令人瞩目的成就呢？窃以为在有效利用的训练时间和训练方法上做文章就切中了肯綮。

对于前者来说，专注于训练。只要决定了要参加算法竞赛，通常需要大量的训练，提升专注度以及找到正确的训练方法以最大化训练效率对高效提升水平很有帮助。另外大家可能会感觉到可利用的时间过少且过于碎片化，此时大家要学会合理评估大学各门课程的重要性。例如我认识的一位ICPC World Finals东亚冠军队的一位大学零基础选手，就是通过学会合理评估大学各门课程的重要性，从而挤出训练时间并以高速率提升自己的水平的。

另外就是不同比赛之间优良的比赛策略通常有一定差别；此外，不同比赛命题组的出题风格和出现出题失误的概率也存在一定的差别；而且团队比赛可以通过让队员掌握互补的知识，从而不要求每个人都“全栈”，而个人比赛并没有队友，因此必须一个人承担所有题目，遇到不会的偏僻知识点只能舍弃这道题去看别的题。因此，在XCPC等团队比赛适用的策略也可能不完全能在CSP、CCSP等个人比赛中照搬，在其中一类比赛中取得较好成绩也不能掉以轻心地认为在另一类比赛中也一定会取得优秀的成绩。例如，团队比赛中和队友的配合尤其重要，而个人比赛中发挥的稳定度尤其重要。限于篇幅不可能在本文中准确提到我的所有比赛方法，大家可以在训练后自行复盘总结适合自己且扬长避短的一套方法。

还有一点，就是永不言弃。对于一个挤出时间竭尽全力地备考算法竞赛的高中生或大学生来说，理论上可利用的时间是完全充足的。只要还没退役（因为年龄或离开学校等原因失去参赛资格），经过刻苦训练后下个赛季很可能能东山再起。如果遇到困难或沮丧了，想想算法竞赛社群里自己仍有这么多朋友正在陪自己一起披荆斩棘般地训练，可以与他们交流。大家需要在备考算法竞赛时保持合适、良好的心态，既不要把失败看得过于沉重，也不要觉得算法竞赛没有什么用就自暴自弃，算法竞赛通常是通往教培、开发、深造等去向的垫脚石，并且在大多数情况下效果通常比在大学课程绩点方面进行徒劳“内卷”好得多。例如知名算法竞赛选手组合赵予唯、沈航、朱智睿，他们三人的年龄有很大的差别，但他们参加算法竞赛后的去向令人难以望其项背。

上述这三人中最年长的赵予唯选手（网名炸鸡块君）于2021年成功预推免至北京航空航天大学读硕，期间发表过NLP领域顶会论文，此后虽多次在大厂实习、获得offer，也申请过香港科技大学（广州）的博士研究生并拿到offer，但最终决定参与OI的教培工作，先后在北京市第四中学、清华大学附属中学实习并取得留用offer，以说话幽默风趣而闻名。赵予唯使用下图中的账号在国际性质的比赛牛客多校2024第五场中获得F题一血（最快解题奖）。

沈航选手于大三成功进入某知名大厂的某核心事业群，下图为他讲解算法竞赛的生成函数相关题目的截图。

朱智睿是三人中最年轻的选手，算法竞赛水平优秀但在部分重要比赛中遗憾发挥失误，曾前往某头部人工智能科技企业参与实习。下图是他参与CCF经验分享时的介绍图，在各个社群内拥有较高的转发量。

感谢CCF举办的CSP系列认证考试和信息学奥林匹克竞赛，让我得以窥见算法世界之美。希望和我一样热衷于算法竞赛的大家都能取得满意的成绩。