【金牌选手分享】针对零基础选手的C++算法学习路线

发布于 2023-07-30  1239 次阅读



我是ErikTse,如果你或你的朋友是计算机专业的新生,这个视频值得你收藏和转发给你的朋友们

不要再问up高中有没有打过oi(奥林匹克信息学竞赛)了,up是纯零基础选手,大一才开始学c语言的,现在是准大三,获得过一些不错的奖项,有ICPC亚洲区域赛(济南)银牌、CCPC全国邀请赛(湘潭)金牌、ICPC全国邀请赛(西安)铜牌。

有不少朋友都想要up出一期关于算法的学习路线,于是有了这期视频,其实这一份计划不仅能帮助你学习ACM竞赛,还可以帮助你准备蓝桥杯、RAICOM等相关竞赛,并且在算法面试、考研、保研的机试中实现乱杀。

以下是一份针对大一零基础选手的算法学习路线建议,分为大一上、下学期,大二上、下学期四个部分:

大一上学期

基础知识

学习一门编程语言,推荐 C++

掌握基本的数据类型、运算符、循环、分支、函数、数组等基本语法。

熟悉常用数据结构,如数组、链表、栈、队列等,这些都要会用数组来模拟实现,其中原因一个是加深自己对这一类数据结构的理解,另一个是这可以使得算法跑的更快,使用起来也更方便。

算法入门

学习算法基础知识,如时间复杂度、空间复杂度等,学会根据题目数据猜算法复杂度和打表

掌握基本排序算法,如冒泡排序、选择排序、插入排序(主要学习算法思想)等。

学习基础算法,如前缀和与差分、二分查找、双指针、离散化、快速幂、乘法逆元、gcd、lcm等。

学习基本的递归算法,如斐波那契数列、暴力搜索(包括剪枝和记忆化)、分治法等。

初步了解图论、动态规划、贪心算法等常用算法思想,整理一些动态规划、贪心的模型。

练习

刷入门级别的题目,如洛谷的入门题(建议刷够100题)。

可以去尝试打一打Atcoder Beginner Contest(推荐,一般题意比较明确,思维难度较低)或Codeforces Div4,赛后一定要补题并多写博客,总结做题思路和代码细节。

也推荐大家去打一打牛客小白月赛(中文题面),对新手比较友好。

一定要参加校内的 ACM 集训队或者社团,在群里多说话,不要怕被大佬嘲笑,即便可能问的问题比较低级但是也要勇敢提问,多与同学交流学习经验。

这时候很多学校会举办ACM新生赛,一定要参加并争取拿到较好的名次。

大一下学期

数据结构进阶

掌握树的遍历、图的遍历等基本算法。

熟悉STL中的优先队列、map、set、multiset、vector、lower_bound、upper_bound等常用数据结构和算法的用法。

学习线段树、拓扑图、并查集、树状数组等数据结构。

算法进阶

学习线性的动态规划算法,掌握背包问题(01背包、多重背包、完全背包、混合背包、二维费用背包)、最长上升子序列等经典问题,理解多重背包的二进制优化

学习贪心算法,掌握最小生成树(Prim和Kruskal)、最短路径(单源最短路Dijkstra,多源最短路Floyd)等问题的贪心思想。

初步了解数论,包括欧拉函数、欧拉定理、埃氏筛法(学习思想)、欧拉筛法、exgcd

这时候也是思维提升的关键时期,要注意总结各种乱七八糟的结论,有条件的可以适当证明,写成一片文章,时不时翻出来看看。

练习

洛谷普及-到普及的题(黄题),同样建议至少刷够100题(如果想看up带刷100题的uu们留下你的评论和弹幕,一键三连,点赞过1000必出这个系列)。

练习线段树、并查集、图等高级数据结构的相关题目,可以在闲暇的时间找几道题来做,并自己写一篇文章关于对这个数据结构的理解。

这时候很多学校会举办ACM校赛,一定要参加并争取进队,一般只有进队了才有后续参加比赛的资格。

可以去尝试打一打Codeforces Div2(一般可以做到C题),cf的比赛比较考察思维,而对数据结构的考察较少,赛后一定要补题并多写博客,总结做题思路和代码细节。

当然ABCDiv3的训练也不要落下,牛客小白月赛和练习赛也很不错,推荐去做一做。

大二上学期

算法深入

学习字符串算法,如 KMP 算法、Manacher算法等。

学习数据结构,如单调栈、单调队列、trie等等。

学习高级的图论算法,如SPFA、二分图、DAG-DP、Tarjan强联通分量、倍增LCA、Tarjan离线求LCA等。

学习博弈论的相关知识,如基本博弈类型(巴什博奕、尼姆博弈、威佐夫博弈)、SG函数、mex操作等等。

简单的计算几何

学习计算几何的基础知识,如向量、点、线、面、叉乘等基本概念。

掌握平面几何和立体几何中的基本算法,如点线距离、线面交、求二维凸包等。

练习

刷洛谷绿题到蓝题。

练习字符串匹配、图论等高级算法的相关题目,要写更多dp的题目,尽量各种类型的都做一些,比如计数dp(一般是求方案数)、存在性dp(一般求某种情况是否存在、可行)、区间dp(尝试四边形不等式优化)、期望dp、数位dp、状压dp、树上dp(这个往往很难)

参加 ACM 竞赛,多参加省内外的比赛(一般在牛客竞赛上可以看到),积累比赛经验和认识到更高水平的选手。

这时候可以多去打Codeforces上的比赛(Div2,Div3),一定要补题,写博客,尽量把分数刷上1600。

这个时间段也一般是第一次打正式比赛的时间,好好发挥一下~

推荐大家在正式比赛前,和队友进行几场vp,对正式赛题目有一个了解。

大二下学期

这时候的练习就比较自由了~

尽量多去提升思维,遇到不会的算法再去学,没必要不断的学习新的很复杂的算法(这样的性价比比较低)。

算法拓展

学习树剖、主席树(可持久化线段树)等高级数据结构和算法。

学习分块、莫队、Pollard Rho大数质因数分解、dp中的斜率优化、矩阵快速幂、差分约束系统等算法。

学习更深层的数论和组合数学,包括莫比乌斯反演、约数定理、生成函数、高斯消元、线性基等等。

练习

这时候尽量跟队友分工,常见的分工是三个人分别学dp(字符串)、图论(数据结构)、数论(博弈论)。

持续打CodeforcesAtocder保持手感,牛客小白月赛要尽量做到ak(all kill全部做完)

参加 ACM 竞赛,多参加全国性的比赛,提高自己的竞赛水平。

以上是一份大一零基础选手的 ACM 算法竞赛学习路线建议,希望对你有所帮助。

需要注意的是,除了以上的学习和练习,平时的补题写题解、阅读题解、自己讲给自己(同学)听等也是非常重要的,希望你能够坚持下去,不断提升自己的编程能力和算法竞赛水平。

19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2023-07-30