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

CCSP金奖说 | 武汉大学卢凯宾:我的算法竞赛成长之路

阅读量:503 2024-11-20 收藏本文

武汉大学卢凯宾在2024 CCF CCSP竞赛中获得金奖,每年CSP高分考生(200分及以上)均可报名参加CCSP竞赛。第36次CSP认证考试将于12月8日举办,报名正在进行中。CCF不定期邀请CSP高分和CCSP获奖选手分享经验,希望能够帮助同学们取得更大的进步。

图片

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



一、在信息学竞赛初识CCF


我很幸运,能够在小学时期就有机会接触到了信息学竞赛。当时入门学习Pascal语言,主要掌握了一些语法和基础算法知识。参加了区里的竞赛获奖之后,自己乐在其中,于是到初中时期仍然继续参加信息学竞赛相关活动。


2015年,还在读初一的我参加了由CCF组织的NOIP(全国青少年信息学奥林匹克联赛)普及组,在满分400分的比赛中获得了290分,以10分之差遗憾获得广东省二等奖第一名。


接下来的一年时间里,我努力提高自己的水平,终于在初二时的NOIP 2016中一跃获得375分,位列广东省并列17名,顺利获得普及组一等奖。


到了初三,我不再满足于普及组的比赛,想要尝试参加提高组。但在NOIP 2017提高组中,我的发挥不尽人意,在满分600分的比赛中仅获得了315分。尽管如此,在与高中生同台竞技中,我成功获得了提高组一等奖,这让我给自己继续在竞赛路上前进增添了一分动力。


到了高一,我的竞赛水平得到进一步提升,并在NOIP 2018中以420分的成绩获得一等奖。然而在高二那一年,CCF宣布:由于某种原因,NOIP从2019起暂停。CCF在当年推出了CSP-J/S(非专业级别能力认证),但可惜我因为自身原因没有选择继续参加,而是选择回归备战高考,也就无缘后续的省队选拔以及NOI。至此,我的算法竞赛生涯前半篇章划下了句号。


后来,CCF在2020年宣布恢复NOIP竞赛。当时的我已经在读高三,正面临着备战高考的关键时期。但出于对算法竞赛的情怀,同时也是为了弥补自己没有参加去年CSP-J/S的遗憾,我选择了参加CSP-S 2020和NOIP 2020。作为一名阔别竞赛一年之久的退役选手,我仍然在两项赛事中取得了一等奖。


于是,我想:虽然我在算法竞赛领域无法达到顶尖水平,但至少我应该或多或少有一些适合在这个方向发展的素质。我希望能在大学续写算法竞赛的故事。


图片

图:作者在中学时期参加CCF组织的NOIP竞赛和CSP-J/S认证所获奖项



二、与算法竞赛再续前缘


进入大学之后,我加入了武汉大学ACM-ICPC集训队,并积极参加ICPC和CCPC(国际/中国大学生程序设计竞赛)。与中学时期参加的单人赛制、无即时反馈、有部分分的信息学竞赛不同,这些比赛具有多人组队参赛、即时反馈、由题数和罚时决定排名的特点。不同的赛制带来了新的挑战,在与队友的日常训练中,我们不断磨合,精进技术。


在我大二时(2022赛季),程序设计类赛事均在线上举行,参赛队伍数量相比于往年的线下赛有了显著增长,奖牌的竞争也更为激烈。尽管进行了大量的训练,我们仍未能如愿获得金奖,只能遗憾获得ICPC银奖2项和CCPC银奖1项。


到了大三(2023赛季),线下赛终于得以恢复。我们乘坐高铁辗转征战CCPC深圳分站赛和ICPC澳门区域赛,仍然均以银奖告终。至此,若将邀请赛的成绩排除在外,我们队已经连续获得了5次银奖。于是,在ICPC杭州区域赛,我们将队名起为“背水一战”。这是我们队夺金最后的希望了。幸运的是,在队友的帮助下,我们队最终顺利收获了1枚ICPC金奖,并入围EC-Final(亚洲区决赛)。


至此,我大学时期的团队算法竞赛生涯迎来了圆满的结束。现役期间,我不仅作为竞赛选手参赛,而且参与承办了湖北省赛和武汉邀请赛,均获得一致好评。


图片

图:作者在大学时期参加ICPC和CCPC所获奖项



三、参加CSP认证与CCSP竞赛


在大学期间,除了ICPC与CCPC竞赛外,我还积极参与了一系列个人独立参加的算法竞赛,包括蓝桥杯、天梯赛、睿抗等,并均获得了全国一等奖。


在这些赛事活动中,由CCF组织的CSP(计算机软件能力认证)和CCSP(大学生计算机系统与程序设计竞赛)最具特色。与其余赛事有所不同,CSP认证事实上参考了国际主流的IOI赛制,巧妙地将大学生程序设计竞赛中的“即时反馈”和中学生信息学竞赛中的“部分分”机制进行融合,降低了认证者的准入门槛,也为认证者带来了良好的参赛体验。


除此以外,CSP认证不仅考察传统算法竞赛中的算法与数据结构知识,还引入了更贴近业务实际的系统工程题,全面考察认证者对于计算机组成原理、计算机网络、操作系统、数据库等领域中常见模块的理论掌握和代码实现水平。值得一提的是,这些课程的内容往往都会在考研或保研机试中有所涉及,因此参加CSP认证能够有效提高认证者的机试水平。


CSP认证时长4小时,共有5道试题。一般而言,第1、2、5道题目会考察传统的算法与数据结构知识,其中前两道题目相对简单,最后一题相对困难;中间的第3、4道题目则更倾向于考察选手对于长篇幅业务需求描述的阅读理解能力以及对于程序设计语言中STL(标准模板库)的熟练应用程度。


我到目前为止总共参加过5次CSP认证,在实践中熟能生巧,最近3次认证都获得了450分以上的成绩。特别是今年CCF上线了新模拟认证系统(https://sim.csp.thusaac.com/),不仅能够自由练习以往参加过的认证,并且每报名一次认证都能获取1个模拟认证兑换码,有效助力认证者体验考场环境。


届次

时间

分数

全国排名

排名百分比

25

2022年3月

420

11

0.28%

27

2022年9月

380

58

1.13%

29

2023年3月

475

3

0.03%

33

2024年3月

455

115

1.50%

35

2024年9月

465

30

0.49%

表:作者参加5次CSP认证的成绩一览


CCSP竞赛可以认为是CSP认证的集大成者,每年只有CSP成绩200分以上的认证者可以报名参加,全国约500名选手齐聚线下,进行持续12小时的鏖战。去年,我参与了沈阳师范大学承办的CCSP 2023,但发挥未能如意,仅获得铜奖。为了弥补遗憾,今年我决定再度报名参加CCSP,向更高的荣誉发起冲击。


今年CCSP的试题与往年一样,共有5道。


开场后,我很快阅读完了第一题。按照我对题意以及题目定位的理解,这是一道简单的算法题,只需采用朴素的贪心策略,维护两个队列,每次将新到达的任务交给完成时间更早的队列即可。代码实现起来非常简单,我在几分钟内就通过了第一题。


第二题需要对一个森林结构进行强制在线的动态维护和询问,看起来比较繁琐。正当苦恼之际,我发现数据范围部分提到了树的形态是随机生成的,这意味着树的期望高度为O(logn)级别,因此直接按照题意所述操作进行模拟的复杂度足以通过。提交结果表明,我的猜想是正确的。于是,我随之很快通过了第二题。


第三题是一道数据结构题。我首先提交了朴素的暴力代码,只能获得40分。对于测试点11-15,仅有操作1,即对于静态序列离线统计区间颜色数,这是莫队算法的经典例题,我很快对代码进行修改,获得了60分。对于测试点16-20,操作3的比例不超过10%,这意味着或许可以对于每次操作3暴力重建序列,而在两次相邻的操作3之间,则是支持修改元素的统计区间颜色数。虽然我知道这里考察的是带修改的莫队算法,但由于长时间没有应用,我对此已经比较生疏。好在CCSP竞赛允许携带电子资料,我在资料中找到了带修莫队的模板,修改代码后获得了80分。对于最后的测试点21-25,应该需要结合平衡树等数据结构进一步维护,但考虑到实现代码所需的时间性价比,我决定暂时放弃这一部分分数。


第四题是与计算机网络相关的模拟题。第五题的背景与操作系统相关,但最终考察无源汇点的最小割问题。这两题的阅读量和代码量都非常大,调试起来也非常麻烦。我从中午一直写到晚上,分别获得了100分和70分。


最终,我以100+100+80+100+70=450分的成绩,获得金奖第8名。


图片

图:作者获得2024年CCF CCSP金奖第8名


得益于积极参与CSP系列活动以及对算法竞赛社区的深耕和贡献,我有幸被评为2023年CCF优秀大学生,并在2024年CCSP颁奖典礼上被投票选为2025年度四名CSP代言人之一。这是CCF和算法竞赛圈对我的认可,我也希望自己能够继续努力,在自己的位置上发挥应尽的力量,推动竞赛健康可持续发展。



四、备考建议


对于正在备考或即将备考CSP认证以及CCSP竞赛的同学,我以自己的经验提供以下几点建议,希望能够帮到大家。


1.参考以往真题进行有针对性的训练。CSP认证和CCSP竞赛考察的侧重点与一般的算法竞赛有所区别,其中的系统工程题对代码能力要求很高。

2.考试过程中合理安排时间分配策略。虽然我上面提到的解题流程是逐题描述的,但实际上我在考场上是先拿到了各个题的暴力分,再逐步完善。

3.重视常见算法和数据结构模板整理。以今年的第三题为例,集中考察了普通莫队、带修莫队和平衡树等高级数据结构,需要提前做好相关准备。