POJ 解题报告
可用于练手与增强自信 |
---|
POJ-1000 POJ-1003 POJ-1004 POJ-1005 POJ-1207 POJ-3299 POJ-2159 POJ-1083 POJ-3094 |
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.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.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