CSP满分说 | 中山大学黄秋铭:如何备考算法竞赛

中山大学黄秋铭在第34次CSP认证考试中获得满分，第35次CSP认证考试将于9月22日举办，报名正在进行中。每年CSP高分考生（200分及以上）均可报名参加CCSP竞赛，CCF不定期邀请CSP高分和CCSP获奖选手分享经验，希望能够帮助同学们取得更大的进步。

非常欢迎更多CSP优秀学子分享自己的宝贵经验，联系：csp@ccf.org.cn

算法竞赛与我

小升初时，我第一次接触算法竞赛。通过深入的学习，我对算法竞赛产生了极大的兴趣，也参加了CSP-S、NOIP、APIO和WC等比赛并获得了一些奖项。虽然当时未能达到省队的标准，没能参加NOI的比赛，但是这也极大程度锻炼了我的思维能力并为我日后在大学中继续参加算法竞赛奠定了基础。

在进入中山大学后，我依然选择参加算法竞赛。在林瀚老师、张子臻老师和万海老师的指导下，我和我的队友参加了ICPC沈阳站和CCPC桂林站并取得了一金一银的成绩。此外，我参加了第32、33和34次的CCF CSP认证，并在33、34次认证中取得了500分满分成绩。这极大地鼓舞了我，让我对我的大学算法竞赛生涯更加充满自信。

ICPC参赛现场

第34次CSP认证经历

CSP认证要求在4个小时内完成5道题，选手能够实时收到反馈的测试结果。

本次认证的第一题只需要熟悉基础的语法应该就能够顺利完成，第二题考察的也是比较基础的暴力算法，我在稍微思考后很快通过了这两题。

本次比赛的第三题是一个比较复杂的模拟题。如果选手熟悉各种STL容器（如string, map, set等）的使用的话，在应对本题的时候会稍微轻松一点。但是本题还是比较复杂的，如果直接模拟会有TLE的风险。我先后想过很多种写法，最终决定用优先队列来找每次要加入词汇表的词汇对，并用了多个map和set来维护词汇对的变化情况，最终通过了本题。

本次比赛的第四题是一个背包问题。最开始，由于目标是求使得花费最小的方案，于是我考虑以获得的现金为背包容量，以花费为价值进行dp，但是由于获得的现金较大，这样会TLE。然后，我注意到b和c都很小，所以只要以花费为下标，求固定花费能获得的现金的最大值，最后从小到大枚举花费，这样就可以在时限内完成了。想清楚后，我很快将其实现并通过了这道题。

CSP34认证成绩单截图

本次比赛的第五题本应是一个数据结构题。我在考场上的时候，我认为这道题是一个二维线段树题，而二维线段树通常由四叉树和树套树两种写法。但是四叉树最坏情况的复杂度是O(n^2)的，我一开始在考场上不太记得，对此也没想清楚，写了四叉树提交发现TLE了，此时由于担心写树套树时间不够，于是想先写个暴力拿点分。我发现暴力做法可以做到O(nm)，并且只要排个序常数比较小，最多有可能获得50分。但是最终这个暴力做法通过了本题。正确的做法好像需要分治、线段树和四毛子算法，一个比较复杂的单log做法。

备考经验

CSP认证考试通常在前两题会考察比较基础的语法和暴力算法，在第三题考察大模拟题，在第四、五题考察一些常用的算法和数据结构。在对CSP认证考试的题型有了基本了解后，我们就可以对症下药进行练习。

首先，对于前两题，我们要熟悉一门编程语言并用它实现一些简单的算法。我们可以通过阅读算法竞赛的经典书籍并做一些Leetcode或者Codeforces div3/4，Atcoder Beginner Contest的题目。这些题目往往比较基础，在做了一些这样的题目之后，就算是打好了一定的算法基础了，应该就可以比较顺利地通过前两题了。

然后，对于第四、五题，这两题通常涉及一些经典的算法和数据结构，例如本次考察的背包dp、线段树、分治等。要熟练掌握这些算法，首先要相对系统地学习这些算法。我当时是阅读《算法竞赛入门经典》来学习这些经典算法的，而现在也可以跟着洛谷题单的顺序逐个在网络上搜索讲解对应算法的博客来进行学习。在学习了基础的经典算法后，我们就可以参加一些网络比赛来提升自己的水平了，比如说Codeforces的div1/2/3和Atcoder的ABC和ARC。尽量选择适合自己难度的比赛，我通常以能够完成3题左右为标准。适时参加比赛是激发兴趣的提升能力的重要方式。但是，在学习了一些基本的经典算法后，往往还有很多复杂的算法需要我们学习。我们可以逐个专题（例如动态规划，图论，字符串，数学，数据结构等）学习，并完成一定量的对应题目，整理相应的模板（因为在CSP和icpc/ccpc等大学的算法竞赛中，很多是可以携带纸质模板的）。这样在应对相应算法的题目时也能够更加从容。最后，锻炼自己的思维能力也是非常重要的。我建议可以在Codeforces上刷比自己实力稍高的题，例如如果自己有rating 1800的实力，就可以去刷rating 2000的题，在感觉能够从容处理现在做的题目难度的题之后就可以进一步增加题目难度，这样就能够让自己的能力稳步提升。

而关于第三题，我认为不需要刻意地训练这样地大模拟题。因为在我们训练各种算法题的时候，我们同时也写了很多很多代码，在码量的堆积上，我相信在遇到大模拟题的时候也能够从容应对。

同时，对于CSP认证考试来说，我们可以善用考试机制。由于即时反馈且没有罚时，我们可以尝试写一些比较优秀的暴力，猜结论，用比较好写的做法来验证自己的结论等，或许就能够取得更好的成绩。

结语

非常感谢CCF给我这个与大家分享经验的机会。希望CSP能够越办越好，也希望各位选手能够在未来的CSP认证考试中发挥自我，取得优异成绩。