📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 8372| 回复: 14
跳转到指定楼层
上一主题 下一主题
收起左侧

[其他] 【分享】刷题算法知识点脑图总结——来自多次 ACM-ICPC 金牌获得者

   
全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 vuuiwo 于 2024-7-22 22:49 编辑

jiangshibiao 大佬 zju 毕业,拿了好多枚 ACM-ICPC 区域赛金牌。为了给从零开始学 ACM 的同学指导算法知识点,把他以前保存了一个整理的相对全的 OI 知识图标上了难度和注释。


大佬把难度分为了 1,2,3 三层(未标的要不不算知识点,要不是太偏的知识点):


1. 熟练应用难度 1,leetcode 周赛题应该能乱杀了。
2. 熟练应用难度 1 和 2,差不多能和队友混个 acm 金牌了。
3. 熟练应用难度 3,应该能单挑拿 acm 金 / 组队出线 WF 了。


大佬是 21 年做的分享,想来知识点应该变化不会太多。如果想乱杀 leetcode 周赛我们还是可以参考一下知识点 1 的。

完整图在帖子最后

本人对知识点 1 的整理如下(里面好多陌生的概念,面试应该不会涉及吧 😢):


- 博弈论
  有关博弈,只需要深刻理解 nim 游戏和 SG 函数的推导。进一步提升需要靠的是题目的练习
  - Nimm Game
  - SG 函数
- 图论
  - 最短路
    最短路需要会 DIJ,SPFA 和 Floyd,其中前者最常见,要熟练掌握 DIJ 的堆优化。
    - SPFA
    - dijkstra
      - 堆优化的 dijkstra
    - Floyd
  - Tarjan
    需要学会 tarjan 找强连通分量。进一步拓展就是求割边和割点。
    - 强连通分量/缩点
  - 拓扑排序
  - 树论
    - 生成树
      - 最小生成树
        - Kruskal
        - Prim 及其堆优化
      - LCA
        LCA 是最常见的树上询问,推荐优先学倍增。
        - 倍增
      - dfs 序
        dfs 序是最基础而有用的工具
      - 树的遍历
        - 前序
        - 中序
        - 后序
      - 树的直径
      - 树的重心
- 数据结构
  - 队列
    - 单调队列
      很经典的优化方法
    - 优先队列(堆)
    - 双端对接
  - 栈
    - 单调栈
  - 堆
  - 并查集
    会按秩合并和路径压缩两种优化。
  - hash 集
  - 链表
    - 双向链表
  - st 表
    一种有效的序列处理工具。
  - 树状数组
    一维树状数组是很基础的优化工具。
    - 树状数组求逆序对
  - 线段树
    线段树也是较为基础的优化工具。
  - Trie 树
  - STL
    C++ 的 STL 很好用,最常用的是 vector, set, map 和 bitset,其他的用不用看个人习惯。
    - map
    - set
    - vector
- 搜索
  - bfs
  - dfs
  - 记忆化搜索
  - 剪枝
    剪枝其实是一个很自然的方法。
    - 可行性剪枝
    - 最优性剪枝
- 字符串
  - KMP
  - 字符串 Hash
    常用而灵活的字符串处理工具。
  - manacher
    最经典的回文串处理工具。
- 计算几何
  - 基础知识
  - 向量
    - 点积
    - 叉积
    - 基础知识
  - 凸包
    最经典的计算几何应用。推荐学习两种方法,一是 graham 扫描法,二是排序两遍得到上下凸壳的方法。
- 数论
  - 基础知识
    - % 理论
  - 素数
    筛素数和分解质因数是数论里最基础的部分。
    - 暴力判素数
    - 筛法求素数
      - 埃拉托色尼筛
      - 线性筛(欧拉筛)
    - 分解质因数
  - 欧拉函数
    - 欧拉定理
  - 快速幂
    必须要掌握的思想。
  - gcd
    - 辗转相除法
      - gcd
      - lcm
  - 矩阵
    - 矩阵快速幂
      用矩阵快速幂优化线性递推。
  - 狄利克来卷积
    积性函数的概念。
  - 容斥原理
    - 抽屉原理(鸽巢原理)
  - 费马小定理
  - 逆元
    - 线性求逆元
    - 费马小定理求逆元
  - 高斯消元
    很经典的方法,可以用来解方程组、求矩阵逆。
  - 排列组合
    - 杨辉三角
      预处理+O(1) 求 10^6 以内的组合数。
  - 数列
    - 斐波那契数列
    - 卡特兰数
    - 等差、等比数列
      - 通项公式
      - 求和公式
  - 概率和期望
- 动态规划
  - 简单 dp
  - 背包 dp
    - 01 背包
    - 完全背包
    - 多重背包
  - 区间 dp
  - 状压 dp
    - 普通状压
      - 枚举子集 dp
  - 数位 dp
  - 树形 dp
  - 环形 dp
  - 期望 dp
  - 记忆化 dp
  - DAG 上的 dp
  - 多维动态规划
- 其他算法和思想
  排序就直接调用 C++ 的 sort。学会如何手写 O(NlogN) 的快排、归并和 O(N) 的桶排。同时了解 O(N^2) 的插排、选排、冒泡的思想。
  - 二分
    - 二分答案
    - lower_bound
    - upper_bound
      C++ 提供的函数。
  - 贪心
  - 枚举
  - 暴力
  - 离散化
    学会用 map/sort 离散。
  - 模拟
    这是一种考验耐心和细心的能力。
  - 排序
    - 快速排序(sort)
      - 重载运算符
    - 归并排序
      - 归并排序求逆序对
    - 桶排
    - 插入排序
    - 选择排序
    - 冒泡排序
  - 前缀和
  - 高精度
    简单的高精度题直接上 py 或 java。如果一定要 C++,数据量大时要用到压位的技巧。
  - 递推、递归
    - 矩阵加速递推
  - 位运算
  - 打表
    打表是一种有趣的方法。
    - 打表找规律
  - 卡常








补充内容 (2024-07-22 23:19 +08:00):

忘了说,对OI感兴趣的话,也可以看看 [OI wiki](https://oi-wiki.org/) 这个网站

评分

参与人数 15大米 +44 收起 理由
bryanjhy + 20 给你点个赞!
AndrewAct + 1 给你点个赞!
14417335 + 10 很有用的信息!
Joey60209Joey + 1 赞一个
小丸几 + 1 欢迎分享你知道的情况,会给更多积分奖励!

查看全部评分


上一篇:LeetCode上面bytedance和tiktok分开了
下一篇:分享三道在45-60分钟里写的系统设计题答案
推荐
nhqgoal 2024-7-23 00:57:13 | 只看该作者
全局:
你这个太overoveroverkill了,直接猛刷medium就行了
回复

使用道具 举报

全局:
面试有人会问SG函数?你怕是在逗我。。。
回复

使用道具 举报

全局:
竞赛的话么可以看guide to competitive programming(之前有个免费版的competitive programming handbook),虽然看完了不能保证拿牌子,但是基本的知识储备应该是有了
回复

使用道具 举报

🔗
 楼主| vuuiwo 2024-7-22 22:45:18 | 只看该作者
全局:
知识点楼主纯手打,求米求米,想看其他大佬的面经

评分

参与人数 1大米 +1 收起 理由
scuba + 1 赞一个

查看全部评分

回复

使用道具 举报

🔗
basketwang 2024-7-22 23:40:14 | 只看该作者
全局:
太猛了 感谢
回复

使用道具 举报

🔗
wuwendongxi 2024-7-23 00:27:26 | 只看该作者
全局:
太复杂就没人学。纯表彰你手打知识点。
回复

使用道具 举报

全局:
一张图告诉你程序员凭什么工资高
回复

使用道具 举报

🔗
james47 2024-7-23 02:09:02 | 只看该作者
全局:
面试不需要会这些
回复

使用道具 举报

🔗
红A 2024-7-23 02:46:27 | 只看该作者
全局:
同zju,

注意竞赛和面试的准备方向是不一样的。以上高难的dp部分都不会出现在面试里。
如果是对竞赛感兴趣,可以多准备。
如果是对找工作面试有兴趣,显然有更有效率的方式。类似楼上的median和简化的知识点。

然而市场才是最大的因素,刷题能到3.5题周赛也够了大部分面试了。
回复

使用道具 举报

全局:
overqualified 实际上只需要浙江初中oi学生中等水平就可以完爆coding面了..
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表