IOI2021 集训队作业（三）
有生之年。
297. Surveillance
对于一个长为 \(n\) 的环，给定环上 \(m\) 个区间，使用最少的区间覆盖整个环。
时间复杂度：\(O(m + n \log n)\) 。
题解
如果是链的话，容易得到一个贪心做法。
把环剖成一个长为 \(2n\) 的链，问题转换为用最少的区间覆盖长为 \(n\) 的任意一段。
然后沿用贪心做法，利用倍增，设 \(f(k,i)\) 表示从 \([1, i]\) 中任意选一个起点，贪心地使用 \(2^k\) 个区间能到达的终点位置，有
\[ f(k, i) = f(k - 1, f(k - 1, i)) \]
预处理 \(f\) 数组后枚举起点就可以 \(O(\log n)\) 得到该起点的答案。
191. Frightful Formula
给出 \(f(1,i)\) 和 \(f(i,1)\) ，对于 \(i > 1, j > 1\) 定义 \(f(i,j) = a f(i,j-1) + b f(i-1,j) + c\) ，求 \(f(n,n)\) 。
时间复杂度：\(O(n)\) 。
题解
令
\[ f(i,j) = g(i,j) + h(i,j) \] \[ g(i,j) = a g(i,j-1) + b g(i-1,j) + c \] \[ h(i,j) = a h(i,j-1) + b h(i-1,j) \]
如果 \(g(i,j)\) 很好算，那么我们可以由 \(h(1,i)\) 和 \(h(i,1)\) 简单地算出 \(h(n,n)\) ，进而得到 \(f(n,n)\) 的值。
那么问题就是如何构造一个好算的 \(g\) ，容易想到：
- \(a + b \neq 1\) 时，\(g(i, j) = \dfrac{c}{1 - a - b}\) 。
- \(a + b = 1\) 时，\(g(i, j) = c (i + j)\) 。