POJ-Solving-Reports

POJ 解题报告

1. 入门水题

可用于练手与增强自信
POJ-1000 POJ-1003 POJ-1004 POJ-1005 POJ-1207 POJ-3299 POJ-2159 POJ-1083 POJ-3094

2. 初级

2.1. 基本算法	-
枚举	POJ-1753 POJ-2965
贪心	POJ-1328 POJ-2586
递归和分治法	-
递推	-
构造法	POJ-3295 POJ-3239
模拟法	POJ-1008 POJ-1068 POJ-2632 POJ-1573 POJ-2993 POJ-2996 POJ-3087
高精度算法	POJ-1001 POJ-1503 POJ-2109 POJ-2389 POJ-2602 POJ-3982

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.3. 数据结构	-
串	POJ-1016 POJ-1035 POJ-3080 POJ-1936
排序（快排、归并排、堆排）	POJ-1007 POJ-2388 POJ-1804 POJ-2299
并查集	-
高效查找法（数的Hash、串的Hash、二分查找）	POJ-1002 POJ-3349 POJ-3274 POJ-1840 POJ-2002 POJ-3432 POJ-2503
哈夫曼树、优先队列	POJ-3253
堆	-
trie树（静态建树、动态建树）	POJ-2513

2.4. 搜索	-
深度优先搜索DFS	POJ-2488 POJ-3083 POJ-3009 POJ-1321
广度优先搜索BFS	POJ-3278 POJ-1426 POJ-3126 POJ-3414 POJ-2251
简单搜索技巧和剪枝	POJ-1010 POJ-2362 POJ-1011 POJ-1416 POJ-2676 POJ-1129

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.6. 数学	-	-
组合数学	加法原理和乘法原理
-	排列组合	POJ-3252 POJ-1850 POJ-1496 POJ-1942
-	递推关系	POJ-1012 POJ-1019
-	逻辑推理	POJ-1013 POJ-1017
数论	素数与整除问题	POJ-2739 POJ-2262 POJ-3006
-	进制位	-
-	同余模运算	POJ-2305 POJ-2635 POJ-3292 POJ-1845 POJ-2115
-	中国余数定理（扩展欧几里德、辗转相除法）	POJ-1006
计算方法	二分法求解单调函数	POJ-3273 POJ-3258 POJ-1905 POJ-3122
-	随机化算法	POJ-2531
-	概率	POJ-2151

2.7. 计算几何学	-
几何公式	POJ-2031
叉积和点积的运用（如线段相交的判定、点到线段的距离等）	POJ-1039
多边形的简单算法（求面积）和相关判定（点在多边形内、多边形是否相交）	POJ-1408 POJ-1584
凸包	POJ-1696 POJ-2187 POJ-1113

3. 中级

3.1. 基本算法	-
C++的标准模版库的应用	POJ-3096 POJ-3007
较为复杂的模拟题的训练	POJ-3393 POJ-1472 POJ-3371 POJ-1027 POJ-2706 POJ-1009

3.2. 图算法	-
差分约束系统的建立和求解	POJ-1716 POJ-1201 POJ-2983
最小费用最大流	POJ-2516 POJ-2195
双连通分量	POJ-2942
强连通分支及其缩点	POJ-2186
图的割边和割点	POJ-1523 POJ-3352 POJ-3177
最小割模型、网络流规约	POJ-3308

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.4. 搜索	-
最优化剪枝和可行性剪枝	-
搜索的技巧和优化	POJ-1020 POJ-3411 POJ-1724
记忆化搜索	POJ-3373 POJ-1691
搜索与状态压缩	POJ-1184

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. 高级

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

版权声明

Site: http://exp-blog.com
Mail: 289065406@qq.com

Name		Name	Last commit message	Last commit date
Latest commit History 237 Commits
.github		.github
doc		doc
reports		reports
.gitignore		.gitignore
README.md		README.md

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Repository files navigation

POJ-Solving-Reports

相关资源

1. 入门水题

2. 初级

3. 中级

4. 高级

版权声明

About

Uh oh!

Releases

Sponsor this project

Uh oh!

Packages

Uh oh!

Uh oh!

Contributors

Uh oh!

Languages

Uh oh!

Folders and files

Latest commit

History

Repository files navigation

POJ-Solving-Reports

相关资源

1. 入门水题

2. 初级

3. 中级

4. 高级

版权声明

About

Topics

Resources

Uh oh!

Stars

Watchers

Forks

Releases

Sponsor this project

Uh oh!

Packages 0

Uh oh!

Uh oh!

Contributors

Uh oh!

Languages

Packages