SDUTACM训练计划.doc

SDUT集训计划假设已有C/C+/JAVA中任何一门程序设计语言基础，熟练掌握基本语法。Step1: 入门hduwater，刷完Step2: 数据结构课本算法代码熟敲。数据结构需要掌握的内容（数据结构C语言版 严蔚敏|吴伟民）：第1章 绪论算法和算法分析（时间复杂度分析和空间复杂度分析）第2章 线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现（注意掌握循环链表和双向链表）第3章 栈和队列3.1栈的定义、表示和实现3.2栈的应用举例3.4队列的定义、表示和实现（注意掌握循环队列，以及循环队列的数组实现）第4章 串掌握串在C语言中的表示方法、常用字符串函数掌握简单的模式匹配算法第6章 树和二叉树6.1树的定义和基本术语6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质（重点掌握）6.2.3二叉树的存储结构6.3 掌握二叉树的遍历（先序、中序、后序）6.4树和森林树的存储结构森林与二叉树的转换（左孩子右兄弟法）树和森林的遍历6.6赫夫曼树及其应用6.6.1最优二叉树（赫夫曼树）6.6.2赫夫曼编码第7章 图7.1图的定义和术语7.2图的存储结构7.2.1数组表示法7.2.2邻接表7.3图的遍历7.3.1深度优先搜索7.3.2广度优先搜索7.4图的连通性问题7.4.1无向图的连通分量和生成树7.4.3最小生成树算法(prim & kruskal)7.5有向无环图及其应用7.5.1拓扑排序7.6最短路径7.6.1单源最短路径问题(dijkstra算法)7.6.2每一对顶点之间的最短路径（floyd算法）第9章 查找9.1 掌握有序表的二分查找算法9.3掌握哈希表的思想及简单的hash算法（如取模法hash）第10章 内部排序10.1概述10.2插入排序（掌握直接插入排序）10.3快速排序（重点掌握）10.4选择排序10.4.1简单选择排序10.4.2树形选择排序10.4.3堆排序10.5归并排序（重点掌握）10.7各种排序方法的比较集训第一天POJ纯水题 = =：Like the following2017 1218 2000 1046 1218 1003 1004 1005 1008 1013(枚举) 12071552 21052388 13162499 3006（a）（筛法求素数）正式集训计划：第一阶段 初级：第1周-第4周项目时间必做题目基本算法枚举第1周poj1753,poj2965贪心poj1328,poj2109(a),poj2586（a）分治法poj2524递推poj2506构造法poj3295模拟法poj1068,poj2632,poj1573,poj2993,poj2996图算法图的深度优先遍历和广度优先遍历第1周poj3278, poj2049, poj3083最短路径算法poj1860,poj3259,poj1062,poj2253,poj1125,poj2240最小生成树算法poj1789,poj2485,poj1258,poj3026拓扑排序poj1094, poj3267，poj3687二分图的最大匹配poj3041,poj3020最大流的增广路算法poj1459,poj3436数据结构串第2周poj1035,poj3080,poj1936排序poj2388,poj2299简单并查集的应用poj1611哈希表和二分查找等高效查找法poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503哈夫曼树poj3253堆,优先队列poj2442, poj1442trie树poj2513, poj2418简单搜索深度优先搜索第2周poj2488,poj3083,poj3009,poj1321,poj2251广度优先搜索poj3278,poj1426,poj3126,poj3087.poj3414简单搜索技巧和剪枝poj2531,poj1416,poj2676,poj1129动态规划背包问题第3周poj1837,poj1276型如下表的简单DPpoj3267,poj1836,poj1260,poj2533,poj3176,poj1080,poj1159数学组合数学第3周POJ3252,poj1850,poj1019,poj1942数论poj2635, poj3292,poj1845,poj2115计算方法poj3273,poj3258,poj1905,poj3122计算几何学几何公式第4周poj1265(pick定理)叉积和点积的运用poj2031,poj1039多边型的简单算法和相关判定poj1408,poj1584凸包poj2187,poj1113第二阶段 中级：第4周-第9周项目时间必做题目基本算法C+的标准模版库的应用第4周poj3096,poj3007较为复杂的模拟题的训练poj3393,poj1472,poj3371,poj1027,poj2706图算法差分约束系统的建立和求解第5周poj1201,poj2983, poj3159poj1275, poj1364最小费用最大流poj2516, poj2195, poj3422双连通分量poj2942，poj3694强连通分支及其缩点poj2186, poj3592, poj3114图的割边和割点poj3352最小割模型poj3308, poj3155（偏难）KM算法(最大权/最小权）poj2195, poj2400, poj3686数据结构线段树第6周poj2528,poj2828,poj2777,poj2886,poj2750静态二叉检索树,平衡树treap,splaypoj2482,poj2352, poj2892poj3468,树状树组poj1195,poj3321RMQpoj3264,poj3368并查集的高级应用poj1703,2492KMP算法poj1961,poj2406搜索最优化剪枝和可行性剪枝第7周poj1699搜索的技巧和优化poj3411,poj1724记忆化搜索poj3373,poj1691动态规划较为复杂的动态规划第7周poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034记录状态的动态规划poj3254,poj2411,poj1185树型动态规划poj2057,poj1947,poj2486,poj3140数学组合数学,polya定理,置换群第8周poj1286,poj2409,poj3270,poj1026高斯消元法poj2947,poj1487, poj2065,poj1166,poj1222概率问题poj3071,poj3440GCD、扩展的欧几里德poj1061, poj2891,poj3101poj2115计算方法(矩阵、三分等)poj2976,poj3150,poj3422,poj3070, poj3301随机化算法poj3318,poj2454杂题poj1870,poj3296,poj3286,poj1095计算几何学坐标离散化第9周poj1151扫描线算法poj1765,poj1177,poj1151,poj3277,poj2280,poj3004多边形的核poj3130,poj3335几何工具的综合应用poj1819,poj1066,poj2043,poj3227,poj2165,poj3429第三阶段 高级：第10周-第18周项目时间必做题目基本算法代码快速写成第10周poj2525,poj1684,poj1421,poj1048,poj2050,poj3306保证正确性和高效性poj3434图算法度限制最小生成树和第K最短路,分数规划第10-11周poj1639, poj3621, poj2976poj3255，poj2513，poj2449最短路,最小生成树,二分图,最大流问题的相关理论poj3155,poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446最优比率生成树poj2728（0/1分数规划应用）最小树形图poj3164(朱-刘算法)次小生成树poj1679(存在O(n2)的DP解法)2-SAT问题poj3207, poj3678, poj3683poj3648, poj2723, poj2749无向图、有向图的最小环poj1734(floyd扩展)数据结构trie图的建立和应用,DFA第12周hdu2222 poj2778, poj3691LCA和RMQ问题poj1330双端队列和它的应用poj2823左偏树poj3666，poj3016后缀树,后缀数组poj3415,poj3294, poj2774poj2758搜索较麻烦的搜索题目训练第13周poj1069,poj3322,poj1475,poj1924,poj2049,poj3426广搜的状态优化poj1768,poj1184,poj1872,poj1324,poj2046,poj1482深搜的优化poj3131,poj2870,poj2286动态规划需要用数据结构优化的动态规划第14-15周poj2754,poj3378,poj3017四边形不等式理论、斜率优化poj1160，poj1180，poj3709较难的状态DP、插头DPpoj3133,poj1739,p