竞赛 > CCSP > 竞赛动态
CSP满分说 | 南京理工沈培森:从CCF开始的算法之旅
2024-05-17 阅读量:47 小字

南京理工大学沈培森在第33次CSP认证考试中获得满分,第34次CSP认证考试将于6月2日举办,报名正在进行中。每年CSP高分考生(200分及以上)均可报名参加CCSP竞赛,CCF不定期邀请CSP高分和CCSP获奖选手分享经验,希望能够帮助同学们取得更大的进步。



图片

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



充满坎坷的算法生涯


我从大学开始接触算法竞赛,CSP可以算是我的算法路上不可或缺的一部分,在备战CSP的过程中,我经历了许多挫折和困难。2022年6月,我参加了第26次CSP认证,也是我第一次参加,我在前两题上表现不错,但第三题让我束手无策,最终获得了220分,并因此加入了南京理工大学的ACM-ICPC集训队,系统地学习算法,并参加比赛积累经验,开始了我大学四年的算法竞赛之旅。在大三上学期,我拿到了ICPC南京站的银牌,这让我找到了自信。

 

图片

2023年ICPC南京站现场 右一为沈培森


后来,我报名参加了第32次CSP认证,刷题进展顺利,但考前的ICPC济南站中,我们队以几名之差错失银牌。同时考试中第三题再次让我困扰。考试结束后,我倍感疲惫和失落。然而,在ICPC队友的鼓励下,我重新振作起来,并报名参加了第33次CSP认证。考前两天,我碰到一道关于树上启发式合并的题目,是一个我从未接触过的算法。当时的我怎么也想不到考试会涉及到它。经过两天的努力,我终于在考试当天凌晨三点找到了最后一处bug并完成了题目。


图片

 沈培森在宿舍写代码



第33次CSP认证考试经验


在考试中,第一二题过得很顺利,来到了困扰我两年的第三题。幸运女神似乎终于眷顾我,这题正好是关于高斯消元的字符串模拟,而我准备的资料里刚好有高斯消元的代码模板。那么只要完成数据处理,然后对高斯消元模板微调一下应该就可以了。我模拟了一下矩阵形成的过程,并轻松地拿到了第三题的满分。


第四题是关于水滴爆炸的题目,需要快速找到水滴左右两边的水滴,用set容器存储水滴的位置,每次log查找水滴的位置,用迭代器log搜索左右两边的水滴,把即将爆炸的水滴存到优先队列里依次处理,即可满足题目的要求。我细心地写完了代码并测试样例,成功通过了第四题。


来到第五题,我内心充满激动。这题可以分为两个子问题,第一个是合并操作,第二个是删点维护深度。第一个子问题我选择暴力合并,第二个子问题,我很快想到了树链剖分加线段树的算法,这正是我在寒假刚学的。我迅速写完了代码却发现有几个点空间爆炸,只得了55分。在一次次检查中,我发现执行合并操作时,每次最差要O(n)的时间,q次询问则最坏有O(nq)的时间复杂度,显然是会超时的。这虽然看上去和空间没关系,但我还是运用树上启发式合并对其进行优化。提交后,我紧张地等待测试结果。当看到“100正确”的字样,我激动地喊了一声“yes!”。这一刻,我感到非常兴奋,仿佛一场梦。确认自己真的拿到了满分后,我再次喊了一声“yes!”,看看时间,还有两分钟到三个小时。


图片

 沈培森CSP满分成绩单截图



关于CSP备考的建议


1.正确认识CSP认证。CSP前两题都是比较基础的,只涉及一些简单的算法以及STL容器。第三题是一道大模拟,对思维要求不高,但需要较强的代码能力。第四第五题会涉及一些较难的算法,需要一定的竞赛基础。


2.多写题,多学算法。努力是通往成功的唯一捷径,也是我们唯一所能做的事情,是分数上一台阶的突破口。所有的实力都是通过一道道题目的积累得来的。我们需要根据自己的薄弱环节,有重点的努力,努力填补自己的不足。


3.坚持不放弃的心态。在我经历前两次CSP失败的时候,如果选择放弃,我就无法欣赏到我现在500分的成果,甚至无法接触到算法竞赛这条充满挑战的道路。人生中总是充满了失败、坎坷,在面对这些困难时,坚持不放弃的心态可以帮助我们保持积极的态度和动力,努力度过人生的“阴天”。



结语


非常感谢CCF能给我这个分享自己算法竞赛经验的机会。参加CSP认证无疑是对自身代码、算法水平的一次检验,能很好的体现自身的优势与不足。最后祝CCF能越办越好,同学们也能在CSP认证中取得自己满意的成绩。

热门动态
2022-08-18
助力制造业企业及会员单位匹配需求供给、实现资源互补,搭建专业的产需服务平台,促进制造业数字化转型和融合创新发展,首届“CCF智能制造大会” (CIMC 2022),于2022年7月16-17日在CCF业务总部&学术交流中心成功举办。
2022-08-18
7月22-23日,由CCF主办的2022 CCF未来计算机教育峰会(FCES 2022)在苏州CCF CCB(业务总部&学术交流中心)召开,全国近百所高校科研机构和企业的60多位专家学者、政府领导和多家企业代表,以及300多位现场观众齐聚苏州,共话中国计算机教育的未来。
2022-08-18
CCF发展的60年,也是伴随中国计算机事业走过的60年,庆典上的很多专家,都为中国计算机事业奉献了热血青春,当年意气风发,如今虽已满头华发,但初心未改,他们创造了CCF的光辉历史,还将继续带领CCF走向更加美好的明天。
CCF聚焦
场地预订
如何抵达
周边酒店
活动预告
返回顶部