2023.07.13

CF865D Buy Low Sell High

CF32E Hide-and-Seek

CF266D BerDonalds

\(O(n^3)\) 预处理出任意两个点间的最短距离 \(d(u, v)\)。

若餐厅定在边 \((u, v, w)\) 上，且与 \(u\) 点距离为 \(x\)，则最远距离为 \(\max\limits_{i = 1}^{n}(d(u, i) + x, d(v, i) + w - x)\)。取得该函数最大值时，\(d(u, i) + x = d(v, i) + w - x\)，解得 \(x = \frac{d(v, i) + w - d(u, i)}{2}\)。

然后画出关于 \(x\) 的函数图像，发现 \((u, v, w)\) 确定的情况下，最小值为最上方折线的最低点。

考虑枚举 \((u, v, w)\)，算出每个 \(\max\) 函数的最高点，把横坐标相邻的两个最高点联立解出它们之间的低谷。

实际上有些最高点还会被覆盖，所以还要用单调栈来维护一下之类的，比较麻烦。

更好的处理方法是按 \(d(u, i)\) 从大到小排序，维护使得 \(d(v, i)\) 最大的 \(i = p\)，对于之后的折线，若 \(d(v,i) > d(v, p)\)，则产生一个合法交点，且不会覆盖之前的交点。

有趣的是 \(ans\) 的小数部分要么是 \(0.0\) 要么是 \(0.5\)，所以给了 \(10^{-9}\) 次方这么严格的精度限制。

CF200A Cinema

记录 \(d(x, y)\) 表示 \((x, y)\) 周围距离为 \(d(x, y) - 1\) 的地方都被填满了。

然后暴力扫，每次查询前将 \(d(x, y)\) 用周围的点更新。

\(O(nk)\)。

CF200E Tractor College

扩欧

分类讨论

\(x = x_0 + kp, y = y_0 - kq\)。

原函数可看作关于 \(k\) 的分段一次函数，因此把端点拿出来更新答案即可。

CF922F Divisibility

结论。找到使 \(f(I) \ge k\) 的最小整数 \(p\)，\(I = (1, 2, \cdots, p)\)。

找不到就无解，找得到就如下构造方案：

从小到大尽可能选质数。

CF29E Quarrel

\(f(u1, u2) + 1 \to f(v1, v2), u1 \ne u2, v1 \ne v2\)。做到 \(O(n^4)\)。

还不会 \(O(n^3)\)。

CF125E MST Company

放到 wqs 学习笔记里。