noip知识点汇总

OI

基础算法

贪心、枚举、二分（分治）、倍增、模拟、构造。

搜索

bfs、dfs、剪枝

启发式搜索、迭代加深搜索

动态规划

背包、树形动规、记忆化搜索、递推

区间dp、序列dp、状压

优化（数据结构）

图论

图

最短路、差分约束

最小生成树

并查集

拓扑排序

二分图染色、二分图匹配

tarjan

分数规划

树

树上倍增（lca）

树的直径、重心

dfs序、树剖

数论

gcd（lcm）

exgcd、逆元、同余方程

高斯消元

线筛

快速幂、快速乘

组合数学、容斥

矩阵

概率

数据结构

链表、队列（单调队列）、栈（单调栈）

堆（优先队列）、st表、hash表

线段树、树状数组

字典树

分块

字符串

读入、输出

高精

KMP、AC自动机、trie树（图）