算法设计基础
枚举
枚举子集、枚举子集的子集,枚举排列(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为基础的统计
数学
埃筛,欧筛
求函数
不定方程
同余
kasumi,逆元(费马小定理、、线性递推),模合数的技巧(分母整除分母时的做法和质因数分解向量的做法)
考试技巧
数据生成
Python生成序列、树、DAG、图
对拍
Shell, diff