写在前面
- 随着四月的到来, 离省选越来越近了.
- 从NOIP到现在, 学到了很多很多东西, 有的学的比较深入, 有的只是略知一二
- 从明天开始, 进行针对省选的算法复习计划. 省选前完成.
- 重点是对算法的理解和应用, 还会注重模板习惯的养成
计划内容
1. 数据结构
- 一直觉得我数据结构学的还可以, 不过列出来发现会的也没多少.
- 少就少吧, 省选够用就行...
- 线段树
- 树状数组
- 并查集
- 哈希表
- STL
- treap
- splay
- 树链剖分
- 主席树(可忽略)
- 字符串(KMP, 后缀数组)
2.
图论
- 掌握经典的算法, 并会应用是重点
- 经常和动态规划结合
- 最短路(Floyed, 堆优化dijkstra, SPFA)
- 最小生成树(Prim, Kruskal), 以及生成树相关
- 强连通分量(Tarjan)
- 拓扑排序
- 欧拉路径和哈密尔顿环
- 桥和关键路径
- 二分图
- 其他(2-SAT, Floyed判圈)
3. 网络流
- 算法是基础, 建模是关键
- 多看原来做过的题目, 总结建模方法
- 最大流, 最小割(Dinic)
- 费用流(SPFA)
- 上下界网络流
- 弄清时间复杂度...
4. 数学
- 东西很多, 基本上都在训练指南上有
- 我数学不好, 所以会几个基础算法然后考试暴力吧.
- 归纳法
- gcd
- 筛法求素数
- 普通欧拉函数, 筛法求欧拉函数
- 逆元(欧拉函数, 扩展欧几里得), 预处理逆元
- 容斥原理
- 解线性模方程
- 离散对数(BSGS)
- 中国剩余定理
- 组合数, 卢卡斯定理
- 莫比乌斯函数
- 矩阵乘法(循环矩阵)
5. 搜索
- dfs
- bfs
- A*
- IDA*
- 启发式dfs
- 双向dfs
- 双向bfs
- 记忆化搜索
6. 动态规划
- 最好是想出动态规划的方法来
- 能否用动态规划关键是看有无后效性和有无重叠子问题
- 但有时看上去有后效性的问题可以转化成没有后效性
- 什么优化的就看着来了
- 基本上不加优化部分分可能也能拿到少许
- 棋盘型动态规划
- 序列型动态规划
- 背包型动态规划
- 区间型动态规划
- 划分型动态规划
- 路径型动态规划
- 树型动态规划
- 状态压缩动态规划
- 基于连通性的动态规划
- 斜率优化, 单调性优化, 凸壳(都不会)
7. 分治
- 效率极高, 但一般想不到, 思路比较怪异
- 如果满足离线要求往往很BT
8. 贪心
- 发现从NOIP以来我还没有做过一道贪心的题目
- 但是思想很重要
9. 群论
10. 离散化
11. 计算几何
- 发现竟然忘了计算几何
- 注意不要去死记, 训练指南上的代码普适性好但还要因题而异, 有可能有更简单的方法
- 有时看不出是计算几何但是可以转化成计算几何的题目, 比如半平面交之类的
12. 暴力技巧(乱搞)
- 同样是暴力, 有的人20分有的人就能40分.
- 暴力也有技巧, 而且不一定学的算法多暴力写的就好, 往往思维活跃的人暴力写得好(Orz wxjlzbcd)
- 大胆猜测不失为一种好办法.
算法复习计划
原文：http://blog.csdn.net/qq_21110267/article/details/44731847
