CSP满分说 | 天津大学李国鸿：我的算法竞赛和CSP经验

我第一次接触编程是在初三后的暑假，当时刷信息学奥赛一本通的OJ来学习C++的语法基础，然后自己用简单的分支结构和函数去写一些像贪吃蛇、文字冒险这样的小游戏。在这一过程中，我学着去使用栈和队列等数据结构，并产生了对于编程和算法的兴趣。

初三时候写的贪吃蛇小游戏

我所在的高中是所具有竞赛底蕴的学校，在身边都是竞赛高手云集的环境下，我也开始尝试参加算法竞赛。由于经验不足，高一上学期第一次参赛时，我只拿到了CSP-J的奖项，但我并没有气馁。经过一年的努力，我获得了CSP-S、NOIP的一等奖，NOI冬令营的金牌，并顺利以综合成绩第一进入NOI天津代表队。

 高中期间所获奖项

在算法强手云集的浙江余姚NOI现场，我见识到了更广阔的天地。可惜个人实力不足，没能取得理想成绩的我只能回到课堂准备高考。于是我高中阶段的算法竞赛就这样草草收尾。

 在NOI2021现场，右一

进入大学后，得益于天津大学宽松的转专业制度，我顺利在大一下转入计算机科学与技术专业。在这里，我和其他优秀的选手作伴，一同交流学习，并重新踏上了算法竞赛之路。这半年里，我和队友征战全国各个赛站，共计4次获得ICPC/CCPC银奖。

 本科期间所获奖项

 在EC Final，左二

这次的CSP认证是4个小时做5道题目，采用即时反馈测试结果的赛制。

前两道只需要掌握基础语法模拟题意，比如用C++ 中的STL。

第三道是一个稍微麻烦些的模拟题，于是我暂时跳过去看后两道题。

第四道题数据范围较大因此需要离散化，注意到数据保证了有值的位置不会凭空增多，于是将这些位置用链表连接起来，维护前驱后继，再模拟题意操作。

第五道题一般会用到一些更高级的算法。像这次的题目，将操作分开考虑，对于修改可以用启发式合并维护，而它对到根的距离查询的影响，则可以转化为子树的权值减一，于是利用dfs序和树状数组即可解决。

这时回过头去看第三题，先写一个字符串处理的步骤，得到一个矩阵，然后按题面所给算法做高斯消元计算矩阵的秩，结合线性代数知识，即可判断齐次线性方程组的解是否唯一。写这种稍复杂的模拟需要细心一些，不过由于此时时间充裕，便能够心态良好地慢慢写完并一次通过。

CSP认证的考试并不会用到太多高难度的算法，所以即使是没有算法竞赛经验的选手也能获得不错的成绩。在对所选语言基本语法熟练掌握的基础上，了解一些算法和数据结构相关的知识，并能正确判断算法时间复杂度，也有助于在认证中得到更高的分数。

除了对算法的掌握，一定的思维训练可以使自己更敏锐地反应出题目性质和解决思路。可以尝试打一打Atcoder和Codeforces上的比赛，这些题目通常不需要太多前置知识，主要考察能否熟练应用简单算法解决问题。

关于比赛本身，因为是即时反馈的IOI赛制，所以不用担心在不知情的情况下挂分。

CSP认证是允许携带纸质材料的，可以提前打印一些自己熟悉的算法和数据结构模板，或是不方便记忆的数学性质和结论。

开题的顺序是自由的，发现某道题目不太好做可以暂时跳过或者只写部分分。这次CSP认证考试中，我将不太好处理的模拟留到了最后，使得自己有充足的时间应对不擅长的题目。

要仔细观察数据范围，考虑时间复杂度是否允许通过，经验上讲如果粗略估计计算次数超过1e9则可以考虑算法的优化。此外数据性质也可能会提示做法，比如注意到这次的第四题的数据性质，就使得我可以用一种比较简单的做法通过。

尽管IOI赛制允许猜测结论并提交尝试，但我个人习惯是先把细节想清楚，包括性质证明和算法流程，再动手写代码，以避免陷入代码写成后再反复修改BUG的窘境。

算法的巧妙令人着迷，而 CSP 认证的举办也让算法之美为更多人所知。

受算法竞赛经历影响，我现在也在辅修数学双学位，试图对算法背后的数学原理有更深刻的理解。祝愿 CSP 能越办越好，让更多选手提升自己的能力，展现自己的风采。