2012年暑期集训内容大纲（暂定）

一、 新队员

1、字符串处理、STL

• 常用字符串处理函数介绍及举例说明（越全面越好）

• STL中的模板、算法介绍。

• 字典树处理

• 字符串匹配

2、计算几何

• 向量法基础

• 线段相交问题

• 求解多边形面积

• 微积分求解曲面面积

• 判断点在多边形内部

• 判断多边形凹凸

• 凸包问题

• 常用几何公式

3、数论、组合数学、计算方法

• 因子分解

• 欧几里得算法

• 扩展欧几里得算法

• 模运算和求解模线性方程

• 反复平方法求解a^b mod m的值

• 中国剩余定理

• 欧拉定理

• 费马定理

• 容斥原理

• 二分法求解单调函数问题

4、基本数据结构

• 线性表

• 栈

• 队列

• 优先队列

• 堆

• 哈希表

• 树和二叉树

• 图

• 并查集

5、贪心法

• 活动选择问题

• 霍夫曼编码

• 背包问题

• 最小生成树（并查集实现、prim算法、kruskal算法）

• Dijkstra单源最短路径

6、动态规划

• 动态规划基础知识

• 最长公共子序列

• 编辑距离

• 0-1背包

• 矩阵乘法

• Floyd算法求最短路径

• 最优二分查找树

7、图的基本算法

• 图的深度搜索算法

• 图的广度搜索算法

• 拓扑排序

• 强连通分支判别

• 欧拉回路

老队员

1、数据结构

• 线段树

• 树状数组

• 后缀树

• 后缀树组

• 红黑树

• 区间树

• RMQ

2、图论

• 网络流

• 最大二分匹配

• Bellman-Ford算法

• 差分约束与最短路径

3、动态规划

• 树形DP

• 三维DP

• 滚动数组

• 状态DP

4、搜索

• Rabin-Karp字符串匹配算法

• A*算法

• 记忆化搜索