NOIP 2018 复习大纲

## 算法设计基础 ### 枚举 枚举子集、枚举子集的子集，枚举排列（`next_permutation`），*FMT*。 ### 贪心 区间选取、哈夫曼树 ### 单调枚举 二分法、倍增法（注意数组维度优化）、尺取法。 ### 分治 归并排序（逆序对） ### 高精（压位高精） ## 搜索 ### 状态设计 ### 状态评估 ### 状态转移 ### Meet in the Middle ### 迭代加深 ## 动态规划 ### 背包问题 01背包，完全背包，多重背包，分组背包 ### 树形dp 点分治 ### 区间dp ### DAG上dp ### 数位dp ### 状压dp ### 动态规划优化 单调队列优化、四边形不等式 ## 字符串 ### KMP 字符串匹配，求字符串周期，公共前后缀树（next） ### Hash 用Hash匹配字符串和子串 ## 数据结构 ### 链表 ### 队列 单调队列 ### 栈 单调栈 ### ST表 ### 哈希表 `unordered_set`，`unordered_map` ### 并查集 带权并查集 ### 树状数组 ### 线段树 ### 平衡树 Treap，`set`，`map`，离散化（排序离散化、Treap离散化） ### `bitset` ## 图论 ### 建图 虚拟点（超级源、超级汇、超级中间点）、拆点（扩展状态）、虚拟边，重新建图 ### 拓扑排序 DAG，判环 ### 最短路 差分约束 ### 最小生成树 最小生成树，最优比率生成树 ### SCC,BCC 割顶，桥，缩点 ### 二分图 二分图判断、染色，*二分图匹配* ### 树的基本性质 树的直径、重心 ### 树上倍增 LCA及以LCA为基础的统计 ## 数学 ### 埃筛,欧筛 求$\varphi$函数 ### $\gcd,\text{exgcd}$ 不定方程 ### 同余 kasumi，逆元（费马小定理、$\text{exgcd}$、线性递推），模合数的技巧（分母整除分母时的做法和质因数分解向量的做法） ## 考试技巧 ### 数据生成 Python生成序列、树、DAG、图 ### 对拍 Shell, diff