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

CSP满分说 | 天津大学李国鸿:我的算法竞赛和CSP经验

阅读量:15 2024-05-15 收藏本文

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



图片

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



CCF与我的算法之路


我第一次接触编程是在初三后的暑假,当时刷信息学奥赛一本通的OJ来学习C++的语法基础,然后自己用简单的分支结构和函数去写一些像贪吃蛇、文字冒险这样的小游戏。在这一过程中,我学着去使用栈和队列等数据结构,并产生了对于编程和算法的兴趣。

 

图片

初三时候写的贪吃蛇小游戏


我所在的高中是所具有竞赛底蕴的学校,在身边都是竞赛高手云集的环境下,我也开始尝试参加算法竞赛。由于经验不足,高一上学期第一次参赛时,我只拿到了CSP-J的奖项,但我并没有气馁。经过一年的努力,我获得了CSP-S、NOIP的一等奖,NOI冬令营的金牌,并顺利以综合成绩第一进入NOI天津代表队。


图片

 高中期间所获奖项


在算法强手云集的浙江余姚NOI现场,我见识到了更广阔的天地。可惜个人实力不足,没能取得理想成绩的我只能回到课堂准备高考。于是我高中阶段的算法竞赛就这样草草收尾。


图片

 在NOI2021现场,右一


进入大学后,得益于天津大学宽松的转专业制度,我顺利在大一下转入计算机科学与技术专业。在这里,我和其他优秀的选手作伴,一同交流学习,并重新踏上了算法竞赛之路。这半年里,我和队友征战全国各个赛站,共计4次获得ICPC/CCPC银奖。


图片

 本科期间所获奖项


图片

 在EC Final,左二



CSP认证经历


这次的CSP认证是4个小时做5道题目,采用即时反馈测试结果的赛制。


前两道只需要掌握基础语法模拟题意,比如用C++ 中的STL。


第三道是一个稍微麻烦些的模拟题,于是我暂时跳过去看后两道题。


第四道题数据范围较大因此需要离散化,注意到数据保证了有值的位置不会凭空增多,于是将这些位置用链表连接起来,维护前驱后继,再模拟题意操作。


第五道题一般会用到一些更高级的算法。像这次的题目,将操作分开考虑,对于修改可以用启发式合并维护,而它对到根的距离查询的影响,则可以转化为子树的权值减一,于是利用dfs序和树状数组即可解决。


这时回过头去看第三题,先写一个字符串处理的步骤,得到一个矩阵,然后按题面所给算法做高斯消元计算矩阵的秩,结合线性代数知识,即可判断齐次线性方程组的解是否唯一。写这种稍复杂的模拟需要细心一些,不过由于此时时间充裕,便能够心态良好地慢慢写完并一次通过。



备考经验


CSP认证的考试并不会用到太多高难度的算法,所以即使是没有算法竞赛经验的选手也能获得不错的成绩。在对所选语言基本语法熟练掌握的基础上,了解一些算法和数据结构相关的知识,并能正确判断算法时间复杂度,也有助于在认证中得到更高的分数。


除了对算法的掌握,一定的思维训练可以使自己更敏锐地反应出题目性质和解决思路。可以尝试打一打Atcoder和Codeforces上的比赛,这些题目通常不需要太多前置知识,主要考察能否熟练应用简单算法解决问题。


关于比赛本身,因为是即时反馈的IOI赛制,所以不用担心在不知情的情况下挂分。


CSP认证是允许携带纸质材料的,可以提前打印一些自己熟悉的算法和数据结构模板,或是不方便记忆的数学性质和结论。


开题的顺序是自由的,发现某道题目不太好做可以暂时跳过或者只写部分分。这次CSP认证考试中,我将不太好处理的模拟留到了最后,使得自己有充足的时间应对不擅长的题目。


要仔细观察数据范围,考虑时间复杂度是否允许通过,经验上讲如果粗略估计计算次数超过1e9则可以考虑算法的优化。此外数据性质也可能会提示做法,比如注意到这次的第四题的数据性质,就使得我可以用一种比较简单的做法通过。


尽管IOI赛制允许猜测结论并提交尝试,但我个人习惯是先把细节想清楚,包括性质证明和算法流程,再动手写代码,以避免陷入代码写成后再反复修改BUG的窘境。



结语


算法的巧妙令人着迷,而 CSP 认证的举办也让算法之美为更多人所知。


受算法竞赛经历影响,我现在也在辅修数学双学位,试图对算法背后的数学原理有更深刻的理解。祝愿 CSP 能越办越好,让更多选手提升自己的能力,展现自己的风采。