# POJ-Solving-Reports
**Repository Path**: exppoc/POJ-Solving-Reports
## Basic Information
- **Project Name**: POJ-Solving-Reports
- **Description**: POJ 解题报告
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No
## Statistics
- **Stars**: 1
- **Forks**: 0
- **Created**: 2023-02-16
- **Last Updated**: 2023-02-16
## Categories & Tags
**Categories**: Uncategorized
**Tags**: None
## README
# POJ-Solving-Reports
> POJ 解题报告
------
## 相关资源
- [北大 POJ 题库（官网在线）](http://poj.org/)
- [北大 POJ 题库（离线版）](/doc/POJ%E7%A6%BB%E7%BA%BF%E7%89%88%E9%A2%98%E7%9B%AE.chm)
- [POJ封面书《程序设计导引及在线实践》](/doc/程序设计导引及在线实践.pdf)
- [ACM 资料](https://lyy289065406.github.io/articles/tags/ACM/)
------
## 1. 入门水题
| 可用于练手与增强自信 |
| :------: |
| [POJ-1000](/reports/POJ1000-a%20plus%20b) [POJ-1003](/reports/POJ1003-Hangover) [POJ-1004](/reports/POJ1004-Financial%20Management) [POJ-1005](/reports/POJ1005-I%20Think%20I%20Need%20a%20Houseboat) [POJ-1207](/reports/POJ1207-The%203n%20plus%201%20problem) [POJ-3299](/reports/POJ3299-Humidex) [POJ-2159](/reports/POJ2159-Ancient%20Cipher) [POJ-1083](/reports/POJ1083-Moving%20Tables) [POJ-3094](/reports/POJ3094-Quicksum) |
------
## 2. 初级
| 2.1. 基本算法 | - |
| :----: |:----:|
| 枚举 | [POJ-1753](/reports/POJ1753-Flip%20Game) [POJ-2965](/reports/POJ2965-The%20Pilots%20Brothers%20refrigerator) |
| 贪心 | [POJ-1328](/reports/POJ1328-Radar%20Installation) [POJ-2586](/reports/POJ2586-Y2K%20Accounting%20Bug) |
| 递归和分治法 | - |
| 递推 | - |
| 构造法 | [POJ-3295](/reports/POJ3295-Tautology) [POJ-3239](/reports/POJ3239-Solution%20to%20the%20n%20Queens%20Puzzle) |
| 模拟法 | [POJ-1008](/reports/POJ1008-Maya%20Calendar) [POJ-1068](/reports/POJ1068-Parencodings) [POJ-2632](/reports/POJ2632-Crashing%20Robots) [POJ-1573](/reports/POJ1573-Robot%20Motion) [POJ-2993](/reports/POJ2993-Emag%20eht%20htiw%20Em%20Pleh) [POJ-2996](/reports/POJ2996-Help%20Me%20with%20the%20Game) [POJ-3087](/reports/POJ3087-Shufflem%20Up) |
| 高精度算法 | [POJ-1001](/reports/POJ1001-Exponentiation) [POJ-1503](/reports/POJ1503-Integer%20Inquiry) [POJ-2109](/reports/POJ2109-Power%20of%20Cryptography) [POJ-2389](/reports/POJ2389-Bull%20Math) [POJ-2602](/reports/POJ2602-Superlong%20sums) [POJ-3982](/reports/POJ3982-The%20Fibonacci%20sequence) |
| 2.2. 图算法 | - |
| :----: |:----:|
| 图遍历（前序序列、中序序列、后序序列） | [POJ-2255](/reports/POJ2255-Tree%20Recovery) |
| 最短路径算法
（dijkstra, bellman-ford,
floyd, heap+dijkstra） | [POJ-1860](/reports/POJ1860-Currency%20Exchange) [POJ-3259](/reports/POJ3259-Wormholes) [POJ-1062](/reports/POJ1062-Expensive%20dowry)
[POJ-2253](/reports/POJ2253-Frogger) [POJ-1125](/reports/POJ1125-Stockbroker%20Grapevine) [POJ-2240](/reports/POJ2240-Arbitrage) |
| 最小生成树算法（prim, kruskal） | [POJ-1789](/reports/POJ1789-Truck%20History) [POJ-2485](/reports/POJ2485-Highways) [POJ-1258](/reports/POJ1258-Agri-Net) [POJ-3026](/reports/POJ3026-Borg%20Maze) |
| 拓扑排序 | [POJ-1094](/reports/POJ1094-Sorting%20It%20All%20Out) |
| 二分图的最大匹配 （匈牙利算法） | [POJ-3041](/reports/POJ3041-Asteroids) [POJ-3020](/reports/POJ3020-Antenna%20Placement) |
| 最大流的增广路算法（压入重标法、KM算法） | [POJ-1459](/reports/POJ1459-Power%20Network) [POJ-3436](/reports/POJ3436-ACM%20Computer%20Factory) |
| 2.3. 数据结构 | - |
| :----: |:----:|
| 串 | [POJ-1016](/reports/POJ1016-Numbers%20That%20Count) [POJ-1035](/reports/POJ1035-Spell%20checker) [POJ-3080](/reports/POJ3080-Blue%20Jeans) [POJ-1936](/reports/POJ1936-All%20in%20All) |
| 排序（快排、归并排、堆排） | [POJ-1007](/reports/POJ1007-DNA%20Sorting) [POJ-2388](/reports/POJ2388-Whos%20in%20the%20Middle) [POJ-1804](/reports/POJ1804-Brainman) [POJ-2299](/reports/POJ2299-Ultra-QuickSort) |
| 并查集 | - |
| 高效查找法
（数的Hash、串的Hash、二分查找） | [POJ-1002](/reports/POJ1002-487-3279) [POJ-3349](/reports/POJ3349-Snowflake%20Snow%20Snowflakes) [POJ-3274](/reports/POJ3274-Gold%20Balanced%20Lineup) [POJ-1840](/reports/POJ1840-Eqs) [POJ-2002](/reports/POJ2002-Squares) [POJ-3432](/reports/POJ3432-Count%20Squares) [POJ-2503](/reports/POJ2503-Babelfish) |
| 哈夫曼树、优先队列 | [POJ-3253](/reports/POJ3253-Fence%20Repair) |
| 堆 | - |
| trie树（静态建树、动态建树） | [POJ-2513](/reports/POJ2513-Colored%20Sticks) |
| 2.4. 搜索 | - |
| :----: |:----:|
| 深度优先搜索DFS | [POJ-2488](/reports/POJ2488-A%20Knights%20Journey) [POJ-3083](/reports/POJ3083-Children%20of%20the%20Candy%20Corn) [POJ-3009](/reports/POJ3009-Curling%202.0) [POJ-1321](/reports/POJ1321-Chess%20Problem) |
| 广度优先搜索BFS | [POJ-3278](/reports/POJ3278-Catch%20That%20Cow) [POJ-1426](/reports/POJ1426-Find%20The%20Multiple) [POJ-3126](/reports/POJ3126-Prime%20Path) [POJ-3414](/reports/POJ3414-Pots) [POJ-2251](/reports/POJ2251-Dungeon%20Master) |
| 简单搜索技巧和剪枝 | [POJ-1010](/reports/POJ1010-STAMPS) [POJ-2362](/reports/POJ2362-Square) [POJ-1011](/reports/POJ1011-Sticks) [POJ-1416](/reports/POJ1416-Shredding%20Company) [POJ-2676](/reports/POJ2676-Sudoku) [POJ-1129](/reports/POJ1129-Channel%20Allocation) |
| 2.5. 动态规划 | - | - |
| :----: |:----:|:----:|
| 背包问题 | - | [POJ-1837](/reports/POJ1837-Balance) [POJ-1276](/reports/POJ1276-Cash%20Machine) [POJ-1014](/reports/POJ1014-Dividing) |
| DP（动态规划）
可参考《刘汝佳：算法法艺术与信息学竞赛》
（黑书一）page 149 | `E[j] = opt{D+w(i,j)}` | [POJ-1018](/reports/POJ1018-Communication%20System) [POJ-3267](/reports/POJ3267-The%20Cow%20Lexicon) [POJ-1260](/reports/POJ1260-Pearls) |
| - | 最长公共子序列
`E[i,j] = opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij}` | [POJ-1015](/reports/POJ1015-Jury%20Compromise) [POJ-3176](/reports/POJ3176-Cow%20Bowling) [POJ-1163](/reports/POJ1163-The%20Triangle) [POJ-1080](/reports/POJ1080-Human%20Gene%20Functions) [POJ-1159](/reports/POJ1159-Palindrome) [POJ-2533](/reports/POJ2533-Longest%20Ordered%20Subsequence) [POJ-1836](/reports/POJ1836-Alignment) |
| - | 最优二分检索树问题
`C[i,j] = w[i,j]+opt{C[i,k-1]+C[k,j]}` | - |
| 2.6. 数学 | - | - |
| :----: |:----:|:----:|
| 组合数学 | 加法原理和乘法原理 | |
| - | 排列组合 | [POJ-3252](/reports/POJ3252-Round%20Numbers) [POJ-1850](/reports/POJ1850-Code) [POJ-1496](/reports/POJ1496-Word%20Index) [POJ-1942](/reports/POJ1019-Number%20Sequence) |
| - | 递推关系 | [POJ-1012](/reports/POJ1012-Joseph) [POJ-1019](/reports/POJ1019-Number%20Sequence) |
| - | 逻辑推理 | [POJ-1013](/reports/POJ1013-Counterfeit%20Dollar) [POJ-1017](/reports/POJ1017-Packets) |
| 数论 | 素数与整除问题 | [POJ-2739](/reports/POJ2739-Sum%20of%20Consecutive%20Prime%20Numbers) [POJ-2262](/reports/POJ2262-Goldbachs%20Conjecture) [POJ-3006](/reports/POJ3006-Dirichlets%20Theorem) |
| - | 进制位 | - |
| - | 同余模运算 | [POJ-2305](/reports/POJ2305-Basic%20remains) [POJ-2635](/reports/POJ2635-The%20Embarrassed%20Cryptographer) [POJ-3292](/reports/POJ3292-Semi-prime%20H-numbers) [POJ-1845](/reports/POJ1845-Sumdiv) [POJ-2115](/reports/POJ2115-C%20Looooops) |
| - | 中国余数定理
（扩展欧几里德、辗转相除法） | [POJ-1006](/reports/POJ1006-Biorhythms) |
| 计算方法 | 二分法求解单调函数 | [POJ-3273](/reports/POJ3273-Monthly%20Expense) [POJ-3258](/reports/POJ3258-River%20Hopscotch) [POJ-1905](/reports/POJ1905-Expanding%20Rods) [POJ-3122](/reports/POJ3122-Pie) |
| - | 随机化算法 | [POJ-2531](/reports/POJ2531-Network%20Saboteur) |
| - | 概率 | [POJ-2151](/reports/POJ2151-Check%20the%20difficulty%20of%20problems) |
| 2.7. 计算几何学 | - |
| :----: |:----:|
| 几何公式 | [POJ-2031](/reports/POJ2031-Building%20a%20Space%20Station) |
| 叉积和点积的运用
（如线段相交的判定、点到线段的距离等） | [POJ-1039](/reports/POJ1039-Pipe) |
| 多边形的简单算法（求面积） 和
相关判定（点在多边形内、多边形是否相交） | [POJ-1408](/reports/POJ1408-Fishnet) [POJ-1584](/reports/POJ1584-A%20Round%20Peg%20in%20a%20Ground%20Hole) |
| 凸包 | [POJ-1696](/reports/POJ1696-Space%20Ant) [POJ-2187](/reports/POJ2187-Beauty%20Contest) [POJ-1113](/reports/POJ1113-Wall) |
------
## 3. 中级
| 3.1. 基本算法 | - |
| :----: |:----:|
| C++的标准模版库的应用 | [POJ-3096](/reports/POJ3096-Surprising%20Strings) [POJ-3007](/reports/POJ3007-Organize%20Your%20Train%20part%20II) |
| 较为复杂的模拟题的训练 | [POJ-3393](/reports/POJ3393-Lucky%20and%20Good%20Months%20by%20Gregorian%20Calendar) [POJ-1472](/reports/POJ1472-Instant%20Complexity) [POJ-3371](/reports/POJ3371-Flesch%20Reading%20Ease) [POJ-1027](/reports/POJ1027-The%20Same%20Game) [POJ-2706](/reports/POJ2706-Connect) [POJ-1009](/reports/POJ1009-Edge%20Detection) |
| 3.2. 图算法 | - |
| :----: |:----:|
| 差分约束系统的建立和求解 | [POJ-1716](/reports/POJ1716-Integer%20Intervals) [POJ-1201](/reports/POJ1201-Intervals) [POJ-2983](/reports/POJ2983-Is%20the%20Information%20Reliable) |
| 最小费用最大流 | [POJ-2516](/reports/POJ2516-Minimum%20Cost) [POJ-2195](/reports/POJ2195-Going%20Home) |
| 双连通分量 | [POJ-2942](/reports/POJ2942-Knights%20of%20the%20Round%20Table) |
| 强连通分支及其缩点 | [POJ-2186](/reports/POJ2186-Popular%20Cows) |
| 图的割边和割点 | [POJ-1523](/reports/POJ1523-SPF) [POJ-3352](/reports/POJ3352-Road%20Construction) [POJ-3177](/reports/POJ3177-Redundant%20Paths) |
| 最小割模型、网络流规约 | [POJ-3308](/reports/POJ3308-Paratroopers) |
| 3.3. 数据结构 | - |
| :----: |:----:|
| 线段树 | [POJ-2528](/reports/POJ2528-Mayors%20posters) 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](/reports/POJ1020-Anniversary%20Cake) [POJ-3411](/reports/POJ3411-Paid%20Roads) [POJ-1724](/reports/POJ1724-ROADS) |
| 记忆化搜索 | [POJ-3373](/reports/POJ3373-Changing%20Digits) [POJ-1691](/reports/POJ1691-Painting%20A%20Board) |
| 搜索与状态压缩 | [POJ-1184](/reports/POJ1184-Smart%20typist) |
| 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](/reports/POJ2525-Text%20Formalization) 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 |
------
## 版权声明
[-EXP%202016-blue.svg)](http://exp-blog.com) [](https://www.gnu.org/licenses/gpl-3.0)
- Site: [http://exp-blog.com](http://exp-blog.com)
- Mail: 289065406@qq.com
------