计算几何

无

树套树 1

图论 1

图论 2

无

见专题部分

字符串基础

字符串匹配

字符串哈希

字典树(Trie)

前缀函数与 KMP 算法

无

见专题部分

洛谷p1742

最小圆覆盖模板

洛谷p5192

网络流

一个摄影师，$n$ 天时间，$m$ 个取材对象。要求 $n$ 天后第 $x$ 个取材对象至少需要取材 $G_x$ 张照片。

第 $k$ 天可以取材 $C_k$ 个对象，总共可以取材 $D_k$ 张照片，当天每个可取材对象的取材照片数量必须在区间 $[L_{k_i},R_{k_i}]$ 内。

问是否存在满足条件的方案，如果存在输出总共可以取材的最大照片数，如果不存在输出 $-1$。

把天和取材对象都当成一个节点，建有源上下界网络流图。

$n$ 天后第 $x$ 个取材对象至少需要取材 $G_x$ 张照片可以理解为第 $x$ 个取材对象代表节点向汇点连一条上下界为 $[G_x,\inf]$ 的边。

第 $k$ 天总共可以取材 $D_k$ 张照片可以理解为源点向第 $k$ 天代表节点连一条上下界为 $[0,D_k]$ 的边。

第 $k$ 天可取材对象的取材照片数量必须在区间 $[L_{k_i},R_{k_i}]$ 内可以理解为第 $k$ 天代表节点向第 $k_i$ 个取材对象连一条上下界为 $[L_{k_i},R_{k_i}]$ 的边。

最后求一下有源汇上下界的最大流即可。

一道不错的有源汇上下界最大流练习题。

CF1200E Compress Words

哈希、KMP

给你若干个字符串，答案串初始为空。第 $i$ 步将第 $i$ 个字符串加到答案串的后面，但是尽量地去掉重复部分（即去掉一个最长的、是原答案串的后缀、也是第 $i$ 个串的前缀的字符串），求最后得到的字符串。

字符串个数不超过 $10^5$，总长不超过 $10^6$。

法一：每次需要求最长的、是原答案串的后缀、也是第 $i$ 个串的前缀的字符串。枚举这个串的长度，哈希比较即可。

法二：用 KMP 算法解决。构造一个待拼接串在前,当前拼接好的串在后的新串，求出当前拼接好的串的最后一个字符的 $\pi[i]$，即为重复的前、后缀的最长长度

一道比较基础的题。有助于哈希和 KMP 算法的理解。