ACM学习资料整理

声明：参考泥瓦匠BYSocket、POJ题目分类推荐 （很好很有层次感）整理所得

1 推荐题库

? http://ace.delos.com/usaco/

? http://livearchive.onlinejudge.org/

上面有全部的赛区真题，绝大部分都可以提交，不适合当题库刷，不过在这里找题非常方便。

? http://poj.org/

不解释了，中国最知名的oj，题量非常之大，历史也很悠久，推荐刷一些代表性的题目。

? http://acm.timus.ru/
Ural 大学的oj，国外oj 中非常好的一个，题目非常锻炼基本功，管理员会不时添加一些新数据rejudge，推荐找些通过人数适中的题目割一割。

? http://acm.sgu.ru/

SGU 大学的oj，题目比较经典（比较老）。

? http://www.spoj.pl
比较奇葩的一个oj，有一些与众不同的提交模式，也有很多著名的系列题目，qtree 等，题目质量很好，但问题是国内的题解较少，新手如果只是想去割水题还是不要去了。

? http://acm.hdu.edu.cn
杭电大学的oj，亮点是上面独有的中国多校联合训练的题目，而且有一版（第11版，以20 开头的那版）水题大全，新手提高很不错。

? http://acm.zju.edu.cn

每个月定时有月赛，浙大出题非常靠谱，推荐每个月月赛可以做一做。

? http://acm.hust.edu.cn
华中科技大学的oj，也就是各大oj 著名的virtual judge（三国五虎上将）的始作俑者，亮点就是那个模拟比赛的功能异常好用，平时大家可以自己配题做做模拟比赛，还有大量的专题训练。

? http://www.codeforces.com
著名线上比赛网站，几乎每周都有一场线上比赛，有各国牛人参加，强烈推荐按时参加提高实力（要克服时差问题）。

? http://www.topcoder.com/tc
更著名的一个线上比赛网站，历史相当悠久，而且有丰富的奖金，强烈推荐去做algorithm 比赛的single round match，非常提高智商。

2 ACM算法分类（来源于知乎）

3 ACM算法总结及相关练习（POJ题目分类推荐）

3.1 C++ STL

? STL 容器: set, map, vector, priority_queue, queue, stack, deque, bitset
? STL 算法: sort, unique, nth_element, reverse, rotate, next_permution, find, for_each, count, lower_bound,max, swap, random_shuffle

3.2 基本算法

? 枚举: poj1753, poj2965, zoj1716, zoj3356, ural1010
? 贪心: poj1328, poj2109, poj2586, ural1303, sgu195, sgu171
? 递归与分治: ural1181, poj1579, poj1845, poj3714
? 构造: poj3922, poj1092, sgu121
? 模拟: poj3125, poj1068, poj2993, ural1007
? 排序: ural1082, poj2092, poj1694
? KMP 算法: poj2406
? 扩展KMP: poj3376, poj1699
? 二分法: poj1905, poj2002
? 三分法: hdu3400, hdu2298
? 矩阵乘法: zoj2105, zoj3289
? 离散化: ural1019, sgu177
? 快速傅立叶变换: poj2821

? 环状字符串最小表示: poj1509

3.3 图论

? 深度优先遍历: poj2488
? 宽度优先遍历: poj3620, poj2251
? 最短路: poj1847, poj1062
? 最小生成树: zoj1914
? 拓扑排序: zoj2193, zoj1060
? 二分图最大匹配: poj1469
? 二分图的最大权匹配: ural1076
? 稳定婚配问题: poj3487
? 最大流与最小割: poj1459
? 带下界的最大流: poj2396
? 最小费用最大流: poj2159
? 差分约束系统: poj1275
? 双连通分量: zoj2588
? 强连通分量: zoj2470, poj2186
? 割边及割点: poj3352, poj3177
? 度限制生成树: poj1638, hdu3070
? K 短路: poj2449, sgu145
? 最近公共祖先: poj1330
? 最优比率生成树: poj2728
? 次小生成树: poj1679
? 最小树形图: poj3164
? 欧拉回路与路径: poj1386, poj2337
? 哈密顿回路: sgu122
? 旅行商问题: poj2288
? 极大团搜索: poj2989
? 弦图的判定与应用: zoj1015

? 任意图的最大匹配: ural1099

3.4 数据结构

? 栈与队列: poj2559
? 并查集: poj1611, poj1182
? 哈希表: poj1840, poj1186
? 优先队列: poj1862, poj3253
? 可合并堆: zoj2334
? 字母树及AC 自动机: zoj3430, zoj3228
? 线段树: zoj3317, zoj1610
? 树状数组: poj2299, poj2352
? 倍增表(RMQ): poj3368, poj2452
? 平衡二叉树: poj2892, poj2418, poj3580
? 后缀数组: poj2774, poj3294
? KD 树: spoj2835, poj2528
? 树链剖分: poj3237, spoj2666, spoj2798
? 树的分治算法: poj2114, poj1987

? 动态树: hdu2475, hdu3601, hdu4010

3.5 搜索

? 简单技巧与剪枝: poj1033, poj3009
? 最优化与可行性剪枝: poj1011, poj1190
? 记忆化搜索: poj1191, poj1088
? 迭代加深: poj2286, poj2032
? A 搜索: hdu2467, poj1077
? Dancing Link: poj3074, hdu4069
? 折半搜索: zoj3631
? 双向广搜: poj1198, poj1915

3.6 动态规划

? 资源分配问题: poj3624, poj2063
? 区间划分问题: poj3280
? 状态压缩问题: poj1185
? 树形DP: poj1463, poj3345
? 数据结构优化DP: poj2374, poj2355
? 四边形不等式: poj1160
? 队列优化: zoj3399
? 插头表示的状态压缩DP: poj1739
? 最小表示法的状态压缩DP: spoj2159

? 数位DP: hdu3555, sgu258, sgu390

3.7 数学

? 排列组合: poj1850, poj3252
? Lucas 定理: poj3219
? 素数测试与筛法: poj2191, poj1811
? 大数分解的快速算法: poj1142
? 进位制: poj2798, poj1702
? 同余模运算: poj1006, poj2115
? 容斥原理: poj3904, poj1173
? 置换群与Burnside 引理: poj2888
? 递推关系与母函数: poj3734
? 高斯消元: poj1681, poj1222
? 概率与统计: poj2151, poj1021
? 扩展欧几里得算法: poj2891, poj1061
? 中国剩余定理: poj1006, zoj3538
? 离散对数与离散根: sgu261
? 拉格朗日插值: uva4209
? 迭代逼近: poj2868, poj3933
? 莫比乌斯反演: poj2154
? 博弈论与SG 函数: poj2960, poj2311
? 偏序论与格: poj1065, poj3636

3.8 计算几何

? 点积与叉积: zoj1010
? 线段相交: zoj1648
? 简单多边形的面积: poj1654
? 点到线段的最近最远距离: ural1348
? 凸包: poj1113
? 对锺点: poj2187
? 圆与点的切线: poj1375
? 圆与直线的交: poj1263
? 圆与圆的交: poj2564
? 圆与多边形的并与交: poj3675
? 点在多边形内: poj2398
? 半平面交: poj1474, poj2540
? 最小圆覆盖: zoj1450, spoj145
? 三维凸包: poj3528
? 三维点与直线的表示: poj3129

? 线性规划: poj1755

4 可参考资料

? 《算法艺术与信息学竞赛》（黑书）

? 《算法竞赛入门经典（第二版）》（紫书）

? 《算法竞赛入门经典 训练指南》（白书）

? 《挑战程序设计竞赛》

?  ACM-ICPC程序设计系列 （哈尔滨工业大学出版社）

? 《算法导论》

?  历年的NOI 国家集训队论文

?  数学相关书籍

ACM学习资料整理