CSP满分说 | 北邮崔家瑞：CCF带我领略算法的奥妙

我从小学六年级开始初步接触C/C++编程，我的中学生活与算法为伴，开启了美妙竞赛之旅。在信息学竞赛的过程中，对算法原理的迷惑不解和未通过题目的焦灼是家常便饭，但AC之后的喜悦与释然让我坚定地走下去。

中学阶段我三次获得CCF NOIP提高组一等奖，也获得了CCF WC/CTS/APIO 铜牌，虽然省选失利未能进入省队，但以D类参加CCF NOI并获得铜牌成绩。在参加竞赛的过程中，与CCF结下了不解之缘。

升入大学后，我心怀对算法竞赛的热爱继续前行。

获得程序设计校赛冠军（中为崔家瑞）

刚进入北京邮电大学不久，我就和队友一起在程序设计校赛中获得了正式选手的第一名。但我们没有因此沾沾自喜，反而发现了一些问题，因为备战高考疏于练习，之前在高中熟练掌握的一些算法题目现在甚至写不出来，想在区域赛中获奖需要进一步训练。

大二、大三两个赛季，我和队友参加ICPC和CCPC程序设计竞赛。我们多次获得银奖但没有获得过金奖，还是留下了些许遗憾。经过赛后复盘和思考，主要原因还是思维深度不够，做不出较难的题目。

参加CCPC深圳站（左二为崔家瑞）

2023年秋天，我参加了CCF CCSP竞赛，12个小时一整天的比赛对竞技水平和身心素质都是一种考验。我在比赛过程中心态崩了，在两道题之间摇摆不定耽误了时间，最终获得铜奖，虽有遗憾但是更反映出了自己在算法水平和临场发挥方面的一些问题。不过我凭借此前的CSP成绩入选比赛现场的CSP高分墙，得益于我的“人气”和北邮老师同学的支持，在颁奖典礼非常幸运地成为CSP代言人。

北邮参加2023年CCSP竞赛（后排左三为崔家瑞）

虽然目前我的竞赛之路已告一段落，但是竞赛带给我的远不止学到的算法知识和技能，还有思考问题的方式和深度、一次次跌倒再爬起来的毅力、在计算机世界中遨游的快乐……

我参加过第24、29、33三次CSP认证考试，分别获得了349分、450分、500分。就我个人而言，这几次CSP的前三题我都能比较顺利地做对，分数差距主要出现在后两题。

第24次CSP认证，第四题是一个模拟磁盘管理的数据结构题，我当时大概想了线段树的做法但是没有理清打标记的细节，只写了一个暴力战略性放弃了；第五题是一个树上路径的统计问题，我只做写了暴力和“菊花”形态的24分，不过赛后发现堆性质的部分分也可以用树状数组比较轻松地实现，与之前的结合有52分，但是考试时没有仔细思考。尽管这次分数不高但是达到了0.16%的单次排名，说明这次认证比较难。

在第29次CSP认证中，我用线段树写出了模拟IP地址分配的第四题（其实可以用std::set等更简洁的实现），不过有一个测试点运行时错误，拿到了90分就没有再调试；最后一题写了60分的暴力，另有15分的部分分没有时间了，最终拿到450分。

第33次CSP认证难度不大，最后两题也恰好碰到自己比较熟悉的知识点。第四题“十滴水”只要发现总的消除发生次数不超过5n就可以用线段树或者优先队列、set等模拟操作；第五题“文件夹合并”实际上就是一道树上合并和子树修改查询的“组合”题，起初我使用启发式合并的策略，可能由于这一部分多一个log n的复杂度导致超时，后来改成用链表存储儿子，再加上用树状数组和差分修改、查询节点深度就通过了本题，获得了满分。

 获得第33次CSP认证满分

首先从CSP的考试形式来看。

不同于传统的CCF高中赛事，CSP可以多次提交并实时查看提交结果，这给认证者更多的尝试机会，并且更注重考察认证者的程序设计能力（传统没有实时评测的比赛容易因为写挂而最终“爆零”，需要查错、对拍等等），这样让认证者能放心做题和提交，同时也能展现算法、数据结构的真实水平。

也不同于ICPC等赛事，CSP的每道题都有部分分，尤其是后面难题的部分数据性质非常丰富，即使认证者不会这道题的标准做法，也可以通过一些简单、暴力的做法或者针对特殊情况拿到相当一部分分数，甚至可能因为部分分的引导想出正解，这对于各层次的认证者都比较友好。

接下来从我参加的CSP认证和做过的真题进行逐题分析。

第一题一般是一个简单的编程题，没有算法背景、有一点程序设计基础往往就可做出。

第二题需要了解一些简单的算法，或是进行一些数学推导，编程一般也不难。

第三题往往是一道稍显复杂的模拟题，题面长、细节多，代码量偏大，需要认证者准确读懂题意、有比较扎实的编程实现功底，在模拟中运用一些结构化、模块化的设计思想能更快更准地做出，同时这道题基本也是能否拿到300+较高分数的“分水岭”。

最后两道题涉及一些较复杂的算法和数据结构，每次考察的知识点各异、难度也有波动，但还是有一些共性。就我的经历来说，第四题有时是一道需要经过一些思考和转换的数据结构题目，最终很可能能用线段树或一些set map等STL解决；这两道题也可能考察动态规划、图论里的最短路等算法、树上算法等等，和算法竞赛类似，难度比较大，正解不容易但是可以拿一些部分分。

总体来说，备考CSP主要还是需要学习算法、数据结构的知识，编程的准确度和速度这些“硬功夫”，毕竟4小时5道题还是比较紧张的。

多编程实现代码量较大的模拟题目；着重掌握基础和中等层次的算法和数据结构，并争取熟练编写；C/C++语言认证者熟悉STL也很可能事半功倍。这些除了做历年CSP真题（CSP报名网站模拟考试）之外还可以去一些其他OJ（如codeforces，洛谷）练习，不过没必要刻意去学习太难的高级算法（比如算法竞赛常见的数论、多项式、计算几何等在CSP认证中基本不会出现）。

同时培养针对小范围和特殊数据思考和解答的能力，在不会的题目上尽可能获得部分分数，也要注意从实时评测的反馈中推测程序的问题并进行调试。另外现在CSP允许携带纸质资料，可以携带一些书籍和打印的模板以便赛时参考。

感谢CCF给我这次分享的机会和对我的认可，也十分荣幸成为CSP代言人。CSP是对认证者算法、数据结构和程序设计能力的综合考验，希望我的分享能给大家备考带来一点帮助。祝愿CCF CSP认证越办越好，也祝大家在CSP认证中取得理想的成绩，让自己的专业能力得到业界认可的同时，领略算法设计的无限风采，感受计算机科学的无穷魅力。