中级:
一.基本算法:
C++的标准模版库的应用.
二.图算法:
差分约束系统的建立和求解.
最小费用最大流
双连通分量
强连通分支及其缩点.
图的割边和割点
最小割模型、网络流规约
三.数据结构.
线段树.
静态二叉检索树.
树状树组
RMQ.
并查集的高级应用.
KMP算法.
四.搜索
最优化剪枝和可行性剪枝
搜索的技巧和优化
记忆化搜索
五.动态规划
较为复杂的动态规划(如动态规划解特别的旅行商TSP问题等)
记录状态的动态规划.
树型动态规划(
六.数学
组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理4.递推关系和母函数.
数学.1.高斯消元法2.概率问题.3.GCD、扩展的欧几里德(中国剩余定理)
随机化算法
七.计算几何学.
坐标离散化.
扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用)
几何工具的综合应用.
高级:
一.基本算法要求:
代码快速写成,精简但不失风格
保证正确性和高效性.
二.图算法:
度限制最小生成树和第K最短路.
最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
小生成树.
无向图、有向图的最小环
三.数据结构.
trie图的建立和应用.
LCA和RMQ问题(LCA(最近公共祖先问题)有离线算法(并查集+dfs)和在线算法
双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的).
左偏树(可合并堆).
四.搜索
广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法.
深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法.
五.动态规划
需要用数据结构优化的动态规划.
四边形不等式理论.
较难的状态DP
六.数学
组合数学.1.MoBius反演2.偏序关系理论.
博奕论.1.极大极小过程2.Nim问题.
七.计算几何学.
半平面求交
可视图的建立
点集最小圆覆盖.