搬运自 10 月 22 日讲课

上回书说到，failure function的3个应用......

\1. 最短的 $S$ 使 $A=S^d$，称作 $root(A)$

引理：当 $n-\pi_n|n$ 时，$|root(A)|=n-\pi_n$ 否则 $root(A)=A$（一共分成 $\frac{n}{n-\pi_n}$ 段，推得每段相等）

Fallure Function $\pi_i=max\{j<i|s_{1\dots j}是s_{1\dots i}后缀\}$

引理 $S=BB'=B'B(B,B'\neq \cancel{o})$，那么 $root(S)\neq S$

引理 $root(A)<n$ → $\pi_n\leq n-|root(A)|$

（反证，假设 $\pi_n>n-|root(A)|$ 则 $|root(A)|>n-\pi_n$ 得到与定义矛盾）

//假如 $(S,d)$ 满足 $S^d=A$

//$A$ 中长为 $n-|S|$ 的前后缀相等，$\pi_n\geq n-|S|$ 特别地，$\pi_n\geq n-|root(A)|$

\2. 给定串 $S$（$10^5$ 级别），求每个前缀 $S_{1...i}$ 在 $S$ 中出现次数。（枚举出现位置末尾 $j$，则问题变为 $S_{1\dots i}$ 是 $S_{1\dots j}$ 后缀，辅助 $\pi_j$ 计算 $\pi$ 树子树和即可）

\3. 求本质不同字串个数

法一：后缀数组/自动机（？）

法二（$n^2$）：求 $S$ 转移到 $S'=S+c$ 增加的贡献

01-分数规划

若干物品，每个物体有权值（价值和代价） $a_i$、$b_i$（$b_i>0$），最优比率即合法选择($X=(x1\dots x_{|X|})$ 属于合法方案集合 $S$)中 $\frac{\sum a}{\sum b}$ 最小/大。

无限制条件或某些特殊限制条件 → 贪心

贪心无法保证最优 → 分数规划（如最小/大比例生成树）

二分答案，将最值问题转化为可行问题：是否存在一组解，使得比率大于等于/小于等于 $\lambda$？

以大于等于为例，$\frac{\sum a}{\sum b}\geq \lambda$ 即 $(\sum a)-\lambda(\sum b)\geq 0$

每次求 $\lambda$ 的可行性时赋予每个物体一个新权重 $c_i=a_i-\lambda b_i$，可行即存在合法方案，使得选中物体的权重和 $\sum c\geq 0$。

例：最小比率环

按上述处理后，每次二分用 SPFA 查找是否存在 $c_i$ 组成的正/负环即可。

例：最小乘积变种（如生成树，匹配），即 $(\sum a)(\sum b)$ 最小

将每个方案对应点 $(\sum a,\sum b)$

第一步，找到离 $x$ 和 $y$ 轴最近的点（使权值 $c_i$ 分别等于 $a_i$ 和 $b_i$），设为 $A$ 和 $B$

第二步，找到在 $AB$ 左下方且距离 $AB$ 最远的点 $C$（在左下方，则显然 $C$ 比 $A$ 和 $B$ 优）

因 $AB$ 固定，距离最远即 $S_{\Delta ABC}=-\frac{\vec{AB}\times\vec{AC}}{2}$ 最大。

又 $\vec{AB}\times\vec{AC}=y_C(x_B-x_A)+x_C(y_A-y_B)-y_A(x_B-x_A)+x_A(y_B-y_A)$

赋予新权值 $c_i=(y_A-y_B)a_i+(x_B-x_A)b_i$ 求最优解。

第三步，若递归中找不到在线段左下角的解 $C$ 则返回，否则将线段 $AB$ 拆分为子线段 $AC$ 和 $CB$，对两边递归求解。

最终答案即递归过程中出现的合法方案中的最优解。

---

例题：

恰好选 $k$ 个物品 POJ2976

最优比率环 POJ3621&洛谷 P2868 / 洛谷 P3199

最小比率生成树 洛谷 P4951

最小乘积匹配 P3236

最小乘积生成树 P5540