ACM竞赛须掌握的知识 以及 2个版本的POJ推荐 @ NKOJ discuss
图论 二分图匹配问题 网络流问题 弦图的性质和判定
解决组合数学问题时常用的思想
计算几何的核心:叉积 / 面积 基本形 凸多边形 / 凸包 Graham扫描法 完美凸包算法 相关判定 经典问题
最大公约数 线性方程组 矩阵 分数 数论计算 素数问题
组织结构 统计结构 关系结构 STL中的数据结构
动态规划和记忆化搜索在思考方式上的区别 最长子序列系列问题 一类NP问题的动态规划解法 树型动态规划 背包问题 动态规划的优化
常用思想 二分 串 KMP 排序
/**************以下为POJ推荐*****************************/ 题目均为POJ上的 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman (poj1860,poj3259,poj1062 (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258 (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串 (poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash (poj3349,poj3274,POJ2151 (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索 (poj2488,poj3083,poj3009 (2)广度优先搜索(poj3278,poj1426 (3)简单搜索技巧和剪枝(poj2531,poj1416 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书 page149): 1.E[j]=opt{D[i]+w(i,j)} (poj3267,poj1836,poj1260 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C 六.数学 (1)组合数学: 1.加法原理和乘法原理. 2.排列组合. 3.递推关系. (POJ3252,poj1850,poj1019 (2)数论. 1.素数与整除问题 2.进制位. 3.同余模运算. (poj2635, poj3292,poj1845,poj2115) (3)计算方法. 高级: 一.基本算法要求: (1)代码快速写成,精简但不失风格 (poj2525,poj1684,poj1421 (2)保证正确性和高效性. poj3434 二.图算法: (1)度限制最小生成树和第K最短路. (poj1639) (2)最短路,最小生成树,二分图,最大流问题的相关理论 (poj3155, poj2112,poj1966,poj3281 (3)最优比率生成树. (poj2728) (4)最小树形图(poj3164) (5)次小生成树. (6)无向图、有向图的最小环 三.数据结构. (1)trie图的建立和应用. (poj2778) (2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法 (RMQ+dfs)).(poj1330) (3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中 目的). (poj2823) (4)左偏树(可合并堆). (5)后缀树(非常有用的数据结构,也是赛区考题的热点). (poj3415,poj3294) 四.搜索 (1)较麻烦的搜索题目训练(poj1069,poj3322 (2)广搜的状态优化:利用M进制数存储状态、转化为串用hash (3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少 五.动态规划 (1)需要用数据结构优化的动态规划. (poj2754,poj3378,poj3017) (2)四边形不等式理论. (3)较难的状态DP(poj3133) 六.数学 (1)组合数学. 1.MoBius反演(poj2888,poj2154) 2.偏序关系理论. (2)博奕论. 1.极大极小过程(poj3317,poj1085) 2.Nim问题. 七.计算几何学. (1)半平面求交(poj3384,poj2540) (2)可视图的建立(poj2966) (3)点集最小圆覆盖. (4)对踵点(poj2079) 八.综合题. (poj3109,poj1478,poj1462 ================================= 下面是另一版本POJ推荐,基本都比较难,很多题目与黑书配套 ================================= 推荐一些题目,希望对参与ICPC竞赛的同学有所帮助。 POJ上一些题目在 http://162.105.81.202/course/problemSolving/ 可以找到解题报告。 《算法艺术与信息学竞赛》的习题提示在网上可搜到 一.动态规划 参考资料: 刘汝佳《算法艺术与信息学竞赛》 《算法导论》 推荐题目: http://acm.pku.edu.cn/JudgeOnline/problem?id=1141 简单 http://acm.pku.edu.cn/JudgeOnline/problem?id=2288 中等,经典TSP问题 http://acm.pku.edu.cn/JudgeOnline/problem?id=2411 中等,状态压缩DP http://acm.pku.edu.cn/JudgeOnline/problem?id=1112 中等 http://acm.pku.edu.cn/JudgeOnline/problem?id=1848 中等,树形DP。 可参考《算法艺术与信息学竞赛》动态规划一节的树状模型 http://acm./show_problem.php?pid=1234 中等,《算法艺术与信息学竞赛》中的习题 http://acm.pku.edu.cn/JudgeOnline/problem?id=1947 中等,《算法艺术与信息学竞赛》中的习题 http://acm.pku.edu.cn/JudgeOnline/problem?id=1946 中等,《算法艺术与信息学竞赛》中的习题 http://acm.pku.edu.cn/JudgeOnline/problem?id=1737 中等,递推 http://acm.pku.edu.cn/JudgeOnline/problem?id=1821 中等,需要减少冗余计算 http://acm./show_problem.php?pid=2561 中等,四边形不等式的简单应用 http://acm.pku.edu.cn/JudgeOnline/problem?id=1038 较难,状态压缩DP,《算法艺术与信息学竞赛》中有解答 http://acm.pku.edu.cn/JudgeOnline/problem?id=1390 较难,《算法艺术与信息学竞赛》中有解答 http://acm.pku.edu.cn/JudgeOnline/problem?id=3017 较难,需要配合数据结构优化(我的题目^_^) http://acm.pku.edu.cn/JudgeOnline/problem?id=1682 较难,写起来比较麻烦 http://acm.pku.edu.cn/JudgeOnline/problem?id=2047 较难 http://acm.pku.edu.cn/JudgeOnline/problem?id=2152 难,树形DP http://acm.pku.edu.cn/JudgeOnline/problem?id=3028 难,状态压缩DP,题目很有意思 http://acm.pku.edu.cn/JudgeOnline/problem?id=3124 难 http://acm.pku.edu.cn/JudgeOnline/problem?id=2915 非常难 二.搜索 参考资料: 刘汝佳《算法艺术与信息学竞赛》 推荐题目: http://acm.pku.edu.cn/JudgeOnline/problem?id=1011 简单,深搜入门题 http://acm.pku.edu.cn/JudgeOnline/problem?id=1324 中等,广搜 http://acm.pku.edu.cn/JudgeOnline/problem?id=2044 中等,广搜 http://acm.pku.edu.cn/JudgeOnline/problem?id=2286 较难,广搜 http://acm.pku.edu.cn/JudgeOnline/problem?id=1945 难,IDA*,迭代加深搜索,需要较好的启发函数 http://acm.pku.edu.cn/JudgeOnline/problem?id=2449 难,可重复K最短路,A*。 可参考解题报告: http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144 http://acm.pku.edu.cn/JudgeOnline/problem?id=1190 难,深搜剪枝,《算法艺术与信息学竞赛》中有解答 http://acm.pku.edu.cn/JudgeOnline/problem?id=1084 难,《算法艺术与信息学竞赛》习题 http://acm.pku.edu.cn/JudgeOnline/problem?id=2989 难,深搜 http://acm.pku.edu.cn/JudgeOnline/problem?id=1167 较难,《算法艺术与信息学竞赛》中有解答 http://acm.pku.edu.cn/JudgeOnline/problem?id=1069 很难 三. 常用数据结构 参考资料: 刘汝佳《算法艺术与信息学竞赛》 《算法导论》 线段树资料: http://home.ustc.edu.cn/~zhuhcheng/ACM/segment_tree.pdf 树状数组资料 http://home.ustc.edu.cn/~zhuhcheng/ACM/tree.ppt 关于线段树和树状数组更多相关内容可在网上搜到 后缀数组资料 http://home.ustc.edu.cn/~zhuhcheng/ACM/suffix_array.pdf http://home.ustc.edu.cn/~zhuhcheng/ACM/linear_suffix.pdf 推荐题目 http://acm.pku.edu.cn/JudgeOnline/problem?id=2482 较难,线段树应用,《算法艺术与信息学竞赛》中有解答 http://acm.pku.edu.cn/JudgeOnline/problem?id=1151 简单,线段树应用矩形面积并,《算法艺术与信息学竞赛》中有解答 http://acm.pku.edu.cn/JudgeOnline/problem?id=3225 较难,线段树应用,可参考解题报告 http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1233 http://acm.pku.edu.cn/JudgeOnline/problem?id=2155 难,二维树状数组。 http://acm.pku.edu.cn/JudgeOnline/problem?id=2777 中等,线段树应用。 http://acm.pku.edu.cn/JudgeOnline/problem?id=2274 难,堆的应用,《算法艺术与信息学竞赛》中有解答 http://acm./show_problem.php?pid=2334 中等,左偏树,二项式堆或其他可合并堆的应用。 左偏树参考http://www./dads/HTML/leftisttree.html 二项式堆参见《算法导论》相关章节 http://acm.pku.edu.cn/JudgeOnline/problem?id=1182 中等,并查集 http://acm.pku.edu.cn/JudgeOnline/problem?id=1816 中等,字典树 http://acm.pku.edu.cn/JudgeOnline/problem?id=2778 较难,多串匹配树 参考:http://home.ustc.edu.cn/~zhuhcheng/ACM/zzy2004.pdf http://acm.pku.edu.cn/JudgeOnline/problem?id=1743 难,后缀数组 http://acm.pku.edu.cn/JudgeOnline/problem?id=2774 较难,最长公共子串,经典问题,后缀数组 http://acm.pku.edu.cn/JudgeOnline/problem?id=2758 很难,后缀数组 可参考解题报告 http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1178 http://acm.pku.edu.cn/JudgeOnline/problem?id=2448 很难,数据结构综合运用 四.图论基础 参考资料: 刘汝佳《算法艺术与信息学竞赛》 《算法导论》 《网络算法与复杂性理论》谢政 推荐题目: http://acm.pku.edu.cn/JudgeOnline/problem?id=2337 简单,欧拉路 http://acm.pku.edu.cn/JudgeOnline/problem?id=3177 中等,无向图割边 http://acm.pku.edu.cn/JudgeOnline/problem?id=2942 较难,无向图双连通分支 http://acm.pku.edu.cn/JudgeOnline/problem?id=1639 中等,最小度限制生成树,《算法艺术与信息学竞赛》中有解答 http://acm.pku.edu.cn/JudgeOnline/problem?id=2728 中等,最小比率生成树,《算法艺术与信息学竞赛》中有解答 http://acm.pku.edu.cn/JudgeOnline/problem?id=3013 简单,最短路问题 http://acm.pku.edu.cn/JudgeOnline/problem?id=1275 中等,差分约束系统,Bellman-Ford求解,《算法艺术与信息学竞赛》中有解答 http://acm.pku.edu.cn/JudgeOnline/problem?id=1252 简单,Bellman-Ford http://acm.pku.edu.cn/JudgeOnline/problem?id=1459 中等,网络流 http://acm.pku.edu.cn/JudgeOnline/problem?id=2391 较难,网络流 http://acm.pku.edu.cn/JudgeOnline/problem?id=1325 中等,二部图最大匹配 http://acm.pku.edu.cn/JudgeOnline/problem?id=2226 较难,二部图最大匹配 http://acm.pku.edu.cn/JudgeOnline/problem?id=2195 中等,二部图最大权匹配 KM算法参考《网络算法与复杂性理论》 http://acm.pku.edu.cn/JudgeOnline/problem?id=2516 较难,二部图最大权匹配 http://acm.pku.edu.cn/JudgeOnline/problem?id=1986 中等,LCA(最近公共祖先)问题 参考Tarjan's LCA algorithm 《算法导论》第21章习题 http://acm.pku.edu.cn/JudgeOnline/problem?id=2723 较难,2-SAT问题 参考:http://home.ustc.edu.cn/~zhuhcheng/ACM/2-SAT.PPT http://acm.pku.edu.cn/JudgeOnline/problem?id=2749 较难,2-SAT问题 http://acm.pku.edu.cn/JudgeOnline/problem?id=3164 较难,最小树形图 参考《网络算法与复杂性理论》中朱-刘算法 五.数论及组合计数基础 http://acm.pku.edu.cn/JudgeOnline/problem?id=1811 简单,素数判定,大数分解 参考算法导论相关章节 http://acm.pku.edu.cn/JudgeOnline/problem?id=2888 较难,Burnside引理 http://acm.pku.edu.cn/JudgeOnline/problem?id=2891 中等,解模方程组 http://acm.pku.edu.cn/JudgeOnline/problem?id=2154 中等,经典问题,波利亚定理 http://cs./soj/problem.action?id=2703 难,极好的题目,Burnside引理+模线性方程组 http://acm.pku.edu.cn/JudgeOnline/problem?id=2764 较难,需要数学方法,该方法在《具体数学》第七章有讲 http://acm.pku.edu.cn/JudgeOnline/problem?id=1977 简单,矩阵快速乘法 /* |
|