中级农民
- 积分
- 100
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2019-10-25
- 最后登录
- 1970-1-1
|
注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
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/) 这个网站 |
上一篇: LeetCode上面bytedance和tiktok分开了下一篇: 分享三道在45-60分钟里写的系统设计题答案
|