CSP满分说 | 南京理工沈培森：从CCF开始的算法之旅

我从大学开始接触算法竞赛，CSP可以算是我的算法路上不可或缺的一部分，在备战CSP的过程中，我经历了许多挫折和困难。2022年6月，我参加了第26次CSP认证，也是我第一次参加，我在前两题上表现不错，但第三题让我束手无策，最终获得了220分，并因此加入了南京理工大学的ACM-ICPC集训队，系统地学习算法，并参加比赛积累经验，开始了我大学四年的算法竞赛之旅。在大三上学期，我拿到了ICPC南京站的银牌，这让我找到了自信。

2023年ICPC南京站现场 右一为沈培森

后来，我报名参加了第32次CSP认证，刷题进展顺利，但考前的ICPC济南站中，我们队以几名之差错失银牌。同时考试中第三题再次让我困扰。考试结束后，我倍感疲惫和失落。然而，在ICPC队友的鼓励下，我重新振作起来，并报名参加了第33次CSP认证。考前两天，我碰到一道关于树上启发式合并的题目，是一个我从未接触过的算法。当时的我怎么也想不到考试会涉及到它。经过两天的努力，我终于在考试当天凌晨三点找到了最后一处bug并完成了题目。

 沈培森在宿舍写代码

在考试中，第一二题过得很顺利，来到了困扰我两年的第三题。幸运女神似乎终于眷顾我，这题正好是关于高斯消元的字符串模拟，而我准备的资料里刚好有高斯消元的代码模板。那么只要完成数据处理，然后对高斯消元模板微调一下应该就可以了。我模拟了一下矩阵形成的过程，并轻松地拿到了第三题的满分。

第四题是关于水滴爆炸的题目，需要快速找到水滴左右两边的水滴，用set容器存储水滴的位置，每次log查找水滴的位置，用迭代器log搜索左右两边的水滴，把即将爆炸的水滴存到优先队列里依次处理，即可满足题目的要求。我细心地写完了代码并测试样例，成功通过了第四题。

来到第五题，我内心充满激动。这题可以分为两个子问题，第一个是合并操作，第二个是删点维护深度。第一个子问题我选择暴力合并，第二个子问题，我很快想到了树链剖分加线段树的算法，这正是我在寒假刚学的。我迅速写完了代码却发现有几个点空间爆炸，只得了55分。在一次次检查中，我发现执行合并操作时，每次最差要O(n)的时间，q次询问则最坏有O(nq)的时间复杂度，显然是会超时的。这虽然看上去和空间没关系，但我还是运用树上启发式合并对其进行优化。提交后，我紧张地等待测试结果。当看到“100正确”的字样，我激动地喊了一声“yes！”。这一刻，我感到非常兴奋，仿佛一场梦。确认自己真的拿到了满分后，我再次喊了一声“yes！”，看看时间，还有两分钟到三个小时。

 沈培森CSP满分成绩单截图

1.正确认识CSP认证。CSP前两题都是比较基础的，只涉及一些简单的算法以及STL容器。第三题是一道大模拟，对思维要求不高，但需要较强的代码能力。第四第五题会涉及一些较难的算法，需要一定的竞赛基础。

2.多写题，多学算法。努力是通往成功的唯一捷径，也是我们唯一所能做的事情，是分数上一台阶的突破口。所有的实力都是通过一道道题目的积累得来的。我们需要根据自己的薄弱环节，有重点的努力，努力填补自己的不足。

3.坚持不放弃的心态。在我经历前两次CSP失败的时候，如果选择放弃，我就无法欣赏到我现在500分的成果，甚至无法接触到算法竞赛这条充满挑战的道路。人生中总是充满了失败、坎坷，在面对这些困难时，坚持不放弃的心态可以帮助我们保持积极的态度和动力，努力度过人生的“阴天”。

非常感谢CCF能给我这个分享自己算法竞赛经验的机会。参加CSP认证无疑是对自身代码、算法水平的一次检验，能很好的体现自身的优势与不足。最后祝CCF能越办越好，同学们也能在CSP认证中取得自己满意的成绩。