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

CSP满分说 | 中山大学陈景泰:CSP的“前端”和“后端”

阅读量:15 2024-03-13 收藏本文

中山大学陈景泰在第32次CSP认证考试中获得满分,第33次CSP认证考试将于3月31日举办,报名已于3月4日开启。每年CSP高分考生(200分及以上)均可报名参加CCSP竞赛,CCF不定期邀请CSP高分和CCSP获奖选手分享经验,希望能够帮助同学们取得更大的进步。



图片

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



与CCF的感情


我和CCF在初中相遇。我在小升初时有幸接触到信息学竞赛,并激发了极大的兴趣,以此开始了五年的OI求学过程。在此过程中,我参加了CCF主办的NOIP、CSP、WC等赛事,也取得了较好的成绩,获得了充分的程序设计竞赛经验。虽然在此过程中,我和省队失之交臂,未能站在NOI的赛场上,但这五年的奋斗历程无疑成为了我的宝贵经验。我逐渐认识到了算法的丰富绚丽,而算法也在我日后的学习中提供了许多便利。


在进入中山大学后,我对算法竞赛的热爱依然不减。我开始转战ACM,并在ICPC、CCPC等赛事上展现了自己的水平。在林瀚老师、张子臻老师和万海老师的悉心指导下,我和两位队友作为新生队伍在2023赛季取得了三金一银的成绩。同时,我们报名了本次CCF CSP认证,并都取得了500分满分的成绩。这些成绩无疑为我加强了信心,鼓励我在未来的赛事中不断突破自我。可以肯定的是,这些成绩离不开CCF对算法竞赛的优秀组织,也离不开CCF相关赛事提供的广大交流平台。


图片

在第48届ICPC合肥站中的气球簇



CSP“前端”——题目总结


CCF CSP认证时长为四个小时,包含五道题目。


第一题和第二题相对来说比较基础,考察的是对普及层面算法的了解程度。一般来说,只要在前期的程序设计学习中稳扎稳打,这200分实际上不难拿到手。


第三题一般而言会在题面中提供相当多的信息,主要考察选手对具体信息抽象化的能力,而对算法本身不做太多深入。对于本次比赛的第三题而言,在略去题目提供的背景知识和样例解释后,本题的核心实际上比较简单:利用权重系数构建一个树状结构,随后利用模拟算出每一步需要询问的编号。当然,除了分析题目之外,选手还应当对代码的复杂度和常数有一定的认知,防止分析不当导致复杂度错误等问题。我在写完第三题后发现代码超时了,随后发现是递归栈的使用增加了常数,导致复杂度卡不过去,到了最后优化了复杂度才解决问题。


从第四题开始,题目对算法的要求逐渐提高,风格也更加偏向于OI/ACM系列的题目风格。这类题目一般带有比较强的形式化描述,方便选手进行题目的理解,所以对于这两道题更应该借助自身的算法基础,尽可能多的进行拿分。对于这一些题目,有一个比较好用的经验:抓住数据范围、部分分性质等得到一些关键提示。在某些题目中,一些循序渐进的数据范围可能会给我们一定的启发,而整体的数据范围也可以帮助我们快速锁定算法。在本次比赛的第四题中,由于数组长度和询问次数均有可能到达十万,而题目的矩阵乘法必然对算法带来比较大的常数,故此时我们就能自然考虑使用单次操作亚线性的经典数据结构,在本题中对应线段树和分块。同样的,在本次的第五题中,考虑到路径拆成两部分后的合并可以快速达成,再次利用长度较小、颜色数量较少的性质,即可设计出正确的算法。


图片

在Byte Camp训练



CSP“后端”——复习策略


CCF CSP认证在赛时就会提供评测的分数等信息,同时不在赛内公开榜单。对于长时间在OI赛制模式下练习的选手来说,这一点可能会带来赛场策略和调试思路的一些差异。对于这部分选手,我的建议是先进行IOI赛制下的策略训练。训练可以直接从官方的题库切入,也可以对照难度在其他题库中寻找题目并组成比赛。由于算法本身涉及到方方面面,而对一个算法的深入程度可能会深刻影响到某道题的分数得失,因此在训练过程中尽可能多的进行算法开拓并非坏事。


另外,每一位选手都需要根据自己的能力设计一个清晰的赛时得分预期,防止在赛事出现心理上的过度作用。如果对一道题抱有太高的期望,而中途发现自己无法达到预期的时候,往往就会出现死磕一道题目,却忘了后面题目的情况。CCF CSP认证存在部分分的设置,在不清楚正确解法的时候,适当的跳过或者先实现部分分算法是很有必要的。因此,我们可以在赛前借助自己的训练经验,明确每道题目需要实现的目标,在赛时也需要放平心态,发挥尽可能大的潜能。


当然,除了算法学习之外,一些细节上的优化也是可行的,例如代码能力训练、数学推导练习、常数优化技巧等。这些优化无疑可以提升赛时得分的稳定程度,保障选手在赛场上高质量地完成题目。而与此同时,这些优化训练也并不是必需的,在本身算法能力并不充足的情况下,还是建议以算法学习为主。



总结


CCF CSP认证在各方面体验良好,题目难度梯度适中,赛事评测迅速,比赛的公平性也能得到保障,无疑是验证程序设计能力的大好机会。希望CCF CSP认证保持优秀的比赛质量,也祝愿各位选手在赛场上发挥出自己的最佳水平,得到理想的成绩。