*表示只会用库
+表示不熟悉
?表示待学
数据结构:
基本数据结构:
数组
链表
栈(STL/stack)
队列(STL/queue,STL/deque)
串
HASH表
高级数据结构:
块状链表{数组+链表}
堆(STL/priority_queue)
线段树
并查集
字典树+
二叉搜索树+
左偏树?
平衡二叉搜索树[AVL?,RBTree?,Treap,Splay?](STL/map,STL/set)
算法:
通用:
贪心[矩阵胚+]
递归,分治,递推
搜索[DFS,BFS,ID,Astar,IDAstar,最优性剪枝,可行性剪枝]
动态规划[树形动规,状态压缩+,利用单调性优化,四边形不等式]
排序:
冒泡,插入
快排(STL/sort)
图论:
最小生成树[Prim,Kruskal]
最短路[Dijkstra,SPFA(Bellman-Ford),Floyd]
网络流-最大流[Edmonds-Karp,ISAP,Dinic,Relabel-to-front]
网络流-费用流[SPFA增广]
有向图强联通分量[Tarjan]
拓扑排序
匈牙利算法
欧拉路,欧拉回路
树的直径
最小环[Floyd]
最近公共祖先,LCA[RMQ],Tarjan
计算几何:
凸包[Graham]
半平面交[朴素O(n^2),分治?]
字符串匹配:
KMP
AC自动机
后缀数组
Rabin-Karp
博弈论:
Nim取石子游戏
SG函数
敌对搜索
数论:
辗转相除
扩展辗转相除
计数问题:
生成函数+
排列组合
容斥原理
抽屉原理
置换群?
代数:
高斯消元
高精度数