标签：总结 20230714 frac sum 练习 y1 x2 x3 x1

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)\) 判断选哪些就可以了。

标签：总结,20230714,frac,sum,练习,y1,x2,x3,x1
From： https://www.cnblogs.com/dks-and-xiao-yu/p/17554010.html