返回首页
您的位置:首页 > 新闻 > CCF聚焦

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

阅读量:328 2023-11-22 收藏本文

2023 CCF CCSP竞赛10月底于沈阳成功举办,中山大学梁励同学获得金奖。每年CSP高分考生(200分及以上)均可报名参加CCSP竞赛,CCF不定期邀请CSP高分和CCSP获奖选手分享经验,希望能够帮助同学们取得更大的进步。



图片

非常欢迎更多CSP高分学生分享自己的宝贵经验,联系:csp@ccf.org.cn


图片

缘起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未来的比赛能够更加成功,让更多的学子受益匪浅。