Beverly 2008-8-4 22:59
北京大学ACM题目算法分析推荐 acm解决方法
来源：thdxs.uu1001.com
一.动态规划
参考资料：
刘汝佳《算法艺术与信息学竞赛》
《算法导论》
推荐题目：
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1141[/url]
简单
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2288[/url]
中等，经典TSP问题
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2411[/url]
中等，状态压缩DP
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1112[/url]
中等
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1848[/url]
中等，树形DP。
可参考《算法艺术与信息学竞赛》动态规划一节的树状模型
[url]http://acm.zju.edu.cn/show_problem.php?pid=1234[/url]
中等，《算法艺术与信息学竞赛》中的习题
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1947[/url]
中等，《算法艺术与信息学竞赛》中的习题
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1946[/url]
中等，《算法艺术与信息学竞赛》中的习题
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1737[/url]
中等，递推
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1821[/url]
中等，需要减少冗余计算
[url]http://acm.zju.edu.cn/show_problem.php?pid=2561[/url]
中等，四边形不等式的简单应用
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1038[/url]
较难，状态压缩DP，《算法艺术与信息学竞赛》中有解答
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1390[/url]
较难，《算法艺术与信息学竞赛》中有解答
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=3017[/url]
较难，需要配合数据结构优化（我的题目^_^）
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1682[/url]
较难，写起来比较麻烦
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2047[/url]
较难
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2152[/url]
难，树形DP
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=3028[/url]
难，状态压缩DP，题目很有意思
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=3124[/url]
难
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2915[/url]
非常难
二.搜索
参考资料：
刘汝佳《算法艺术与信息学竞赛》
推荐题目：
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1011[/url]
简单，深搜入门题
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1324[/url]
中等，广搜
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2044[/url]
中等，广搜
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2286[/url]
较难，广搜
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1945[/url]
难，IDA*，迭代加深搜索，需要较好的启发函数
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2449[/url]
难，可重复K最短路，A*。
可参考解题报告:
[url]http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144[/url]
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1190[/url]
难，深搜剪枝，《算法艺术与信息学竞赛》中有解答
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1084[/url]
难，《算法艺术与信息学竞赛》习题
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2989[/url]
难，深搜
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1167[/url]
较难，《算法艺术与信息学竞赛》中有解答
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1069[/url]
很难
三. 常用数据结构
参考资料：
刘汝佳《算法艺术与信息学竞赛》
《算法导论》
线段树资料：
[url]http://home.ustc.edu.cn/~zhuhcheng/ACM/segment_tree.pdf[/url]
树状数组资料
[url]http://home.ustc.edu.cn/~zhuhcheng/ACM/tree.ppt[/url]
关于线段树和树状数组更多相关内容可在网上搜到
后缀数组资料
[url]http://home.ustc.edu.cn/~zhuhcheng/ACM/suffix_array.pdf[/url]
[url]http://home.ustc.edu.cn/~zhuhcheng/ACM/linear_suffix.pdf[/url]
推荐题目
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2482[/url]
较难，线段树应用，《算法艺术与信息学竞赛》中有解答
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1151[/url]
简单，线段树应用矩形面积并，《算法艺术与信息学竞赛》中有解答
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=3225[/url]
较难，线段树应用，可参考解题报告
[url]http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1233[/url]
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2155[/url]
难，二维树状数组。
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2777[/url]
中等，线段树应用。
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2274[/url]
难，堆的应用，《算法艺术与信息学竞赛》中有解答
[url]http://acm.zju.edu.cn/show_problem.php?pid=2334[/url]
中等，左偏树，二项式堆或其他可合并堆的应用。
左偏树参考[url]http://www.nist.gov/dads/HTML/leftisttree.html[/url]
二项式堆参见《算法导论》相关章节
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1182[/url]
中等，并查集
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1816[/url]
中等，字典树
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2778[/url]
较难，多串匹配树
参考：[url]http://home.ustc.edu.cn/~zhuhcheng/ACM/zzy2004.pdf[/url]
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1743[/url]
难，后缀数组
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2774[/url]
较难，最长公共子串，经典问题，后缀数组
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2758[/url]
很难，后缀数组
可参考解题报告
[url]http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1178[/url]
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2448[/url]
很难，数据结构综合运用
四.图论基础
参考资料：
刘汝佳《算法艺术与信息学竞赛》
《算法导论》
《网络算法与复杂性理论》谢政
推荐题目:
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2337[/url]
简单，欧拉路
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=3177[/url]
中等，无向图割边
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2942[/url]
较难，无向图双连通分支
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1639[/url]
中等，最小度限制生成树，《算法艺术与信息学竞赛》中有解答
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2728[/url]
中等，最小比率生成树，《算法艺术与信息学竞赛》中有解答
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=3013[/url]
简单，最短路问题
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1275[/url]
中等，差分约束系统，Bellman-Ford求解，《算法艺术与信息学竞赛》中有解答
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1252[/url]
简单，Bellman-Ford
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1459[/url]
中等，网络流
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2391[/url]
较难，网络流
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1325[/url]
中等，二部图最大匹配
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2226[/url]
较难，二部图最大匹配
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2195[/url]
中等，二部图最大权匹配
KM算法参考《网络算法与复杂性理论》
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2516[/url]
较难，二部图最大权匹配
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1986[/url]
中等，LCA（最近公共祖先）问题
参考Tarjan's LCA algorithm 《算法导论》第21章习题
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2723[/url]
较难，2-SAT问题
参考：[url]http://home.ustc.edu.cn/~zhuhcheng/ACM/2-SAT.PPT[/url]
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2749[/url]
较难，2-SAT问题
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=3164[/url]
较难，最小树形图
参考《网络算法与复杂性理论》中朱-刘算法