POJ Problems

POJ 刷题记录 , 参照某题单.

注意： POJ 上 G++ 编译器小数输出用 %.f,C++ 编译器用 %.lf!

初期 :

一 . 基本算法 :

枚举 .
- POJ 1753
- POJ 2965
贪心
- POJ 1328: 求用最少的点覆盖区间。
- POJ 2109: 1. 高精度 + 二分 (POJ 数据开根不一定为整数，二分比较奇怪）， 2. 用 double 存 p，直接用 pow(p, 1.0 / n) 求根号。精度证明见这里
- POJ 2586: 贪心的选取最中间的作为亏损月。
递归和分治法 .
递推 .
构造法 . ( 什么鬼 …)
- POJ 3295: 表达式求值的变形 . 暴枚 $2^5$ 种可能性 , 每一个求一遍值 . ( 话说前后缀表达式用栈来写比中缀表达式用栈写要方便很多 , 但是我更 prefer 递归 )
模拟法 .
- POJ 1068
- POJ 2632: 按照题意逐步模拟。（输出信息抄错了！！！！！！）
- POJ 1573
- POJ 2993
- POJ 2996：直接按题意读入，排序，输出。

二 . 图算法 :

图的深度优先遍历和广度优先遍历 .
最短路径算法 (dijkstra,bellman-ford,floyd,heap+dijkstra)
- POJ 1860: SPFA 判负环（因为原图为双向边，所以一定能从负环上回来，若是单向边，问题就会更复杂）
- POJ 3259
- POJ 1062: 枚举地位值范围 [lb,rb]（显然 $l[0] \in [lb,rb]$ ), 对于直接购买（且地位值在取值范围内），从该点向 n+1 建价值的边，对于 py 购买，从该点向 py 对象连价值的边。然后跑最短路。
- POJ 2253
- POJ 1125: 直接 floyd, 求出单源最短路最大值最小的点。
- POJ 2240: 用 floyd 求负环（在本题中就是找乘积大于 1 的环）
最小生成树算法 (prim,kruskal)
- POJ 1789: 用 prim 求最小生成树。
- POJ 2485
- POJ 1258
- POJ 3026: 对 S，A 点求最小生成树，用 bfs 求各点的距离
拓扑排序
- POJ 1094
二分图的最大匹配 ( 匈牙利算法 )
- POJ 3041: 将输入中的行列看成点，点看成边，原题就变成了二分图的最小点覆盖（用点去覆盖所有边， = 匹配数）
- POJ 3020: 1. 状压 DP( 类似骨牌覆盖）， f[i][j][S]为 (i,j) 及其之后 (m-1) 个点是否被覆盖（o 点认为已经被覆盖），转移时枚举覆盖方式。 $O(2^mnm)$ 2. 将相邻的 * 连边，因其奇偶性不同，建成的一定是二分图。然后求最小边覆盖（用边覆盖所有点，= 顶点数 - 匹配数） $O((nm)^2)$
最大流的增广路算法 (KM 算法 ).
- POJ 1459
- POJ 3436

三 . 数据结构 .

串
- POJ 1035: 对于每一个串与字典串匹配可以在 O(len) 时间内完成，对于长度相同的，可以维护其不相同字符数，对于长度相差 1 的，可以求出其从开头和从结尾开始的公共序列长度，若其和大于等于较短的串，那么就合法。
- POJ 3080: 建一棵 trie, 插入所有的后缀 , 维护每一个子串被哪几个字符串包含 , 最后遍历 trie, 更新答案 . ( 把 len<3 输出无解看成 len<=3…)
- POJ 1936: 扫描匹配串，维护模式串匹配到的位数
排序 ( 快排、归并排 ( 与逆序数有关 )、堆排 )
- POJ 2388: 排序 + 取中位数
- POJ 2299
简单并查集的应用 .
哈希表和二分查找等高效查找法 ( 数的 Hash, 串的 Hash)
- POJ 3349: 直接对六个数 hash，判断相等应该 6×2 种同时判断，不要分开插入 hash 表中（否则会 T)。hash 函数要保证 12 种情况 hash 值相同（不同 hash 值选用方式看这里)
- POJ 3274
- POJ 2151:( 你确定是 hash???) 概率 DP, 首先计算出每一个人 A 掉 x 道题目的概率 f[x]（用递推）。然后计算总概率：设 g0[i]为前 i 人都 A 了 1 题的概率， g1[i]为前 i 人都 A 了 1 题的概率且前 i 人中至少 1 人 A 了至少 n 题的概率，显然转移为 $g1[i] = g1[i - 1] \cdot \sum{j = 1} ^ {n - 1} f[j] + g0[i - 1] \cdot \sum_{j = n} ^ m g[j], g0[i] = g0[i - 1] \cdot (1 - f[0])$
- POJ 1840: meeting in the middle. + hash / map
- POJ 2002
- POJ 2503：可以直接用 map<string, string>, 注意读入 (POJ 卡 cin，要关闭同步）。
哈夫曼树
- POJ 3253: 见标题。（long long)
堆
trie 树 ( 静态建树、动态建树 )
- POJ 2513

四 . 简单搜索

深度优先搜索
- POJ 2488
- POJ 3083: 对于第一问，我们直接模拟（如果手的那一侧没有障碍，就转弯，如果前方有障碍，就向反方向转），第二问直接 BFS。
- POJ 3009
- POJ 1321
- POJ 2251
广度优先搜索
- POJ 3278: 直接爆搜。
- POJ 1426: 不需要用队列，用类似 DP 的思路记录长度和 %n 的余数，并记录转移。用 ×10+1 和 ×10 的转移可以避免前导零的判断。
- POJ 3126: 根据题意进行转移。
- POJ 3087
- POJ 3414
简单搜索技巧和剪枝
- POJ 2531
- POJ 1416: 枚举所有剪断的方式，暴力用 map 维护总和以及剪断方式。
- POJ 2676
- POJ 1129

五 . 动态规划

背包问题 .
- POJ 1837：将前 i 个物品产生力距作为状态转移即可。
- POJ 1276：同[经典问题 1](/2017/10/06/Review-of-October#Oct-16th-VJ-Contest 经典问题 1) D 题。
型如下表的简单 DP( 可参考 lrj 的书 page149):
- E[j]=opt{D+w(i,j)}
  - POJ 3267
  - POJ 1836：两遍 LIS，然后枚举切断的点。
  - POJ 1260：（显然一定是一段区间被合并）1.f[i][j] 表示处理到第 i 位，还剩 j 颗珠子未处理 2.f[i][j] 表示处理到第 i 位，前 j 类珠子已经合并。转移易得。
  - POJ 2533
- E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} ( 最长公共子序列 )
  - POJ 3176
  - POJ 1080: LCS 变形，按照上下串是否用 - 填充转移。
  - POJ 1159
- C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.( 最优二分检索树问题 )

六 . 数学

组合数学 :
- 加法原理和乘法原理 .
- 排列组合 .
- 递推关系 .
- POJ 3252
- POJ 1850: 用类似数位 DP 的方法求出 f[i][j]:i 长度，首位为 j 的方案数。求解时分别计算长度小于 n 以及字典序比 s 小的数量，注意无解特判。
- POJ 1019: 暴力枚举每一个 1 ～ n 串的长度，再在最后一个串中枚举
- POJ 1942
数论 .( 素数与整除问题 , 进制位 , 同余模运算 )
- POJ 2635
- POJ 3292: 很有趣的数学题。设 $h(x) = 4x+1$ ，则根据定义可以得到一些性质： $h(a) \cdot h(b) = h(4ab + a + b)$ , 设 P 为 H-prime 集合，S 为 H-Semi-prime 集合，则 $\forall a, b \in N, h(a) \cdot h(b) \notin P$ 那么我们可以用这一条性质用埃氏筛筛 H-prime. $\forall h(a), h(b) \in P, h(a) \cdot h(b) \in S$ , 那么我们可以枚举两个 H-prime，来求 H-Semi-prime.
- POJ 1845: 对于求一个数的约数和：设数 x 的质因数分解为 $x = \prod p_i^{a_i}$ , 则根据约数的生成方式可得其约数和 $sum = \prod_{i} \sum_{j = 0} ^ {a_i} p_i ^ {j}$ , 那么一个数的 k 次的约数和 $sum_k = \prod_i \sum_{j = 0} ^ {ka_i} p_i ^{j} = \prod_i \frac {p_i ^ {ka_i + 1} - 1} {p_i - 1}$ , 那么在筛质数时顺便求一下即可。但是要注意： $p_i - 1$ 有可能是 MOD（9901）的倍数，这时逆元不存在，要特判一下。
- POJ 2115: 原题即求 $cx \equiv b - a (mod\ 2 ^ k)$ 的最小非负整数解。令 $b - a = t, 2 ^ k = m$ ，则 $cx + my = t$ ，则当 $\gcd(c, m) | t$ 时方程有解。用 exgcd 求即可。输出最小值：显然若 $x = x_0$ 为解，则 $x_0 + k \frac {m} {\gcd(c, m)}, k \in Z$ 均为解。则最小非负整数解为 $x_0 \mod {\frac {m} {\gcd(c, m)}}$ , 若 $x_0$ 为负数同理易推。
计算方法 . 二分法求解单调函数相关知识 .
- POJ 3273
- POJ 3258: 最大化最小值二分，注意在二分最大值的时候， mid 的求法以及更新区间方法和二分最小值有所不同。( 但是似乎还是在二分时顺便更新答案较方便。）
- POJ 1905
- POJ 3122

七 . 计算几何学 .

几何公式 .
叉积和点积的运用 ( 如线段相交的判定 , 点到线段的距离等 ).
- POJ 2031
- POJ 1039: 计算几何 1.0 中的题目，枚举直线，判断是否越界。
多边型的简单算法 ( 求面积 ) 和相关判定 ( 点在多边型内 , 多边型是否相交 )
- POJ 1408
- POJ 1584
凸包 .
- POJ 2187
- POJ 1113：凸包周长 + $2\pi l$ , 鬼畜输出格式

中级 :

一 . 基本算法 :

C++ 的标准模版库的应用 .
- poj3096: 随便开个 bool 数组记录是否出现。（居然输出末尾有句点！！）
- poj3007: 枚举 8 种拼接方式，存到 set/hash_table 中。
较为复杂的模拟题的训练
- poj3393
- poj1472
- poj3371: 根据题意找句号 + 删标点 + 删后缀（以及特判）再求音节数（把原题题面扔进标算答案小于 40。。。）
- poj1027: DFS 求联通块 + 按题意模拟行列移动 + 卡 STL。
- poj2706: 模拟每次加入一个点时，能够与那些点连线（判断距离 + 是否有相交），并用并查集维护连通性，最后看一下是否连通

二 . 图算法 :

差分约束系统的建立和求解 .
- poj1201
- poj2983
最小费用最大流
- poj2516
- poj2195
双连通分量
- poj2942
强连通分支及其缩点 .
- poj2186
图的割边和割点
- poj3352: 先求出边双并缩点，显然是一棵树。设叶节点数量为 x，则答案为 $\lfloor \frac {x + 1} {2} \rfloor$ ( 证明思路：每加一条边，可以使 2 个度为 1 的点变成度为 2 的。
最小割模型、网络流规约
- poj3308

三 . 数据结构 .

线段树 .
- poj2528: 区间覆盖（注意 pushdown 的写法，原 tag 清零）。
- poj2828: 离线操作，逆序操作。则每次只需要知道第 pos[i] + 1 个空位是哪一个即可。用线段树维护即可。
- poj2777: 用二进制位来表示不同颜色。其他的就是普通的区间覆盖区间查询。
- poj2886
- poj2750
静态二叉检索树 .
- poj2482
- poj2352
树状树组
- poj1195
- poj3321: 对树进行 dfs 序（在进入时增加计数器），设 x 子树进入时间戳和离开时间戳为 st[x] 和 en[x], 那么一个子树所对应区间为 [st[x], en[x]], 那么只需要在 BIT 上单点修改，询问上述区间即可。
RMQ.
- poj3264
- poj3368
并查集的高级应用 .
- poj1703：并查集维护种类信息。（维护的应该是与 fa[] 数组对应点的关系！）
- poj2492
KMP 算法 .
- poj1961
- poj2406

四 . 搜索

最优化剪枝和可行性剪枝
搜索的技巧和优化
- poj3411
- poj1724
记忆化搜索
- poj3373
- poj1691

五 . 动态规划

较为复杂的动态规划 ( 如动态规划解特别的施行商问题等 )
- poj1191
- poj1054（IOI2002）: 直接枚举直线的前两个点 , 如果它上一步不在区间外，或区间内长度小于目前，或路径上有点未被覆盖，则剪枝。
- poj3280
- poj2029: 记录前缀和，然后枚举每一个区间。
- poj2948: 由题意得：对于某一行，一定是某点左侧的全部运到最左边，右侧的运到最上面。而且上面一行这个点的位置一定不会在下面一行的右侧（否则就会有浪费）。那么只需要记录 f[i][j] 表示第 i 行，分割点在 j 列的右面的最大收益，然后从下面一行转移。
- poj1925
- poj3034：同T42 B 题，将坐标作为状态来转移。
记录状态的动态规划 .
- POJ3254: 类似于骨牌覆盖，状压自己及之后 m 个格子哪些格子不能选。
- poj2411
- poj1185
树型动态规划
- poj2057
  设 leaves[i] 为 i 子树的叶节点数，sz[i] 为遍历整棵 i 子树的代价，设 $h(x) = \begin {cases} sz[x] + 2, & \text{$ x$ doesn’t have a worm }\2, & \text{ $x$ has a worm} \end{cases} $法一：直接用期望计算，转移时再利用一次状压 DP 来确定遍历顺序，转移时分别计算该子树内找到和找不到的情况对答案的贡献。法二：用平均值计算。此时可以同样用状压 DP 确定遍历顺序（转移时加上该子树的操作数和之前未找到情况对答案的影响）。优化（贪心）：考虑到转移的后半部分为 (S 表示已经遍历过的子树集合 , cur 为目前枚举的 )$ (\sum_{x \in S}h(x)) \cdot leaves[cur] $，将它整个展开后可以得到（`perm[]` 表示枚举顺序）：$ \sum leaves[perm[i]] \sum_{j \lt i} h(perm[j])$，可以通过交换相邻元素法证明 $h(x)/leaves[x]$ 较小的应该先枚举。那么我们就可以根据这个排序计算答案。
- poj1947
- poj2486
  设 f[i][j][0/1] 表示第 i 棵子树中用 j 步操作，是否需要返回根结点时所能获得最大值。在转移时考虑该子节点是否返回父节点分别求值。
- poj3140

六 . 数学

组合数学 :
1. 容斥原理 .
2. 抽屉原理 .
3. 置换群与 Polya 定理
  - poj1286
  - poj2409
  - poj3270
  - poj1026
4. 递推关系和母函数 .
数学 .
1. 高斯消元法模板
  - poj2947
  - poj1487
  - poj2065
  - poj1166: 1. 直接 BFS, 状态压成四进制位（可以用位运算处理）。2. 也可以列出模意义下的方程组 , 每一个方程代表一个 clock，系数代表在对应的 1…9 操作中是否存在 . 唯一需要注意的时，在最后求解的时候，因为模数为 4，所以无法用逆元的方式除以系数，只能枚举[0…3]是否符合条件。（然而 BFS 0ms， Gauss 16ms。。）
  - poj1222
2. 概率问题 .
  - poj3071: 概率 DP，f[i][j]表示第 i 轮第 j 队胜出的概率。根据淘汰赛赛制可知它有可能的对手是固定的 $2^{i-1}$ 个，可以推一下（整张比赛图中每个点的取值就类似于一棵线段树），那么转移就是（设其对手集合为 S）: $f[i][j] = f[i - 1][j] \cdot \sum_{k \in S} f[i - 1][k] \cdot p[j][k]$
  - poj3440
3. GCD、扩展的欧几里德 ( 中国剩余定理 )
  - poj3101
计算方法 .
1. 0/1 分数规划 .
  - poj2976: 其实 01 分数规划就是二分 + 不等式变换。应用范围：求一个分式的最值，且无法通过数学方法分析。（参见 T25 A 题 )
    就本题而言，设 S 为选的元素集合，设 $f(x) = \exists S \frac {\sum_{i \in S} {a_i}} {\sum_{i \in S} {b_i}} \geq x$ 。显然可以通过这个进行二分。但左边很难求，那么将不等式变换得：
  $\frac {\sum_{i \in S} {a_i}} {\sum_{i \in S} {b_i}} \geq x \\ \sum_{i \in S} {a_i} \geq x \cdot \sum_{i \in S} {b_i} \\ \sum_{i \in S} {a_i}- x \cdot \sum_{i \in S} {b_i} \geq 0 \\ \sum_{i \in S} (a_i - b_ix) \geq 0$
  那么我们就可以贪心地选择 $a_i - b_ix$ $a_{i} - b_{i} x$ 最大的 (n - k) 个数，判断其和是否大于零。
2. 三分法求解单峰 ( 单谷 ) 的极值 .
3. 矩阵法
  - poj3150
  - poj3422
  - poj3070
4. 迭代逼近
  - poj3301
随机化算法
- poj3318: 既然 $O(n^3)$ 完整验证不可行，那么只能部分验证： 1. rand 一些位置进行比较，如果都正确那么就认为是 YES（默认 rand 过不去（似乎 POJ 的 g++ 不支持 srand），然后我又手动 rand 了一个 rand() 函数才过） 2. rand 一个 $1 \times n$ 的向量 $r$ , 则若 $r \cdot A \cdot B = r \cdot C$ 就认为等式成立。
- poj2454: 神奇的随机化。。可以选前 2k 个数，然后 random 其分配顺序（具体就是先确定一个排列，然后随机交换两个元素），直至出解。（应用范围：在可行答案较多，且搜索过不去的情况下）
杂题 .
- poj1870
- poj3296
- poj3286
- poj1095

七 . 计算几何学 .

坐标离散化 .
扫描线算法 ( 例如求矩形的面积和周长并 , 常和线段树或堆一起使用 ).
- poj1765
- poj1177
- poj1151
- poj3277
- poj2280
- poj3004
多边形的内核 ( 半平面交 )
- poj3130
- poj3335
几何工具的综合应用 .
- poj1819
- poj1066
- poj2043
- poj3227
- poj2165
- poj3429

高级 :

一 . 基本算法要求 :

代码快速写成 , 精简但不失风格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
保证正确性和高效性 . poj3434

二 . 图算法 :

度限制最小生成树和第 K 最短路 . (poj1639)
最短路 , 最小生成树 , 二分图 , 最大流问题的相关理论 ( 主要是模型建立和求解 )(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最优比率生成树 . (poj2728)
最小树形图 (poj3164)
次小生成树 .
无向图、有向图的最小环

三 . 数据结构 .

trie 图的建立和应用 . (poj2778)
LCA 和 RMQ 问题 (LCA( 最近公共祖先问题 ) 有离线算法 ( 并查集 +dfs) 和在线算法 (RMQ+dfs)).(poj1330)
双端队列和它的应用 ( 维护一个单调的队列 , 常常在动态规划中起到优化状态转移
的目的 ). (poj2823)
左偏树 ( 可合并堆 ).
后缀树 ( 非常有用的数据结构 , 也是赛区考题的热点 ).
(poj3415,poj3294)

四 . 搜索

较麻烦的搜索题目训练 (poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
广搜的状态优化 : 利用 M 进制数存储状态、转化为串用 hash 表判重、按位压缩存储
状态、双向广搜、A*算法 . (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
深搜的优化 : 尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大
、可以考虑双向搜索或者是轮换搜索、IDA*算法 . (poj3131,poj2870,poj2286)

五 . 动态规划

需要用数据结构优化的动态规划 . (poj2754,poj3378,poj3017)
四边形不等式理论 .
较难的状态 DP(poj3133)

六 . 数学

组合数学 .
1. MoBius 反演 (poj2888,poj2154)
2. 偏序关系理论 .
博奕论 .
1. 极大极小过程 (poj3317,poj1085)
2. Nim 问题 .

七 . 计算几何学 .

半平面求交 (poj3384,poj2540)
可视图的建立 (poj2966)
点集最小圆覆盖 .
对踵点 (poj2079)

八 . 综合题 .

poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)