Diary II
大家好,我是Stockholm_Sun,目前是一名高三学生,现就读于山东省聊城第一中学。
写这个博客并不是想让大家认识我,初衷是想要帮助自己更加学好信息学奥赛。距离NOIP就剩下30多天了,今天我想总结一下我们学过了什么,做一个简要的小结。心路历程啥的等退役了,或者2018年高考结束之后再和大家分享(讲真,信息学奥赛真的是一段比较难忘而且煎熬的经历)。
只是个人总结,请大佬们不要群聚而笑之,请蒟蒻也不要认为我在炫耀。
搜索
- DFS(深度优先搜索)
- BFS(广度优先搜索)
- A*(启发式搜索,未代码实现过)
- 记忆化搜索
动态规划
- 01背包
- 完全背包
- 部分背包(代码实现过,但不熟练)
- 记忆化搜索
- 树状动态规划(仍需巩固)
- 简单二维动态规划
- 简单一维动态规划
- 动态规划的单调队列优化(仍需巩固)
数据结构
- 数组
- 栈
- 队列
- 单调队列(数组实现)
- 链表
- 树(树状数组,线段树)
- 图
- 堆(大根堆,小根堆)
- 并查集
图论
- 最短路径算法(Dijkstra及其堆优化,SPFA,Floyd)
- 生成树(Prim,Kruskal)
- 树(LCA倍增实现,Trie树不熟练)
- 差分约束系统(最短路,最长路)
- 强连通分量(Tarjan)
- 拓扑排序
数论
- 数学归纳法
- 组合数
- 欧几里得算法
- 扩展欧几里得(不熟练)
- 数论倒数(逆元)(不熟练)
- 乘法原理
模拟算法(要求低,实用性强)
字符串
- 字符串hash(冲突,构造)
- LCP(最长公共前缀,二分+哈希)
- 哈希表
- KMP(只会打模板)
- Manacher(思路掌握)
- exKMP(扩展KMP算法,不熟悉,可以通过掌握二分+哈希来取代)
- Trie树(字典树)
其他算法
- 分治算法(二分查找,二分答案及其在图上的应用)
- 倍增算法(LCA,ST表(需要巩固))
- 贪心算法
- RMQ问题特殊解法(需要巩固)