北大 ACM - POJ 试题分类

1. 入门水题

2.2. 图算法 -

图遍历（前序序列、中序序列、后序序列） POJ-2255

最短路径算法
（dijkstra, bellman-ford,
floyd, heap+dijkstra） POJ-1860 POJ-3259 POJ-1062
POJ-2253 POJ-1125 POJ-2240

最小生成树算法（prim, kruskal） POJ-1789 POJ-2485 POJ-1258 POJ-3026

拓扑排序 POJ-1094

二分图的最大匹配 （匈牙利算法） POJ-3041 POJ-3020

最大流的增广路算法（压入重标法、KM算法） POJ-1459 POJ-3436

2.5. 动态规划 - -

背包问题 - POJ-1837 POJ-1276 POJ-1014

DP（动态规划）
可参考《刘汝佳：算法法艺术与信息学竞赛》
（黑书一）page 149 E[j] = opt{D+w(i,j)} POJ-1018 POJ-3267 POJ-1260

- 最长公共子序列
E[i,j] = opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} POJ-1015 POJ-3176 POJ-1163 POJ-1080 POJ-1159 POJ-2533 POJ-1836

- 最优二分检索树问题
C[i,j] = w[i,j]+opt{C[i,k-1]+C[k,j]}

2.7. 计算几何学 -

几何公式 POJ-2031

叉积和点积的运用
（如线段相交的判定、点到线段的距离等） POJ-1039

多边形的简单算法（求面积） 和
相关判定（点在多边形内、多边形是否相交） POJ-1408 POJ-1584

凸包 POJ-1696 POJ-2187 POJ-1113

3.3. 数据结构 -

线段树 POJ-2528 POJ-2828 POJ-2777 POJ-2886 POJ-2750

静态二叉检索树 POJ-2482 POJ-2352

树状树组 POJ-1195 POJ-3321

RMQ POJ-3264 POJ-3368

并查集 POJ-1703 POJ-2492

KMP算法 POJ-1961 POJ-2406

3.5. 动态规划 -

较复杂的动态规划
（如特别的旅行商问题等） POJ-1191 POJ-1054 POJ-3280 POJ-2029 POJ-2948 POJ-1925 POJ-3034

记录状态的动态规划 POJ-3254 POJ-2411 POJ-1185

树型动态规划 POJ-2057 POJ-1947 POJ-2486 POJ-3140

3.6. 数学 - -

组合数学 容斥原理

- 抽屉原理

- 置换群与Polya定理 POJ-1286 POJ-2409 POJ-3270 POJ-1026

- 递推关系和母函数

数论 高斯消元法 POJ-2947 POJ-1487 POJ-2065 POJ-1166 POJ-1222

- 概率问题 POJ-3071 POJ-3440

- GCD（最大公约数）
LCM（最小公倍数） POJ-3101

- 中国余数定理
（扩展欧几里德、辗转相除法）

计算方法 0/1分数规划 POJ-2976

- 三分法求解单峰/单谷的极值

- 矩阵法 POJ-3150 POJ-3422 POJ-3070

- 迭代逼近 POJ-3301

随机化算法

POJ-3318 POJ-2454

杂题

POJ-1870 POJ-3296 POJ-3286 POJ-1095

3.7. 计算几何学 -

坐标离散化

扫描线算法
（如求矩形的面积和周长，常和线段树或堆一起使用） POJ-1765 POJ-1177 POJ-1151 POJ-3277 POJ-2280 POJ-3004

多边形的内核（半平面交） POJ-3130 POJ-3335

几何工具的综合应用 POJ-1819 POJ-1066 POJ-2043 POJ-3227 POJ-2165 POJ-3429

4.1. 基本算法 -

代码快速写成（精简但不失风格） POJ-2525 POJ-1684 POJ-1421 POJ-1048 POJ-2050 POJ-3306

保证正确性和高效性 POJ-3434

4.2. 图算法 -

度限制最小生成树 和 第K最短路 POJ-1639

最短路、最小生成树、二分图、最大流问题的相关理论
（主要是模型建立和求解） POJ-3155 POJ-2112 POJ-1966 POJ-3281 POJ-1087 POJ-2289 POJ-3216 POJ-2446

最优比率生成树 POJ-2728

最小树形图 POJ-3164

次小生成树

无向图、有向图的最小环

4.3. 数据结构 -

trie图的建立和应用 POJ-2778

LCA和RMQ问题：
LCA（最近公共祖先问题）
离线算法（并查集+dfs）
在线算法（RMQ+dfs） POJ-1330

双端队列和应用
（维护一个单调的队列，常在动态规划中起到优化状态转移的目的） POJ-2823

左偏树（可合并堆）

后缀树 POJ-3415 POJ-3294

4.4. 搜索 -

较麻烦的搜索题目训练 POJ-1069 POJ-3322 POJ-1475 POJ-1924 POJ-2049 POJ-3426

广搜优化
（利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法）（RMQ+dfs） POJ-1768 POJ-1184 POJ-1872 POJ-1324 POJ-2046 POJ-1482

深搜优化
（尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法） POJ-3131 POJ-2870 POJ-2286

4.5. 动态规划 -

需要用数据结构优化的动态规划 POJ-2754 POJ-3378 POJ-3017

四边形不等式理论

较难的状态DP POJ-3133

4.6. 数学 - -

组合数学 MoBius反演 POJ-2888 POJ-2154

- 偏序关系理论

计算方法 极大极小过程 POJ-3317 POJ-1085

- Nim问题

4.7. 计算几何学 -

半平面求交 POJ-3384 POJ-2540

可视图的建立 POJ-2966

点集最小圆覆盖

对踵点 POJ-2079

4.8. 综合题

POJ-3109 POJ-1478 POJ-1462 POJ-2729 POJ-2048 POJ-3336 POJ-3315 POJ-2148 POJ-1263