本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-21 09:27:14

斜率优化可以优化这样的柿子：

$$f(i) = \max\limits_j f(j) - a_i a_j + b_j$$

在 $i$ 转移时，若 $j < k$ 比 $k$ 优，那么

$$ \begin{aligned} & f(j) - a_ia_j + b_j \gt f(k)-a_ia_k+b_k \ & f(j) + b_j - f(k) - b_k \gt a_i(a_j - a_k) \ & \dfrac{f(j) + b_j - f(k) - b_k}{a_j-a_k} \gt a_i \end{aligned} $$

我们将 $(a_j, f(j) + b_j)$ 看作是一个点，那么就相当于这当直线 $P_jP_k$ 的斜率大于 $a_i$ 时，$j$ 比 $k$ 优。

这也就是一个下凸壳。我们用单调队列就可以维护。

注意到如果 $a_i$ 单增，我们所切的斜率就单增，那么转移就可以做到均摊 $O(1)$。

如果要求的是最小值，那么当斜率小于 $a_i$ 时 $j$ 更优，于是我们就维护一个下凸壳，斜率是单调递减的，于是我们就要保证切的时候斜率也单调递减。

例题 P3648 [APIO2014] 序列分割

转移是显然的

$$ \begin{aligned} f(i, j) &= \max_{k=0}^{i-1} f(k, j - 1) +\sigma_{k} (\sigma_i - \sigma_k) \ & = \max f(k, j - 1) - \sigma_k^2 + \sigma_k\sigma_i \end{aligned} $$

这个转移是 $O(n)$ 的。我们考虑怎么优化。

首先滚动掉第二维然后考虑。

$\sigma$ 是非负序列的前缀和，其单增显然。于是我们可以按照上面的方式，设 $P_j(-\sigma_k, f(k) - \sigma_k^2)$。

每次用 $\sigma_i$ 去切即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-21 22:34:46

我们有一个基本转移。设 $f(i, j)$ 代表前 $i$ 个数，分了 $j$ 组的最小权值，那么

$$f(i, j) = \min_{0\le k\lt i} f(k, j - 1) + (i - k) \times \max\limits_{l=k+1}^i a_l$$

这个 $\max$ 相当唐，我们用普通的想法很难把它去掉。

考虑跑 $k$ 轮分治，用类似 CDQ 的思想，以左区间去贡献右区间。

怎么合并？分治后，柿子里头的 $\max$ 就变成了一个前后缀最大值的 $\max$。

我们设 $\text{mid}$ 前的后缀最大值为 $p$，其后面的前缀最大值为 $q$，那么 $p$ 显然单不增，$q$ 单不减。

我们可以简单分一下桃子

• $q_i \ge p_j$

$$ \begin{aligned} f(i) &= g(j) + (i-j)q_i \ &= g(j) - q_ij + iq_i \end{aligned} $$

斜率优化显然，决策点是 $(j, g(j))$。为了快速维护 $q_i \ge p_j$ 的性质，我们用双指针（这也是 CDQ 标配），$i$ 从左向右，而 $j$ 从右向左，逐渐加入决策点并维护凸包性质。加入的斜率是单调递减的，于是成为一个上凸壳。我们要在这个上凸壳上找最小值，就要求每次头的斜率小于切的斜，发现

我们加入直线的顺序是单调递减的，那么

然后以均摊 $O(1)$ 复杂度更新 $f(i)$。

• $q_i \lt p_j$

$$ \begin{aligned} f(i) &= g(j) + (i - j) p_j \ &= g(j) + ip_j - jp_j \end{aligned} $$

决策点是 $(p_j, g(j) - jp_j)$，切的

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-22 19:57:53

有一个东西：

$$ \begin{aligned} E(x) &= \sum\limits_{i=1}^V\sum\limits_{j=1}^V \dfrac {\lvert j - i + 1\rvert} {V^2}\ &= \sum\limits_{i=1}^V\bigg(\sum\limits_{j=i}^V \dfrac{j - i + 1}{V^2} + \sum\limits_{j=1}^{i-1}\dfrac{i-j+1}{V^2}\bigg)\ &=\sum\limits_{i=1}^V \dfrac 1{V^2}\bigg(\sum\limits_{j=1}^{V - i + 1} 1 + \sum\limits_{j=2}^i 1\bigg) \ &=\dfrac{1}{V^2} \sum\limits_{i=1}^V\bigg(\dfrac 1 2 (V-i+2)(V-i+1) + \dfrac{1}{2} (i+2)(i - 1)\bigg)\

\end{aligned} $$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-23 09:29:35

AB 是唐题，C 也是唐题，但是找规律找挂了。

写挂 C 心态有点挂，然后 DE 全调挂了，赛后发现做法都对。我不好说。

D

简单状压，设 $f(i, j)$ 为前 $i$ 个字符，最后 $k$ 个字符状态为 $j$ 的方案数，然后随便转移就行了，但是我没调出来。

E

单调栈。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-23 14:17:51

四边形不等式

$$a \le b \le c \le d, w(a, c) + w(b, d) \le w(a, d) + w(b, c)$$

即，交叉小于包含。

如果有方程

$$f(i) = \min\limits_{1\le j \lt i} w(j, i)$$

设在 $i$ 点的决策点为 $q(i)$，要证 $j \lt i, q(j) \le q(i)$

设有 $c \lt d$，但 $q(c) = b \gt q(d) = a$，那么首先有

$$a \lt b \le c \lt d$$

于是由最优

$$w(a, c) \gt w(b, c), w(b, d) \gt w(a, d)$$

两式相加得

$$w(a, c) + w(b, d) \gt w(a, d) + w(b, c)$$

但是这与四边形不等式矛盾。

简单证明 P3195 玩具装箱有决策单调性

$$w(i, j) = (s_i - s_j - L)^2 = O((s_i - s_j)^2)$$

其中 $s_i$ 是单调增的，那么对 $i \lt j$，有

$$w(i, j - 1) + w(i + 1, j) \lt w(i, j) + w(i + 1, j - 1)$$

也即

$$(s_i-s_{j-1})^2 + (s_{i+1}-s_j)^2 \lt (s_i - s_j)^2 + (s_{i+1}-s_{j-1})^2$$

$$(s_i-s_{j-1}+s_i - s_j)(s_i-s_{j-1}-s_i+s_j) \lt (s_{i+1}-s_{j-1}+s_{i+1}-s_j)(s_{i+1}-s_{j-1}-s_{i+1}+s_j)$$

$$(2s_i - s_j - s_{j-1})(s_j - s_{j-1}) \lt (2s_{i+1}-s_j - s_{j-1})(s_j - s_{j-1})$$

由于 $s_j - s_{j-1} \gt 0$，那么

$$2s_i - s_j - s_{j-1}\lt s_{i+1}-s_j - s_{j-1}$$

也就是 $s_i \lt s_{i+1}$，由单调性得证。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-24 19:33:07

有的题，横坐标和所切的斜率均不单调，比如 P4655 Building Bridges，这时候我们可以用 CDQ 分治来把朴素的 $O(n^2)$ 优化到 $O(n\log n)$。

具体方法比较简单。CDQ 分治所考虑的核心就是左区间对右区间的贡献。怎么转化成为朴素的斜率优化 DP 呢？左边区间的横坐标要单调，右边区间所切的斜率要单调。

这样，我们就先按照切的斜率排序，然后计算左边对右边的贡献，然后按照横坐标排序。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-29 19:03:17

首先奇耻大辱。赛时以为 Unrated 就不要紧，帮人调码交了两发，然后棕了。确实该罚，以后牢记。

然后来看题。

先不管操作一二。对于操作三，要求我们把所有糖果分成 $k$ 份，所要统计的是重复出现的糖果的数量，别的没有要求。

如果每人每种糖果先分一颗，这时候每种糖果数量减去 $k$，接下来还没分完的糖果每颗都会带来 $1$ 的贡献。

换句话说，我们就是对于每次询问的 $k$，统计每种糖果超出 $k$ 部分的总和。也就是说，大于 $k$ 的数的总和，减去大于 $k$ 的数的数量乘上 $k$ 就是答案。

这个操作用什么可以完成？平衡树，树状数组，权值线段树都可以做到。赛时无脑上了平衡树，但是实际上因为值域很小，所以后两者不需要离散化就可以。

总的来说，我们的做法就是：用桶维护每种糖果的数量，然后用上面三种数据结构之一维护；加减可以先删再插入，查询就查大于某数的数的和以及数量。

这里是代码。

平衡树有几个点注意：

• 需要加哨兵，否则需要注意边界情况；

• 查大于某数的数的数量，可以找后继然后用根减去左子树。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-30 19:40:03

知道两个做法。

第一个做法好想，我们设 $g(x)$ 表示 $[1, x]$ 中最大的翻转数，$g$ 单增显然，并且可以构造出来，类似数位 DP。然后二分就可了。

第二个做法，把原问题转化为找最小的 $k$ 使得 $f(k) \gt n$，答案就是 $k - 1$。这个好构造。我们考虑 $f(k)$ 一定是某一位比 $n$ 恰好大一，否则不优，然后这一位下面的所有数都是零；同时，最后一位必须不是零。

我们枚举这一位，然后算一下就可以了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-02 21:35:41

A 不表

B

给定一个序列，可以用 $k + 1$ 的代价给一个长度为 $k$ 的子序列加上一；求最小的使得序列不降的代价。

考虑所需要修改的量是静态的，因此可以把每个点上需要做的修改都拿下来，然后排序贪心。

赛时写的有点太保守了，调了一会儿。

C

回家再写。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-13 15:18:30

不算难。难点在于 CCF 独有的鹅心大分桃。

答案的单调性是显然的：第 $x$ 天能完成，$x + 1$ 天也定能完成，于是二分一个 $m$ 作为答案，并转化为判定问题。

每棵树每天的增量是不小于一的，但是正由于这个一的下界，我们需要一个有点恶心的分桃。

忽略角标，我们设 $g(x)$ 表示从 $1$ 开始种，种到 $x$ 时刻的总高度，设 $z = \max \{0, \lceil\dfrac{1-b}c\rceil\}$ 是使得增量为一的点，定义域非负。

当 $x \lt z$ 时显然有 $g(x)= bx + \dfrac 1 2 cx(x + 1)$；

当 $x \ge z$ 时：

• $c\gt 0$，$g(x) = z + b(x - z) + \dfrac 1 2cx(x+1)-\dfrac 1 2 cz(z + 1)$

• $c = 0$，$g(x) = bx$

• $c \lt 0$，$g(x) = bz + \dfrac 1 2 cz(z + 1)+(x-z+1)$

很难说这种傻逼线性柿子有什么意义，但凡换成随便其它一个不需要分桃的单调函数都行。但是出了就得做。。

$g(x)$ 单调性显然，我们需要二分找到最大的 $t$ 使得 $g(t) \ge a$ 且 $g(t+1)\lt a$，即种这棵树的最晚入口。$t\le m$ 是显然的，不满足直接跳出。

找到所有的 $t$ 后，问题就转化为了：对每个点，我们为其分配一个 $x$ 使得 $1\le x \le t$ 且 $x_{\text{fa}_i}\lt x_i$，且 $x$ 不重。

那么我们按照 $t$ 排序，优先满足 $t$ 小的即可。

复杂度是两支 $\log$ 的，对应两个二分。