OI/ACM/算法 入门学习指导经验贴

最近有不少人问我OI/ACM/算法到底应当如何入门,为了方便起见,我专门写一篇文章来讲一讲自己的认识。

0 个人水平

个人在初中接触C++,高中自学数据结构与算法、刷题。按照OI标准衡量,水平应当在省一(虽然得奖只得了个省二);按照ACM/ICPC标准衡量,水平应当在区域赛铜牌(得奖ACM Cu);按照蓝桥杯标准衡量,水平在国二。所以如果和经过专业训练清北的IOI金牌、ACM大佬们相比,肯定是菜鸡。

1 适用人群

根据我个人的水平,这篇经验指导不适合的人群包括:

  • 有专业教练指导的ACM/OI选手
  • 已经得过省二以上的OI选手

主要适合以下人群阅读:

  • 零基础,完全未曾入门算法竞赛,并且无教练指导的同学,想要通过自学取得一个相对不错的算法竞赛成绩(OI省一、ACM铜)
  • 有很少编程经验,想通过自学和刷题找工作的同学

2 预备条件

  • 能够编程、上网的电脑
  • 一颗持之以恒、不断拼搏努力的心

要想把任何一件事做的成功与出类拔萃,都不是一件容易的事情,需要持之以恒、不断的努力。我个人认为,练习和实践是最好的提升能力方法。具体反映到算法的入门上,就是要多多刷题。刷题过程中可能遇到各种困难,一定要坚持住,最后一定能够取得属于自己的成功!

3 入门途径

要想入门OI/ACM,主要分为两个阶段:(1)学习C++、学习数据结构与算法;(2)做各种各样的练习题目。下面我列举几个较好的入门渠道。

3.1 入门MOOC

    • (中国大学MOOC)北京大学,郭炜
      • 程序设计与算法(一)C语言程序设计
        • https://www.icourse163.org/course/PKU-1001553023
        • 本门课程属于非常基础的C/C++语言教学,将会是后续学习各类数据结构与算法的重要基础,所以务必需要认真学习
      • 程序设计与算法(二)算法基础
        • https://www.icourse163.org/course/PKU-1001894005
        • 本课程属于比较简单的算法入门,务必认真学习,学习完毕之后差不多水平≈OI省三
      • 一定要跟从指导,完成配套的课后作业,进行OnlineJudge评测,在线测评是提高编程能力最有效的方法
    • (中国大学MOOC)浙江大学,陈越、何钦铭:数据结构
      • https://www.icourse163.org/course/ZJU-93001
      • 本课程覆盖了最为基础和常用的数据结构,是重点高校中数据结构教授难度较为适中的一个,建议认真学习并完成配套课后题目
      • 学习完成该课程后,可以参加PAT甲级测试(PAT后文会提及),如果能够取得一个较高的分数(85以上),那么证明你已经具有超过绝大多数科班学生的编程能力及水平,可以拿着PAT甲级的证书直接去找工作了^v^,学习完毕之后差不多水平≈OI省二
    • (学堂在线)清华大学,邓俊辉
      • 本课程难度较高,对数据结构各项内容的讲解也更加深刻。对应的,评测系统STL中不含各类算法与数据结构的头文件,所有的数据结构与算法都需要自己造轮子。评测系统直接使用清华大学的OJ。
      • 与此同时,本课程中还包含大量对于普通学习者来说,可能一辈子都不会用到的数据结构。推荐数据结构的爱好者,或者愿意多学习、扎实基础的同学进行学习。
      • 数据结构(上)
        • https://www.xuetangx.com/course/THU08091000384/
        • 一个合格的OI省一选手,应当掌握本课程中全部内容(我本人没学过双连通分量[狗头],所以不合格)
      • 数据结构(下)
        • https://www.xuetangx.com/course/THU08091002048/
        • 本章中个人认为比较超纲,可能很少用到的内容包括:高级搜索树、左式堆、串中除了KMP和蛮力匹配之外的其他算法

3.2 入门书籍

由于我本人主要是看MOOC学习知识、做OJ题目训练的,看书看的比较少,所以对于书籍仅作一大致的推荐。

  • CCF中学生计算机程序设计(入门、基础、提高、专业篇),中国计算机学会 (其中专业篇到现在还没出版)
  • 挑战程序设计竞赛,(日)秋叶拓哉,(日)岩田阳一,(日)北川宜稔
  • 算法竞赛入门经典,刘汝佳

4 OJ推荐

OJ是Online Judge的缩写,是在线评测系统的意思,该系统通过自然语言的形式向你呈现出程序编写的要求,由你手工编写代码,并将其提交到该系统中。系统可以通过黑盒测试的方式,对你的程序进行评测,判断你的程序是否编写正确。

使用OJ进行编程训练是提高编程能力最有效的方式之一。下面列举并推荐几个我曾经用过的OJ:

  • 洛谷(面向OI选手)
    • https://www.luogu.com.cn/
    • 一个非常好的OJ,题目质量高且有对应的题解,社区氛围好,有管理员维护
    • 他们家还卖网课,我之前也报过他们家的网课
  • Vijos(面向OI选手)
    • https://vijos.org/
    • 感觉站长已经不怎么维护了,但是评测还是应该能正常用的。。。
  • POJ(面向ACM选手)
    • http://poj.org/
  • OpenJudge
    • http://openjudge.cn/
  • 拼题A(PAT竞赛官方OJ,浙江大学陈越老师背书)
    • https://pintia.cn/
  • Virtual Judge(虚拟评测,利用Web爬虫调用其他网站的评测机评测)
    • https://vjudge.net/
  • USACO
    • https://train.usaco.org/usacogate
  • Codeforces
    • http://codeforces.com/
  • CCF中学生程序设计在线评测系统(CCF官方OJ)
    • http://oj.noi.cn/oj/
  • Leetcode(面向找工作同学)
    • https://leetcode.com/

5 竞赛推荐

5.1 高中阶段竞赛

高中阶段的算法竞赛只有信息学奥赛(NOIP),现在应该已经改名为CSP-J / CSP-S了。
官网:https://www.noi.cn/

5.2 本科阶段竞赛

我参加过的传统程序设计竞赛应该就是下面这些。

  • ACM / ICPC
  • 团体程序设计天梯赛
    • https://gplt.patest.cn/
  • 蓝桥杯
    • https://dasai.lanqiao.cn/

5.3 程序设计能力测试

不同于竞赛,“程序设计能力测试”更加商业化,主要是面向找工作的同学和保研的同学,难度相比竞赛也要简单许多,一年举办多次,可以随意报名,只要交钱就行。详细信息可以去看他们的官网。我知道的有两家:

  • PAT
    • https://www.patest.cn/
    • PAT是浙江大学办的,分:顶甲乙级,三级测试。满分一百分。一般考到甲级就够用了。和很多公司联合推出了招聘优惠措施,除此之外还可以做为浙大研究生上机复试成绩。
  • CSP
    • https://cspro.org/
    • CSP是中国计算机学会办的,满分500分。一般300分左右就是前5%。和很多公司、大学联合推出了优惠措施,除此之外还可以做为北航研究生上机复试成绩。

6 NOI大纲及知识点

可以根据NOI大纲对自己的算法各知识点进行查漏补缺,链接附后。
要想达到OI省一水平(这个水平在一般性编程工作中完全足够),需要学习的知识点应当包括:

    • ANSI C
    • C++ STL (Standard Library)
    • 线性表
      • 数组
      • 链表
      • 队列
      • 二叉树
        • 二叉树的遍历:前序、中序、后序
        • 二叉树的重构
        • 哈夫曼树
        • 二叉堆
      • 二叉搜索树
      • 树状数组
      • 线段树
      • 存储:邻接矩阵与邻接表
      • 遍历
        • 广度优先遍历BFS
        • 深度优先遍历DFS
      • 二分图、欧拉图、哈密尔顿图
      • 单源最短路:Dijkstra、SPFA
      • 多源最短路:Floyd
      • 最小生成树:Prim、Kruskal
      • 拓扑排序
    • 哈希表
      • 哈希函数构造
      • 哈希冲突的解决方法
        • 拉链法
        • 开放定址法
    • 基础算法
      • 枚举
      • 模拟
      • 贪心
      • 递推
      • 递归
      • 二分
      • 分治
    • 排序算法
      • 选择排序、插入排序、冒泡排序
      • 快速排序、堆排序、归并排序
      • 桶排序
    • 搜索算法
      • 剪枝
      • 记忆化搜索
    • 简单的动态规划
    • 数论
      • 整除、因数、倍数、指数、质数、合数等概念
      • 辗转相除法
      • 埃式筛法
      • 同余
      • 逆元
    • 组合数学
      • 排列组合
      • 杨辉三角
      • 二项式定理
      • 容斥原理

全国青少年信息学奥林匹克系列竞赛大纲:https://www.noi.cn/xw/2021-04-02/724387.shtml

文中可能还有写的不详细或者有问题的地方,欢迎大家给我留言!

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注