CCSP金奖说 | 中山大学梁励：从NOIP到CCSP编程之路的蜕变与成长

缘起NOIP

我在中学阶段就开始接触编程学习，并参加过由中国计算机学会CCF主办的全国青少年信息学奥林匹克联赛(NOIP)，然而遗憾的是，当时我的实力并不够强，最高只拿过省级联赛二等奖。

接触CSP

后来进入大学后，因为中学有编程基础，我进入了学校的ACM校队，机缘巧合中了解到CCF还主办了一场面向高校学生的竞赛——CSP软件能力认证成绩，于是就去参加了第十八次CSP软件能力认证。那时候的赛制与中学的NOIP赛制是一样的，赛时编写代码，赛后再测。这种赛制极大地考验选手的代码和测试能力，因为无法实时得到评测结果，尽管编写的代码思路正确，但可能会因为一些细节导致程序的输出结果不正确，在小规模数据集上可能不会引起，但在评测时使用的大数据，这样的错误可能会被放大，导致结果错误，或者程序异常终止。为了防止因为细节丢分，往往需要手动生成一些数据进行测试。我还记得当时的第三题，是一道判断化学方程式是否配平的大模拟题，它像四则运算一样涉及到括号嵌套，为了检验我编写的程序能覆盖各种嵌套情况，我手写了十几个化学方程式以检验我的程序的正确性。最后成绩也非常幸运，前三题都如期拿了满分，第五题如期拿了25分的暴力分。虽然中学成绩不够出色，但这次CSP软件能力认证给我了信心。后来我也因此成为了CCF学生会员。

在第十八次CSP软件能力认证之后，由于个人原因的时间冲突，再一次参加时已是第25次能力认证，此时赛制已经从原来的NOIP赛制变为IOI赛制，实时提交代码并得到实时评测结果，并且非正确的提交不会有任何的惩罚。这样的赛制可以更好地让我们专注于代码的思路，极大程度地避免因为一些细节导致丢分、爆零，和不会此题的人一样的分数。

梁励CSP认证成绩单截图

在随后的25、26、27、29、30次的CSP软件能力认证，我的分数都超过了400分，除了第30次，其余的都是前4题满分，第5题拿了会做的暴力分。我大学期间一共参加的这六次CSP软件能力认证，可以发现它的题型相对固定的，第一、二题考察的是简单的stl运用或者简单算法，比如贪心、二分，而到了第三题，题面不仅会变得比较长，还会涉及到计算机领域的知识，比如第25次的关于亲和性的任务分配（Kubernetes集群），第26次的系统认证与权限认证（Unix类文件系统的权限管理），第29次的表达式解析（编译原理），第30次的数据解压（二进制流操作），如果事先了解过相关领域的话能比较快的理解题目，这类题目往往是大模拟题，一般不会考察高级的算法，但是代码一般会比较长，需要对代码有较好的组织，还有对代码的时间复杂度分析，对于一些耗时较大的操作比如查询可以用stl或者某些预处理优化。到了第四题，难度就会上升，其题目一般是要要求维护一系列操作，需要对操作的行为进行理解，选择合适的数据结构维护数据，比如线段树、树状数组、柯朵莉树、C++的set。第25、26、27都是灵活运用了C++的map和set对数据插入删除查询仅需要log的时间的特性维护数据，而第29次则是一个柯朵莉树（其实也是一个set），这要求对数据结构有深刻的认识，掌握一些维护数据的技巧，其中也对码力有一定的要求。最后的第五题则会涉及到算法知识，比如动态规划、图论、博弈论等等，如第25次的博弈论、第26次的线段树维护矩阵乘法，第27次的分治+李超树或分块，第29次的分治算法，第30次的状态压缩的最短路搜索，这需要对算法比较熟悉。但是，尽管有时不能想到这些题目的满分做法，也可以尝试部分分的做法，其中最低档的部分分往往对应着最朴素的做法，那就是时间复杂度可能是指数级的，非常容易想到的，直接进行模拟的做法。上述提到的一些借助于数据结构的做法，往往是优化了朴素做法里比较耗时的点，从而降低了算法的时间复杂度。对于第25次的博弈论，还可以打表找规律，本地枚举一些局面，计算得出必胜必败态，然后分析有什么规律。

备赛CCSP

除了CSP外，还有一类被称为CCSP（计算机系统与程序设计竞赛）的比赛，它是CSP Plus版——比赛长达12小时，共解决5道题目。题目分两种类型：计算机系统和程序设计两类。程序设计类就是算法题，而计算机系统类则是超大模拟或者完善工程代码。两类题目数量基本是半半开，2023CCSP则是3道算法题+2道工程题。第一道是比较简单的拓扑排序题，第二道是涉及推式子的组合数计算，第三题是二分+线段树优化贪心决策，第四题是编译原理相关的语法解析定义+语句执行，第五题是一个并行流处理背景下的完善代码。后两题题面之长占据了所有的三分之二，其中第五题还涉及到makefile的使用，但虽然题面很长，但耐心读完后，解法就呼之欲出，感觉是这里面最简单、代码量最少的题。12小时的时间感觉非常充裕，在前6小时基本把除了第四题之外的分都拿了，但由于对编译原理掌握不深，对此类大模拟的编写缺乏清晰的方向和大局观。所幸在封榜时意外地看出了第三题代码的bug，多拿了20分进入了金牌线。

2023 CCF CCSP竞赛中山大学师生合影

关于如何提升自己，我觉得可以从三个角度提升：思维、知识点、码力。思维就是指思考问题的方向和角度是否多、广，有一类题被称为思维题，也被称为ad-hoc题，这种题基本不考察什么算法，但考察的是题目性质的发现能力：发现出暗藏在题目中的某种特性，利用该特性就能解决这类题目的。知识点就是诸如二分、动态规划、图论、数据结构这类，可以通过学习网站比如OI-Wiki或者比赛中学习。码力就是快速编写代码的能力，不仅能够将所想的转化成代码，还需要以更快、更简洁的方式编写出来。一道难题往往是思维+知识点的结合，需要注意到题目的一些特性，从而可以用特定的算法求出结果，或者是有一个基本算法，然后因为有一些特性从而可以优化复杂度。

对于CCSP来说，熟练掌握计算机专业知识至关重要。对于工程类问题往往会有计算机知识的背景，如果对相关背景有所了解，就能花较短的时间快速地理解题意，对要编写的代码有初步想法。除此之外也要多接触一些工具的使用，例如，C++项目中常用的CMake、Make，了解一些open source软件的源码。CCSP的规则里有个特别的地方，是可以携带自己的电子资料，因此整理自己以往的课程大作业、知识总结，方便自己去检索、寻找思路。

2023 CCF CCSP竞赛现场

关于提升自己的手段，推荐是坚持去网上的OJ上打比赛，比如codeforces、atcoder这些知名OJ。打比赛不仅是对知识的巩固，在比赛过程种涉及到自己不懂的知识可以赛后学习，而且还是码力、抗压能力的锻炼。这些比赛不仅是限时的，而且还是有排位分，和全球数万人一起比拼，每场都可以视为一场试炼。而且赛后是可以阅读他人的解题代码，从而学习到一些简洁优美的写法。尽管我已经读研一，我每周还是会在atcoder上打一场比赛，并编写比赛的题解，整理自己的解题思路。当然，CCF CSP认证考试官网有一栏模拟考试，其中包含了往年所有CSP考试的题目，可以自行练习。

梁励参加CCF全国算法精英大赛

结语

最后，我由衷感谢CCF为我们提供的比赛平台。CSP和CCSP对我而言，不仅是宝贵的竞技经历，更是促使我认知到个人发展的不足之处的机会。希望CCF未来的比赛能够更加成功，让更多的学子受益匪浅。