CSP高分说 | 武汉大学徐嘉浩：热爱不止于此——我的算法之旅

我最早接触算法竞赛是在小学五年级，当时受到身边同学和家长的影响，报名参加了一个名叫"信奥"的兴趣班。那时我们使用的还是Pascal语言，我从中学会了一些分支和循环语句。初中时，我了解到CCF举办的NOIP比赛，并从那时起正式开始学习算法，成为了一名OIer。在初一的一年里，我学习了许多算法，例如深搜、广搜、二分、动态规划等等，初步领略到了算法的美妙，并开始投入更多时间进行刷题。随后，在初二和初三时，我顺利获得了NOIP普及组的一等奖和提高组的二等奖。在绍兴一中的信息竞赛选拔中，我也以第一名的成绩顺利通过。

然而，在高中时期，我的竞赛表现并不如意。由于一些低级失误，我在高一和高二这两年仅以联赛二等奖收尾。尽管如此，我对算法竞赛的热爱仍然持续着，即使在学习文化课的期间，我也会抽出时间去思考一些算法问题。终于，在NOIP2021上，我正常发挥，获得了一等奖。这次的成功让我更加坚定了继续追求算法竞赛的决心，同时也让我认识到失败并不是终点，而是一个成长的机会。

在大学期间，我早早地加入了ACM集训队，继续着我的算法竞赛之旅。在董文永老师的悉心指导下，我和队友在经历了合肥站的第36名（银奖第一）后及时调整，最终在ICPC南京区域赛上获得了金奖。在接下来的一年里，我经历了队友退役、队伍重组，但仍取得了较不错的成绩：两枚ICPC区域赛金奖，一枚EC Final银奖，一枚CCPC区域赛银奖以及湖北省赛的季军。除了参加XCPC系列比赛外，我还积极参与了许多CCF举办的比赛，如第27次和第32次CSP认证以及2022年CCSP竞赛。CCSP竞赛独特的赛制和题目开拓了我的视野，让我见识到了算法的多样性和实用性。这些经历不仅丰富了我的知识，也让我更加深入地理解了算法的应用价值。

参加2023ICPC济南站与队友的合照，左一为徐嘉浩

CSP认证包含5道题目，每道题目满分100分，有多个测试点，每通过一个测试点会获得相应分数。选手需要在4小时的时间里，尽可能获得更高的分数。CSP认证是IOI赛制，也就是说每道题可以多次提交，实时评测，最后取最好成绩。

题目方面，5道题的难度是由易到难的。前两题较为简单，考察的知识点往往是模拟和枚举，有时会涉及非常简单的动态规划。这两题的代码量通常较短，选手需要在考场上尽快通过，为后面三题留下充足时间。

第三题一般是一道较为复杂的模拟题，思维难度不大，但代码难度很大。题目往往以计算机相关的知识或现实生活中的问题为背景，要求选手模拟一系列过程。题面很长，细节很多，需要选手静下心来慢慢写，慢慢调试。准备这类题目的话，只能多去刷一些代码量大的题目。写题之前多思考各个环节之间的关系和顺序，可以先在纸上将整个流程写一遍。

第四题和第五题主要涉及数据结构，在思维和代码两个方面都难度拉满。选手不仅需要对众多数据结构有较深的理解，还需要有较强的码力来实现。例如，在第27次CSP认证中，第四题的解法涉及并查集和珂朵莉树，第五道题的解法则是树状数组维护李超树，思维难度很高，代码量很大。针对这两道题，一个比较好的选择就是先考虑部分分，尽量多的获得分数，然后再冲击满分正解。部分分的难易程度是有梯度的，而且往往会是正解的重要提示。

需要注意的是，CSP认证是可以携带纸质资料的，从以前只允许书籍，到现在可以是打印和手写的资料。因此，选手可以提前准备各种知识点的模板和参考资料，并将其带入考场以备不时之需。CSP认证使用的电脑系统是Ubuntu，且会提供vscode等代码编写工具。建议选手提前熟悉认证环境，学会如何配置自己熟悉的工具，以便更高效地编写代码。

武大新生赛讲题

在第32次CSP认证中，我非常顺利地通过了前两题。第一题“仓库规划”简单枚举即可，第二题“因子化简”考察了根号枚举因子的方法。然而，在第三道题目上我遇到了一些小问题。本应是一道大码量的模拟题，但是我没有观察到一些性质，错误地认为简单模拟每个询问的复杂度太高。因此，我选择了整体处理询问的方法，浪费了很多时间。

第四题和第五题比较难。我在两题之间反复横跳，思考了一段时间无果后，选择了尽可能多的获得部分分。第四题的撤销操作让我很是头疼，一直找不到好的解决方法。于是，我先获得了O(n^2)模拟的35分，然后通过线段树维护矩阵乘法，获得了没有撤销操作的20分。虽然在最后时刻我想到了倒着处理可以有效解决撤销操作，然后就可以用分块来维护，但遗憾的是已经没有时间来让我完成这题了。至于第五题，第一档特殊性质的20分可以通过简单的动态规划实现，第二档K<=15的30分则可以通过状压DP获得。尽管只是第二档部分分，但是其中的实现细节也很多。

非常感谢CCF提供这次机会，能让我分享自己的竞赛经历和经验。同时也非常感谢CSP认证，始终保持高质量的题目，为广大计算机学生提供了一个测试代码水平的平台。最后，希望CSP和CCSP能够不断发展壮大，吸引更多的学生接触算法，提高代码能力。