TODO-List

1. BigNum.cpp
2. hdu4533-晒被子.cpp 使用线段树
3. hdu4517-游戏的烦恼.cpp 打表
4. hdu4515-世界上最遥远的距离.cpp 这个重写

基本算法

• 枚举
  • 当数据量较小时，可以考虑枚举，依次列举没中可能情况
  • 典型的如排列组合问题，
  • hdu4086-三国杀的问题是个典型应用(使用C++STL中的next_permutation)
• 贪心
  • 贪心算法实际上就是不用回溯的动态规划问题？
  • hdu3916神码bug啊，无语了
• 递归&分治
  • 将数据一分为二，分别求解，之后在合并
  • 一分为二一般使用递归实现，关键是如何合并
  • 简单的归并如求数组最大值，直接比较一下就好了，或者像归并排序稍微复杂些，当然也有更为复杂的需要‘剪枝’，否则分支算法就没不会降低时间复杂度了，这个如最小点距问题(hdu1007)
• 递推
  • 这类题目需要总结出递推公式，f(n)=g(f(n-1),f(n-2)...)
  • hdu2041超级电梯的题目很典型，有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？
  • 思路，回退一步，只能走到M-1和M-2级，并且二者独立，所以可以总结f(n)=f(n-1)+f(n-2) f(1)=1, f(n2)=2
• 构造,模拟

数据结构

• 二叉树(遍历，重建)，二叉搜索树，红黑树，
• 串
  • KMP
  • 字典数
  • AC自动机
  • 后缀数组
• 排序
  • 快排,OK,注意一点mid=(l+h)/2里买你的l和h是‘不对等’的，因为除2的话mid最终等于l却可能无法等于h
  • 归并,OK
  • 堆排,OK
• 哈希表
• 并查集
• 哈夫曼树

搜索

• DFS
• BFS
• 双向
• 启发式
• 记忆

动态规划

• 背包
• 基本DP

最短路（Floyd, Dijstra）

###最小生成树（prime，kruscal，用并查集） ###大数运算 ###二分查找（代码5行以内） ###叉乘，线段相交，凸包 ###BFS,DFS,熟练hash表 ###辗转相除（两行内），多角形面积公式 ###任意进制间的转换

二分图，最小路径覆盖

###网络流，最小流 ###线段树 ###并查集 ###常见动态规划LCS、最长递增子串、三角剖分、记忆化dp ###博弈树，二进制法 ###最大团，最大独立集 ###判断点在多边形内 ###差分约束系统 ###双向广度搜索、A*算法，最小耗散优先