提高级算法
必要知识点
NOI大纲
大纲每年都在更新,这里给一份2023 年的,建议大家用的时候预先搜一下
- 2.2 提高级中的所有 6 级算法(熟练掌握)
- 2.2 提高级中的 7/8 级算法(能够看着板子去写相对模板的题目)
- 2.3 NOI 级中的必要数学算法(指线性代数、高等数学、概率论与博弈论)
- 在模板的协助下,一定程度理解树链剖分、可持久化线段树、分块、Manacher 算法与网络流(有概念就行)
- 对于2.3 NOI级中的级别 8 计算几何算法有一定程度的理解,并能尝试解决模板题
以下书籍/网课中,你认为学习难度较低的算法知识点
阶段目标
完成该阶段的学习后,我认为选手应该以下水准:
- 蓝桥杯省赛国三/国二(CA组)
- 天梯赛个人三等奖/二等奖
- CSP 300+
- 能够理解 ACM 铜牌题的所用算法(并在题解帮助下尝试理解部分银牌题的)
推荐书籍/网课
《算法竞赛入门经典(第2版)》(推荐:4星)
在这一阶段,我们就很有必要对除最后一章外的大部分内容进行再次学习了
《挑战程序设计竞赛》(推荐:4星)
这也是一本不错的算法竞赛书籍,适合简单学习算法后的选手进行阅读。这本书覆盖的知识面比较广,但是对于对应专题并没有很深的拓展,适合用它展开面的学习。
《深入浅出程序设计竞赛提高篇》(推荐:5星)
截至 2024.9.15,这本书还没有正式版本销售,仅能作为洛谷月赛年卡的附赠品获得(但这样也很值了)
《算法竞赛进阶指南》(推荐:5星)
大体掌握了算法入门+提高部分,就可以来看看这本 lyd 大神写的书了。这本书分多个专题,每个专题都进行了相当深入的探究,尤其是图论和动态规划方面。这本书对标的是 OI 中等省份省队 + NOI 银牌水平,如果辅助学习其他的内容(如计算几何和一些书中没有提到的高级数据结构,字符串等知识点),可以更进一步到达ICPC 区域赛银牌/金牌水准
在该阶段,仅需要对于较为常见的知识点进行学习,其他部分可以简单了解一下
《算法竞赛》(推荐:Unknown)
一本较新的算法书籍,目录看起来像是一个较大的算法合集,应该很适合查阅吧,作为初次学习资料的效果无法确定
Acwing 算法提高课(推荐:4星)
洛谷网课 提高组冬令营/夏令营/秋令营/五一专题(推荐:2.5/3.5星)
五一的性价比还不错,前面的就算了(
牛客算法竞赛专题班——数据结构/图论/动态规划
在 合集链接 中可以找到,该阶段暂时仅推荐上面三个课程,对于较为困难的部分可以留到后面学
额外推荐题单
在这一阶段,我们同时需要承担两个任务:学习新知识点和巩固原有知识点。因此,该阶段的题目量是最大的。
牛客寒假 算法基础训练营
每年寒假都有,在 合集链接 中可以找到,但是不太全(最好的方式还是直接在牛客的比赛页面搜“寒假”,最早能追溯到 18 年)
虽然叫做基础训练营,但是它的题目难度覆盖范围极广(无论是知识点还是思维难度),全套做完后对能力提升有着极佳的帮助,即使不在暑假也值得花钱买一份去做
这更像是一份参考名单,可以帮助你迅速捋清楚算法竞赛中的常见知识点都有哪些
CF 刷题建议
多刷 1900 以下的题目,Div2 争取写到 3-4 题,努力把 Rating 刷到 1600-1700(能达到这一点,基本上就已经是队内比较靠前的选手了)。此外,你在赛后补题阶段可以尝试对 Div2E 难度的题进行补题了。