CSP满分说 | 杭电高义雄：CCF见证我的算法之路

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

CCF与我的算法竞赛生涯

我从初一开始接触算法竞赛，当时还是使用Pascal语言编写程序。我学习了语法和一些基础的搜索算法后，在初二取得了CCF NOIP普及组一等奖的成绩。进入高中后，我因此前的基础被选拔进竞赛班，继续参加信息学竞赛。也是从这时起，我开始真正认识到算法的美妙，也在对算法的热爱中选择了未来发展的道路。

经过了长约一年的信息学竞赛学习后，我取得了NOIP提高组一等奖的成绩，可以继续冲击省队。于是我选择停课全力冲刺竞赛，但遗憾的是我在第二年的省队选拔中出现了比较严重的失误，无缘NOI。

出于对算法竞赛的热爱，后来我又参加了同年的APIO和CTS选拔，在这次活动上，CCF前秘书长杜子德与NOI科学委员会副主席赵启阳博士的发言给我留下了深刻的印象，让我对CCF有了更深的了解。国家队选拔现场的答辩也令我心潮澎湃，在我心中种下了一颗继续参加算法竞赛的种子。

高义雄在中学阶段的获奖证书

高考后，我选择来到杭州电子科技大学这所有着深厚算法竞赛历史与出色成绩的大学，继续我的算法之路。在学校的大力支持与刘春英教练的悉心指导下，我与志同道合的队友在大一上学期就取得了ICPC济南区域赛的金奖，让我更加坚定了算法竞赛的道路。然而在接下来一年多的竞赛生涯中，我遇到了自己的瓶颈——连续四场XCPC竞赛都是银奖，这带给我比较大的打击。

在纠结是否继续时，学校发布了承办第26次CSP认证的通知。我立刻报名了认证，想借这次认证来检验自己的水平。幸运的是我在这次认证中取得了500分满分的成绩，让我对自己的实力恢复了信心。

第二十届浙江省大学生程序设计竞赛现场，右二为高义雄

于是我坚定地投入到下一个赛季的训练中，大量的训练也带来了丰硕的成果：两枚ICPC金奖、两枚CCPC金奖、浙江省大学生程序设计竞赛亚军。在即将退役之际我又一次报名了CSP认证，并在第30次CSP认证中再次取得了500分满分的成绩，有幸成为全场唯一满分的选手。

2022 ICPC 亚洲区决赛颁奖典礼，右二为高义雄

对CSP备考的建议

CSP 认证时长四个小时，包括五道题目。

第一题一般是比较简单的模拟题目，主要考察对语法的熟悉和代码实现的能力。

第二题一般是有一些思维难度的简单题，要求选手有一定的观察能力和数学基础。

第三题一般是结合一些计算机的背景来出的模拟题，特点是题面长，细节多，代码量和前两题相比明显较大，此题往往也是CSP中区分度最大的一道题目。总的来说，对于此题建议是把题意理顺了再写代码。针对练习，个人建议是首先练一练提取题目信息的能力，三四页纸的题面包括了很多举例理解等内容，实际上题面有效信息可以梳理到约半页纸左右。备赛时可以利用往年题目进行训练，练习一边读题一边在草稿纸上记录有效信息。其次就是对代码能力的要求，平时多写一些比较复杂的模拟类型的题目即可，建议限时训练。

第四题与第五题是比较类似算法竞赛的题目，考察范围广并且一般是代码量比较大的题目，常考察高级数据结构、图论、动态规划等知识点。由于这两题的算法难度相对会大一些，如果不是算法竞赛选手，针对性备赛可以盯准部分分。一般来说题目都会有四到五档的部分分，难度由简到难，最简单的前两个档往往不会有太难的算法要求。

此外CSP认证类似IOI赛制：允许多次提交，取最高一次成绩，实时评测公布得分，但不公布排名。这个赛制对参赛选手来说非常友善，几乎不会出现想法正确但没拿到对应分数的情况，在时间足够的情况下几乎能发挥出个人的最高水平。

建议各位选手合理分配时间，充分利用评测系统提供的信息，即使是比较难的最后两题也积极尝试获得部分分。CSP认证的题目时间限制往往比较宽松，评测机性能也比较好，复杂度稍微大一些但合理的算法依旧可以通过。

高义雄在赛场上编写代码

第30次 CSP 认证个人经验

在第30次CSP认证中，我在大约开场一小时的时候顺利通过前三题。第一题是很简单的模拟题，如果合理使用STL会更好写。第二题考察了矩阵乘法的性质，我赛时采用了时间换空间的方法暴力通过了此题。第三题的题目背景是数据压缩，虽然细节比较多但是比前几次的第三题要好写一些。我用了约20分钟梳理题目内容，然后约15分钟后写完代码通过了此题。

本想着CSP压轴一般都是数据结构题，自己并不太擅长。但看了后两题竟然都是图论题，还有机会。于是先去做了比较有想法的第五题，理解题意大概是要求跑26次单源最短路，点数只有26*1024，但边数不好估计。我想了一个用空间换时间的做法，针对边集做一定的预处理。虽然时间复杂度看起来比较紧张，但相对于直接跑最短路是有明显优化的效果的。在开场大约两小时的时候写完代码，一次通过了此题。赛后观看官方真题讲解直播时，讲解的做法也和我的做法相同。

接下来我仔细读了第四题的题面，发现没有100% 的数据性质，每档都是问题在不同约束下的形式，于是只能一档一档写。第一档考察的是直接枚举；第二档考察的是比较基础的O(nk^2) 的动态规划；第三档是找出来环上的一条边，然后钦定这个边某个端点取值之后，就可以 O(nk^3) 动态规划求解；第四档是暴力找出来具有特殊性质的D点，然后钦定D取值后，就可以O(nk^3) 动态规划求解。我在数据性质的引导下写，还算顺利，这四档都过了的时候比赛时间约还剩下40分钟。对于最后一档数据我能理解到要暴力枚举特殊点（即度数大于2的点）的取值，但不知道怎么快速查询其他的最小代价。思考了一段时间后发现自己对数据性质的理解出了问题，删掉特殊点后剩下的一定是链，并且结果最多只和两个特殊点有关。所以可以对每条链进行动态规划，预处理总复杂度是O(nk^4) 的，可以通过。经过紧张的编码和调试，最终我在距结束还有约15分钟的时候有惊无险地通过了这道题。

回看整个过程，前三题和第五题的快速通过保证了我能够有足够的时间处理第四题；而在做第四题的过程中CSP的评测机制为我提供了很大的帮助，每写完一档我就可以提交测试一次，及时得到反馈，不用全部写完再测试，大大降低了调试难度。

高义雄同学的第30次CSP认证成绩单与CCF贺信

写在最后

感谢CCF给我这次机会，让我能分享自己的算法竞赛经历与感悟。对于广大本科生而言，想要检验自己的编程能力，或接触算法竞赛，CSP认证无疑是最好的机会，既能保证比赛的公平规范，也能保证题目的质量。

高义雄在IOI2023中国国家集训队集训担任志愿者

算法是美妙而深刻的，我本人也即将走上理论计算机方向的学术道路。祝愿CSP和CCSP越办越好，能吸引更多的学生接触算法、认识算法，更好的推动计算机教育的发展。