NOIP 知识清单 (in detail)

- ## 基础算法 1. 贪心 2. 枚举 3. 分治 4. 二分 5. 倍增 6. 构造 7. 高精 8. 模拟 - ## 图论 - ### 图  1. Dijkstra 2. SPFA 3. Floyd 4. 差分约束 5. Kruskal 6. Prim 7. 并查集 8. 扩展域 9. 拓扑排序 10. 二分图染色 11. 二分图匹配 12. Tarjan找scc 13. 桥 14. 割点 15. 缩点 16. 分数规划 - ### 树  1. 树上倍增（求LCA） 2. 树的直径、树的重心 3. dfs序（欧拉序列） 4. 树链剖分 - ## 数论 1. GCD（最大公约数）、LCM（最小公倍数） 2. 埃氏筛法 3. EXGCD（扩展欧几里得算法） 4. 求解同余方程、逆元 5. 快速幂 6. 组合数学 7. 矩阵 - ## 数据结构 1. 链表 2. 队列 3. 栈 4. 堆 5. 单调队列 6. 单调栈 7. ST表 8. Hash表 9. 树状数组 10. 线段树 11. 字典树 12. 分块 - ## 动态规划 1. 递推 2. 背包DP 3. 树形DP 4. 记忆化搜索 5. 区间DP 6. 序列DP 7. DP优化（不涉及斜率优化、四边形不等式等等） - ## 搜索 1. 暴搜（dfs、bfs） 2. 搜索的剪枝 3. 启发式搜索（A*） 4. 迭代加深搜索、IDA* 5. 随机化搜索 - ## 其他算法 1. STL的基本使用方法 2. 脑洞的正确使用方法 3. KMP 4. 状态压缩 5. RMQ 参考自http://blog.csdn.net/fengyingjie2/article/details/54347599