noip考点

未分类

基础

• 模拟
• 贪心
• 搜索（dfs，bfs，剪枝，双向搜索）
• 二分

动态规划

一般类型多种多样，没有非常系统的分类。比较考思维，多练多做题才可以熟练的找到动态规划的状态，找出转移方程。

• 背包（基础）
• 区间
• 树形dp（在树上dp）
• 数位dp（往往求解合法的数字个数）
• 状态压缩dp
• Dag（有向无环图）上的dp

图论

• 树（遍历，存储，直径，重心，dfs序，基环树，树链剖分）
• LCA（最近公共祖先，倍增）
• 最短路（dijkstra，floyd）
• 拓扑排序（可以和动态规划结合）
• 最小生成树（kruskal）
• 联通分量与强连通分量（tarjan，缩点，割点等相关概念）
• 启发式合并（一种降低复杂度的技巧）

数据结构

• 堆
• 队列（单调队列）
• 栈（单调栈）
• st表
• 并查集
• hash表
• 树状数组（常数小，代码少）
• 线段树（用的很多，扩展性强）
• 分块（以及莫队：询问离线时的一种优化的暴力）

字符串

• kmp
• AC自动机
• 字典树（Trie）
• 二分+hash（本质就是暴力算法，往往能处理很多字符串算法做的事情）

数论

• 欧几里得算法和扩展欧几里得
• 逆元
• 筛素数
• 快速幂
• 组合数相关
• 中国同余定理