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

CSP高分说 | 武汉大学徐嘉浩:热爱不止于此——我的算法之旅

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

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



图片

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



我的算法竞赛生涯


我最早接触算法竞赛是在小学五年级,当时受到身边同学和家长的影响,报名参加了一个名叫"信奥"的兴趣班。那时我们使用的还是Pascal语言,我从中学会了一些分支和循环语句。初中时,我了解到CCF举办的NOIP比赛,并从那时起正式开始学习算法,成为了一名OIer。在初一的一年里,我学习了许多算法,例如深搜、广搜、二分、动态规划等等,初步领略到了算法的美妙,并开始投入更多时间进行刷题。随后,在初二和初三时,我顺利获得了NOIP普及组的一等奖和提高组的二等奖。在绍兴一中的信息竞赛选拔中,我也以第一名的成绩顺利通过。


然而,在高中时期,我的竞赛表现并不如意。由于一些低级失误,我在高一和高二这两年仅以联赛二等奖收尾。尽管如此,我对算法竞赛的热爱仍然持续着,即使在学习文化课的期间,我也会抽出时间去思考一些算法问题。终于,在NOIP2021上,我正常发挥,获得了一等奖。这次的成功让我更加坚定了继续追求算法竞赛的决心,同时也让我认识到失败并不是终点,而是一个成长的机会。


在大学期间,我早早地加入了ACM集训队,继续着我的算法竞赛之旅。在董文永老师的悉心指导下,我和队友在经历了合肥站的第36名(银奖第一)后及时调整,最终在ICPC南京区域赛上获得了金奖。在接下来的一年里,我经历了队友退役、队伍重组,但仍取得了较不错的成绩:两枚ICPC区域赛金奖,一枚EC Final银奖,一枚CCPC区域赛银奖以及湖北省赛的季军。除了参加XCPC系列比赛外,我还积极参与了许多CCF举办的比赛,如第27次和第32次CSP认证以及2022年CCSP竞赛。CCSP竞赛独特的赛制和题目开拓了我的视野,让我见识到了算法的多样性和实用性。这些经历不仅丰富了我的知识,也让我更加深入地理解了算法的应用价值。


图片

参加2023ICPC济南站与队友的合照,左一为徐嘉浩



CSP备考建议


CSP认证包含5道题目,每道题目满分100分,有多个测试点,每通过一个测试点会获得相应分数。选手需要在4小时的时间里,尽可能获得更高的分数。CSP认证是IOI赛制,也就是说每道题可以多次提交,实时评测,最后取最好成绩。


题目方面,5道题的难度是由易到难的。前两题较为简单,考察的知识点往往是模拟和枚举,有时会涉及非常简单的动态规划。这两题的代码量通常较短,选手需要在考场上尽快通过,为后面三题留下充足时间。


第三题一般是一道较为复杂的模拟题,思维难度不大,但代码难度很大。题目往往以计算机相关的知识或现实生活中的问题为背景,要求选手模拟一系列过程。题面很长,细节很多,需要选手静下心来慢慢写,慢慢调试。准备这类题目的话,只能多去刷一些代码量大的题目。写题之前多思考各个环节之间的关系和顺序,可以先在纸上将整个流程写一遍。


第四题和第五题主要涉及数据结构,在思维和代码两个方面都难度拉满。选手不仅需要对众多数据结构有较深的理解,还需要有较强的码力来实现。例如,在第27次CSP认证中,第四题的解法涉及并查集和珂朵莉树,第五道题的解法则是树状数组维护李超树,思维难度很高,代码量很大。针对这两道题,一个比较好的选择就是先考虑部分分,尽量多的获得分数,然后再冲击满分正解。部分分的难易程度是有梯度的,而且往往会是正解的重要提示。


需要注意的是,CSP认证是可以携带纸质资料的,从以前只允许书籍,到现在可以是打印和手写的资料。因此,选手可以提前准备各种知识点的模板和参考资料,并将其带入考场以备不时之需。CSP认证使用的电脑系统是Ubuntu,且会提供vscode等代码编写工具。建议选手提前熟悉认证环境,学会如何配置自己熟悉的工具,以便更高效地编写代码。


图片

武大新生赛讲题



第32次CSP认证个人经验


在第32次CSP认证中,我非常顺利地通过了前两题。第一题“仓库规划”简单枚举即可,第二题“因子化简”考察了根号枚举因子的方法。然而,在第三道题目上我遇到了一些小问题。本应是一道大码量的模拟题,但是我没有观察到一些性质,错误地认为简单模拟每个询问的复杂度太高。因此,我选择了整体处理询问的方法,浪费了很多时间。


第四题和第五题比较难。我在两题之间反复横跳,思考了一段时间无果后,选择了尽可能多的获得部分分。第四题的撤销操作让我很是头疼,一直找不到好的解决方法。于是,我先获得了O(n^2)模拟的35分,然后通过线段树维护矩阵乘法,获得了没有撤销操作的20分。虽然在最后时刻我想到了倒着处理可以有效解决撤销操作,然后就可以用分块来维护,但遗憾的是已经没有时间来让我完成这题了。至于第五题,第一档特殊性质的20分可以通过简单的动态规划实现,第二档K<=15的30分则可以通过状压DP获得。尽管只是第二档部分分,但是其中的实现细节也很多。



结语


非常感谢CCF提供这次机会,能让我分享自己的竞赛经历和经验。同时也非常感谢CSP认证,始终保持高质量的题目,为广大计算机学生提供了一个测试代码水平的平台。最后,希望CSP和CCSP能够不断发展壮大,吸引更多的学生接触算法,提高代码能力。