LOJ3686 / JOISC 2022 DAY1 京都观光
考虑从 \((x1,y1)\) 只转一次弯到 \((x2,y2)\)。先向南走当且仅当：
\[\boxed{\frac{a_{x1}-a_{x2}}{x1-x2}<\frac{b_{y1}-b_{y2}}{y1-y2}}
\]
很容易想到斜率相关。但是如果只是对比两行，因为有列的条件参与，无法判断某一行是否一定不会被走过，于是分析三行。
设现在有三行（\(x1,x2,x3\)）两列（\(y1,y2\)），\(x2\) 不会被走过当且仅当：
\[\begin{aligned}
&\frac{a_{x1}-a_{x2}}{x1-x2}>\frac{b_{y1}-b_{y2}}{y1-y2}\\
&\;\;\;\;\;\;\;\;\;\;\;\;\;\;and\\
&\frac{a_{x2}-a_{x3}}{x2-x3}<\frac{b_{y1}-b_{y2}}{y1-y2}\\
\Longrightarrow &\frac{a_{x1}-a_{x2}}{x1-x2}>\frac{a_{x2}-a_{x3}}{x2-x3}
\end{aligned}
\]
故对 \((i,a_i)\) 构造一个斜率递增的凸包，列同理。
求答案每走一段就依据开头式子决定下一步。
LOJ3696 / JOISC 2022 DAY4 复兴计划
题意即要求绝对值最小生成树。
考虑绝对值的性质，随着 \(X_i\) 往后推，一条边一旦被替代就不会再被用到。故一条边会对 \(X\) 在一个区间的询问产生贡献。如果将每条边的影响区间算出问题就可以变得很简单。
考虑从小到大加边，如果边的两端不连通就直接加，否则暴力找路径上边权最小的边并替代。
P4110 / HEOI2015 小L的白日梦
转化一下题意即最小化 \(\sum_{i=2}^k(1-a_{i-1})a_i\) 的。
由于 \(\sum_{i=1}^ka_i\) 为定值。可以转为最大化 \(\sum_{i=1}^ka_i-\sum_{i=2}^k(1-a_{i-1})a_i=a_1+\sum_{i=1}^ka_{i-1}a_i\)。根据排序不等式，\(a\) 降序时最优。
将 \(n\) 的数排序后选的一定是一段前缀和一段后缀，具体证明。
每个测试点 \(O(n)\) 判断选哪些就可以了。