正文

pku题目类型划分(7)2005-09-08 04:31:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/ddtme/4500.html

分享到:

主流算法:
1.搜索 //回溯
2.DP(动态规划) 
3.贪心 
4.图论 //Dijkstra、最小生成树、网络流
5.数论 //解模线性方程
6.计算几何 //凸壳、同等安置矩形的并的面积与周长
7.组合数学 //Polya定理
8.模拟 
9.数据结构 //并查集、堆
10.博弈论 
//表示举例

非主流算法:
1.送分题 
2.构造 
3.高精度 
4.几何 
5.排序 
6.日期/时间处理 (这类题目相当多的)
7.数学方法 
8.枚举 
9.递推 
10.递归 
11.分治 


说明:
  显然“送分题”不是一种算法。但是ACM竞赛中经常有一些很简单很简单的题目,具体涉及内容繁杂,难以归类,干脆就管他们叫送分题。
  几何不同于计算几何,计算几何或者叫S计算几何,以Shamos在1975年发表的一篇论文为诞生标志。其实两者有很大的不同。

部分题目分类统计:

网络流:
最大流:
1087 a plug for UNIX
1149 PIGS
1273 drainage ditches
1274 the perfect stall
1325 machine schedule
1459 power network
2239 selecting courses
最小费用最大流:
2195 going home
?2400 supervisor, supervisee

压缩存储的DP
1038 bugs integrated inc
1185 炮兵阵地
2430 lazy cow

最长公共子串(LCS):
1080 human gene functions
1159 palindrome
1458 common subsequence
2192 zipper

凸包
1113 wall
2187 beauty contest

阅读(4303) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册