概述
本系列指南旨在帮助新同学快速入门算法竞赛的相关概念,并尝试帮助大家搭建一条目前看来较为可行的学习路线。
算法竞赛的考察内容
虽然 XCPC 往往被称为 “XXX 程序设计竞赛”,但是这里的程序设计一般均指代“利用算法与数据结构来编写程序,尝试在较优时空复杂度下解决某问题”,而非“使用开发框架来为特定方面问题来编写软件工程”。
因此,不同于工程类竞赛(如软件杯、服务外包等),我们并不需要构建一套大型的软件系统,而是单纯编写一个较小规模的程序(但这并不意味着它很好写)来解决试题中给出的特定问题。从我个人的角度来看,比起“程序设计竞赛”,我觉得它被称呼为“需要编程解决的数学竞赛”更合适一些。
因此,在算法竞赛中,卓越的代码编写能力和对软件工程知识的了解并非必需(当然,有了更好),最主要的还是对于各类型复杂算法和数据结构的掌握程度、对于各类算法问题的常用建模与 trick、以及在高竞技场景下的抗压能力。
常见算法竞赛
ICPC:国际大学生程序设计竞赛,含金量最高的算法竞赛(大学阶段),因为以前由美国计算机协会赞助而得名“ACM”。该项竞赛的赛制为ACM-ICPC赛制。
对于中国大陆区域,ICPC 每年 8-9 月举办网络赛,随后在 10-12 月举办若干区域赛(等级一致,没有高低之分),并在次年年初会举办一次EC-Final(东亚区决赛,但实际上基本都是大陆学校,行政等级略高于区域赛),随后在 7-8 月举办 World Final(全球总决赛,基本需要各个赛站的前五左右,每个学校至多一支队伍)。
CCPC:中国大学生程序设计竞赛,除了行政级别、组织单位等不同,其余内容几乎完全一样。(参加、承办的人基本都是同一批)
JSCPC:江苏省大学生程序设计竞赛,一般在每年的 5-6 月,隶属于 CCPC 系列竞赛中,其成绩会被列入当年 CCPC 区域赛名额划分的参考依据。
蓝桥杯:一项计算机/电子方向的大型竞赛,其中的“软件类”为算法竞赛,采取OI赛制。
天梯赛:一项大型竞赛的分项目,采取 IOI 赛制
CSP:CCF 专业级软件能力认证,其成绩也是参加 CCSP 的入场券
CCSP:每年 11 月左右,半个算法竞赛(后面的题更偏向工程),12 小时的耐久折磨(
百度之星:最为出名的企业承办的大型算法竞赛,采取 ACM 赛制
NOIP/省选/NOI/WC/CTSC/IOI:中国大陆地区信息学奥赛的系列比赛(从前到后分别为省级联赛、省队选拔、全国决赛、冬令营、国家队选拔、全球决赛),仅作了解即可
校队成员的准备路线(推荐)
本路线主要针对基础相对薄弱的同学
大一上学期:参加校赛并获得较好成绩
大一寒假:参加低年级组集训,学习并应用大部分基础算法
大一下学期:
- 继续巩固基础算法,并尝试了解一些常用高级算法(如线段树)
- 开始打 CF,争取能够 Div2 稳定 2 题 / Div3 稳定 5 题,尝试打到 Rating 1300
- 积极参加一些其他学校的公开校赛(新生赛),并报名尝试看看蓝桥杯等
- 队内可以尝试找找适合的队友
大一暑假:
如果你决定在算法竞赛领域继续深造、进入 ACM 队的话,这个阶段将成为你与非职业选手的分水岭。如果你选择退出,那么你的功底也足够应付以后非算法竞赛环境下的大部分考核场合(例如面试算法、保研/考研机试、蓝桥杯非C++组等)
- 参加牛客/杭电多校,感受真实的准XCPC比赛风格及难度
- 参加专项训练,继续学习相关知识点
- 多校比赛后,能够将铜牌级别题目学习并自行写一遍,并尝试掌握对应知识点
- 如果你发现基础不够,继续回头补基础算法(可以尝试看看牛客的新生冬令营)
- 继续打CF,争取看看能不能打到 1600(Div2 稳定 3 题)
- 此外,到了这个阶段,你已经可以尝试去自己写博客,记录自己的学习笔记了(学了哪些知识点和技巧,遇到了什么有趣的好题目之类)
大二及以后:
如果你能坚持到这里,那么基本上你将作为河海大学 ACM 队的正式成员,代表河海大学参加后续的 XCPC 系列比赛。对于日常训练,基本上就是暑假阶段的强化(寒假多打一个冬令营,暑假的多校要参加更多/补更多,CF 开始尝试冲刺 Div2D,并开始学习 Div2E,等等)。
学习方向
本部分的详细内容将在后续章节进行详细阐述。
- 语法与代码能力
- 基础算法
- 高级算法
- 思维