acm推荐题目

一.动态规划

 

参考资料：

 

刘汝佳《算法艺术与信息学竞赛》《算法导论》

 

推荐题目：

 

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.zju.edu.cn/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.zju.edu.cn/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.zju.edu.cn/show_problem.php?pid=2334

 

中等，左偏树，二项式堆或其他可合并堆的应用。

 

左偏树参考 http://www.nist.gov/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.scu.edu.cn/soj/problem.action?id=2703

 

难，极好的题目，Burnside引理+模线性方程组

 

http://acm.pku.edu.cn/JudgeOnline/problem?id=2764

 

较难，需要数学方法，该方法在《具体数学》第七章有讲

 

http://acm.pku.edu.cn/JudgeOnline/problem?id=1977

 

简单，矩阵快速乘法

 

2009-01-04