（Step2-500题）POJ训练计划+SGU|问题探讨 - 山东理工ACM技术论坛 - Powered by phpwind

经过Step1-500题训练，接下来可以开始Step2-500题，包括POJ训练计划的298题和SGU前两章200题。需要1-1年半时间继续提高解决问题和编码实现能力，加油ACMer！任重道远  

Step1-500题

UVaOJ+算法竞赛入门经典+挑战编程+USACO 请见：http://acm.sdut.edu.cn/bbs/read.php?tid=5321 

一、POJ训练计划 Moon修订  298道题  

集训第一天 POJ纯水题 = =： 17道题
2017 1218 2000 1046 1218 1003 1004 1005 1008 1013(枚举)
1207 1552 2105 2388 1316 2499 3006（筛法求素数）

正式集训计划：

第一阶段 初级：第1周-第4周  92道题
项目		时间	必做题目
基本算法	枚举	第1周	poj1753,poj2965
	贪心		poj1328,poj2109,poj2586
	分治法		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, poj1442
	trie树		poj2513, poj2418
简单搜索	深度优先搜索	第2周	poj2488,poj3083,poj3009,poj1321,poj2251
	广度优先搜索		poj3278,poj1426,poj3126,poj3087.poj3414
	简单搜索技巧和剪枝		poj2531,poj1416,poj2676,poj1129
动态规划	背包问题	第3周	poj1837,poj1276
	型如下表的简单DP		poj3267,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周  104道题
项目		时间	必做题目
基本算法	C++的标准模版库的应用	第4周	poj3096,poj3007
	较为复杂的模拟题的训练		poj3393,poj1472,poj3371,poj1027,poj2706
图算法	差分约束系统的建立和求解	第5周	poj1201,poj2983, poj3159 poj1275, poj1364
	最小费用最大流		poj2516, poj2195, poj3422
	双连通分量		poj2942，poj3694
	强连通分支及其缩点		poj2186, poj3592, poj3114
	图的割边和割点		poj3352
	最小割模型		poj3308, poj3155（偏难）
	KM算法(最大权/最小权）		poj2195, poj2400, poj3686
数据结构	线段树	第6周	poj2528,poj2828,poj2777,poj2886,poj2750
	静态二叉检索树,平衡树treap,splay		poj2482,poj2352, poj2892 poj3468,
	树状树组		poj1195,poj3321
	RMQ		poj3264,poj3368
	并查集的高级应用		poj1703,2492
	KMP算法		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,poj3440
	GCD、扩展的欧几里德		poj1061, poj2891,poj3101 poj2115
	计算方法(矩阵、三分等)		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周  85道题
项目		时间	必做题目
基本算法	代码快速写成	第10周	poj2525,poj1684,poj1421,poj1048,poj2050,poj3306
	保证正确性和高效性		poj3434
图算法	度限制最小生成树和第K最短路,分数规划	第10-11周	poj1639, poj3621, poj2976 poj3255，poj2513，poj2449
	最短路,最小生成树,二分图,最大流问题的相关理论		poj3155,poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
	最优比率生成树		poj2728（0/1分数规划应用）
	最小树形图		poj3164(朱-刘算法)
	次小生成树		poj1679(存在O(n^2)的DP解法)
	2-SAT问题		poj3207, poj3678, poj3683 poj3648, poj2723, poj2749
	无向图、有向图的最小环		poj1734(floyd扩展)
数据结构	trie图的建立和应用,DFA	第12周	hdu2222 poj2778, poj3691
	LCA和RMQ问题		poj1330
	双端队列和它的应用		poj2823
	左偏树		poj3666，poj3016
	后缀树,后缀数组		poj3415,poj3294, poj2774 poj2758
搜索	较麻烦的搜索题目训练	第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、插头DP		poj3133,poj1739,poj2411、poj1763
数学	组合数学	第15周	poj2888,poj2154
	博奕论		poj3317,poj1085
计算几何学	半平面求交	第16周	poj3384,poj2540
	可视图的建立		poj2966
	点集最小圆覆盖		zju1450
	对踵点		poj2079
综合题		第16-18周	poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263

 
二、SGU前两章 200道题　　
SGU是俄罗斯萨拉托夫州立大学(大概是这个名字Saratov State University )的OJ,很老牌了。题目数量很少，但题题精炼，每做一道题都会让你的编程水平上升。在有一定编程水平之后可以试着做做，要争取做出每一道题。如果SGU能全部AC的话...那这个人不是抄袭就是神牛……（摘自http://baike.baidu.com/view/1185778.htm） 

Saratov State University
Volume(100-199)     http://acm.sgu.ru/problemset.php?contest=0&volume=1
Volume(200-299)     http://acm.sgu.ru/problemset.php?contest=0&volume=2

Read full article from （Step2-500题）POJ训练计划+SGU|问题探讨 - 山东理工ACM技术论坛 - Powered by phpwind