好久以前的笔记拿过来存一下。

保序回归问题

参考2018年集训队论文《浅谈保序回归问题》

问题描述

注意这里的偏序关系是非严格偏序关系。
给定正整数 $p$, 一张有向无环图 $G$, 以及代价函数 $(y_i, w_i) (\forall i, w_i > 0)$。如果在 $G$ 中有 $v_i \rightarrow v_j$ 的有向路径， 那么存在偏序关系 $v_i \leq v_j$ 。求点值序列 $f$, 满足 $\forall v_i \leq v_j (i, j \in [1, n])$ , 有 $f_i \leq f_j$, 最小化下列回归代价。
$$\sum_{i = 1}w_i|f_i - y_i|^p, 1 \leq p < \infty$$
$$\max_{i = 1}w_i|f_i - y_i|, p = \infty$$
对于相同的 $p$, 称作 $L_p$ 问题。

一些约定

  • 将序列 $z$ 中不超过 $a$ 的元素变为 $a$ ，不小于 $b$ 的元素变为 $b$ 称为序列 $z$ 向集合
    $S = {a, b}$ 取整。
  • 点集 $U$ 的 $L_p$ 均值为满足 $\sum_{v_i \in U}w_i|y_i - k|^p(1 \leq p < \infty)$ 或 $\max_{i = 1}w_i|k - y_i|, p = \infty$ 最小的 $k$ 。

特殊情况下的算法

一种贪心算法

Approximation 加强版

给定正整数序列 $y, w$, 求一个单调不减的实数序列 $f$， 最小化 $\sum_{i = 1}^nw_i(f_i - y_i)^2$。
$n \leq 2\times 10^5$ 。
Problem Link

可以发现这种情况下可以直接计算其 $L_2$ 均值， 其 $L_2$ 均值为 $\frac{\sum_{v_i\in U}w_iy_i}{\sum_{v_i\in U}w_i}$ 。直接求一阶导数即可证明。
还有一个性质是， 如果 $y_{i + 1} > y_i$ ， 那么 $f_i = f_{i + 1}$ 。

那么有这样一个基于贪心的算法。

  • 考虑维护一个栈， 栈中元素为一个三元组 $(S, y, w)$ 。其中 $S$ 是一个集合。
  • 从左往右扫描， 每次加入元素 $({i}, y_i, w_i)$ 。 如果存在某个时刻使得栈顶的 $y$ 小于栈顶下面那个数的 $y$， 弹出栈顶， 根据之前的 $f$ 相等的结论， 合并之前弹出的栈顶和当前的栈顶即可。
  • 具体来说， 令新元素为 $(S_1 \cup S_2, \frac{y_1w_1+y_2w_2}{w_1+w_2}, w_1 + w_2)$ 。
  • 最后每个元素所属集合对应得 $y$ 就是答案了。
  • 基于扰动容易看出答案正确。

维护折线的算法

由于在保序回归中折线算法可以被整体二分代替， 不为讨论。

一般问题的算法

新问题的构造

在 $L_p$ 基础上加入另一个限制，得到 $S = (a,b)(a<b)$ 问题：满足原问题所有限制的同时，还满足 $a\leq f_i \leq b$ ，最小化回归代价。

$p = 1$ 的情况

讨论

有一个性质， 最优解的所有 $f$ 都在 ${y_i}$ 中。
有一个引理， 在 $L_1$ 问题中， 如果

  • 任意 $y_i$ 不在区间 $(a, b)$ 中
  • 存在一个最优解序列 $z$ 满足 $z_i$ 均不在 $(a,b)$ 中。
  • $z^S$ 为 $S$ 问题的一个最优解。

那么一定存在一组最优解 $z$, 使得 $z$ 向 $S$ 取整可以得到 $z^S$ 。
那么有下面这样的整体二分做法。
考虑整体二分 $z^S$ 的取值， 二分到 $y_l, y_r$ 的时候， 计算 $S = (y_{mid}, y_{mid + 1})$ 的最优解， 然后根据每个 $z$ 选择了 $y_{mid}$ 还是 $y_{mid + 1}$ 就可以确定其取值在 $[y_l, y_{mid}]$ 中还是在 $[y_{mid + 1}, y_r]$ 中。然后递归下去就好。
至于如何求最优解，可以发现这就是一个 $01$ 选择的问题， $f_i \leq f_j$ 相当于 $f_i$ 选 $1$ 的时候， $f_j$ 必须选 $1$ , 使用网络流做最大权闭合子图即可。

ExtremeSpanningTrees

Problem Link
给定一张 $n$ 个点 $m$ 条边的无向连通图 $G = (V, E)$ 和边集 $E1, E2(E1, E2 ∈ E)$ ，每条边有初始的权值 $d_i$ ，每次操作可以把一条边的权值加 $1$ 或减 $1$ ，求通过最少多少次操作可以满足：

  • 边集 $E1$ 组成的子图是整张图的最小生成树
  • 边集 $E2$ 组成的子图是整张图的最大生成树

$n ≤ 50, m ≤ 1000$

要求是最小生成树实际上就是要求树上的边小于等于环上的边， 最大生成树类似。把所有的限制拿出来。
据说虽然论文里面要求是 $DAG$, 但是不是 $DAG$ 也是可以直接做的， 据说不影响结论证明。
那么直接按照论文搞就好了， 复杂度 $O(nm^3\log_2m)$

$1 < p < \infty$ 的情况

讨论

引理 ： 可以证明任意集合 $U$ 的 $L_p$ 均值唯一，且代价函数在 $<L_p$ 时递减， $>L_p$ 时递增。
证明可以考虑对函数求导以后， 只有一个零点。
然后还有这样一个引理 ：

若 $solve(U, a, b)$ 的一组最优解为 $z’$ ， 且满足 $z’ \notin (a, b), \forall i \in U$ 。则
存在 $solve(U, l, r)$ 的一组最优解 $z$， 使得 $z_i \leq a$ 当且仅当 $z_i’ = a$ 。

求$solve(U, mid, mid + \epsilon)$的过程与 $L_1$ 相同， 节点 $i$ 的权值为 $w_i[(b - y_i) ^ p - (a - y_i)^p]$ 。取反以后是最大权闭合子图。
那么有这个引理的话， 可以用 $solve(U, mid, mid + \epsilon)$ 的结果确定 $z$ 的范围然后整体二分。
考虑一定存在足够小的 $\epsilon$ 可以区分所有点， 考虑把所有点的权值除以 $\epsilon$, 那么权值就是 $w_i(mid - y_i)^p$ 关于 $mid$ 的导数。当 $p = 2$ 时， 权值为 $2w_i(mid - y_i)$ 。

[省选联考 2020 A 卷] 魔法商店

Problem Link

把线性基里面 $A$ 可以替换 $B$ 看成一条边， 可以建立一个DAG。
然后就是跑跑跑。
记录实现细节。

  • 由于要求是整数， 所以在 $R - L = 1$ 的时候特殊处理。
  • 分治的时候， 每个点的权值是 $- 2w_i(mid - y_i)$ 这样就是最大权闭合子图。
  • 和源点连接的是在大的那一边。也就是最后一次跑到的是在大的那一边。因为没割掉才算选取。
  • 特判 $R - L = 1$ 的时候， 代价差也就是每个点的权值是 $- (L + 1 - y_i)^2 + (L - y_i) ^ 2 = - 2(y_i - L) - 1$ 。也就是小减大。