返回首页
您的位置:首页 > 新闻 > 专题 > CSP群英榜

CSP高分说 | 山东大学周何:始于小学的算法竞赛之旅

阅读量:33 2023-09-01 收藏本文

山东大学周何在第30次CSP认证考试中获得450分,位列全国第四名。每年CSP高分考生(200分及以上)均可报名参加CCSP竞赛,CCF不定期邀请CSP高分和CCSP获奖选手分享经验,希望能够帮助同学们取得更大的进步。


周何介绍图


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


我的算法竞赛历程



我第一次接触计算机,大概是在小学阶段。在数学老师和同学家长的推荐下,我学习了基础的 Logo 语言——现在看已经是一种很有年代感的编程语言了。小升初时,我凭借这一经历,意外地进入了初中的竞赛班。


在竞赛班的前两年没怎么认真学习算法竞赛,总觉得自己这样的基础很难走远。初中前半段我最喜欢的事情是跑到机房去偷偷玩拷在u盘里的小游戏,平时课上抄抄代码。初二下学期一次偶然的比赛,我碰巧获得了一个比较靠前的位次,这大大激励了我,我从那时真正开始投入较多时间学习算法竞赛,也渐渐发现了它有趣的地方。初三那年,我压线获得了NOIP2017提高组的一等奖,后来被高中的教练选中,进入了高中的信息学竞赛组。


高中的竞赛并不顺利,由于能力终究不够,我没能走得很远。高一获得的冬令营铜牌没想到是我高中竞赛生涯的最高成就。


我对CCF NOI系列活动印象深刻,在考入山东大学后也关注着CCF组织的其他赛事,其中也包括CSP认证。我参加过四次 CSP 认证(24,25,29,30),除第一次对比赛准备不充分,跳过了看似复杂实际简单的第三题,又没能在规定时间内调对第四题,结果成绩并不理想。剩下三次认证中,我均获得了400分以上的成绩,也在最近一次的第30次CSP认证中取得了450分,位列全国第四名。

  

图片
图片
图片

More



如何准备CSP



一次CSP认证的组成是5道题目,前两题一般较为简单,考察内容不会超过模拟、枚举和二分,考场上需要尽快通过,为后面的题目预留出时间。对解决这两道题有困难的同学,需要多练习编程基础题,提高代码能力。


第三题一直是较为复杂的模拟题,一般来说会基于一个现实的系统。几年前的第三题是非常难以通过的,不过近几次难度有降低的趋势,变得越来越可做了。解决第三题需要非常仔细地读题和编写代码,“Think twice, code once”。以最近一次认证的第三题为例,最令我印象深刻的是“10”的回溯引用,“o以小端序存储于随后的两个字节中”,我在考场上把方向弄反,总有几个测试点无法通过。我花费了大约半小时去查找这个错误,最终导致第四题没有时间写完。另一方面要注意的是这类模拟题目实现的代码会比较长,所以编写的时候要尽可能想办法简化代码,封装一些会被使用多次的操作。还是根据上道题目,我们需要处理很多十六进制数字。那么可以想到一个简易处理方法是将读取单个bit单独写成一个函数,输出十六进制单独写成函数等等。不过这些经验之谈仅仅能提供一个编写代码时的建议,具体如何实现,还需要各位选手自行探索。


第四题和第五题,基本围绕高级数据结构、图论、动态规划来命制,以前也考察过计算几何、字符串等知识点。这两道题通常是竞赛级别的算法题,难度较大,如果没有足够的算法水平,还是较难解出的。但这两道题一般会设置较多的部分分,合理利用这些部分分,在很多时候是个好选择。例如想获得满分,数据范围是〖10〗^5,需要实现 O(nlogn) 的算法,但这个算法考场上并没有想到,或者想到了但难以实现,这时候我们观察数据范围,发现可以实现一个 O(n^2) 的算法获得40分,那么这不失为一种选择。不仅仅是数据大小,还有其他的情况,比如图论题目,图的形式是一棵树甚至一条链,也会给予一定的部分分。最近一次认证的第四题就是道典型的数据分治题目,100分中需要写5个20分的、互不相同的subtask。在考场上选择适合自己的,以拿最高的总分为目标,这样是性价比最高的。


关于比赛环境,各校可能不太相同。山东大学软件学院使用的是 Ubuntu,有配置好的 VScode等编辑器可以使用,平时多利用自己的电脑体验比赛环境,对考场稳定发挥是有帮助的。另外CSP认证时现在允许携带书籍,我们可以带一些自己熟悉的参考资料,例如一本通等。


在我看来,CSP认证的准备是一场长跑,需要积累相当的水平,才能在分数上实现突破。很多同学只能完整地解出前两道题,这不是考场技巧可以弥补的。另外CSP认证对知识体系的完整性要求较高。它的考察随机,尽管平均难度小于ICPC等同类型大学生竞赛,但由于ICPC是三人竞赛,队伍里可以形成互补,个人少掌握一些知识点问题不会很大。但CSP考场上,我们只能靠个人能力,一个知识点出问题,会导致整次认证成绩的崩盘。


关于提高综合算法水平,推荐大家去各大训练网站上刷题,包括而不限于CCF官方OJ,牛客网,Leetcode,洛谷等各大知名训练网站。在练习到一定程度后用往年认证的题目模拟,估计自己的水平。最后,每次认证考察的知识点可能不同,因此对每位同学来说,难度也不会相同。因此可以通过多考几次来达到刷高分的目的。



写在最后



算法竞赛带给了我许多潜在的提升,不仅仅是专业知识。还体现在代码水平,学习能力等方面。几年的算法竞赛使我受益匪浅,我非常感谢算法竞赛带给了我这一切,对于选择了这条道路感到无比的庆幸。


我需要感谢组织这一赛事的CCF,感谢山东大学软件学院和其他各院校对CSP认证的认可,使得更多的同学可以借此学习算法知识,提高代码能力。祝CCF-CSP认证越办越好,祝各位选手的认证成绩越来越高!