经过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