一些最值问题

Published: by Creative Commons Licence

  • Tags:

最小不能生成元素

题目1：给定$n$个面值为$a_1,\ldots,a_n$的硬币，其中$1\leq a_i\leq 10^9$。现在要求找到最小的非负价格$p$，满足不存在一个硬币子集，它们的和为$p$。

提供一个问题。

我们可以用动态规划来计算，但是这样会导致状态数爆炸。

我们可以重新理解这个问题。我们驾车在$x$轴上行驶，初始的时候我们位于$0$处，并向正方向行驶。对于硬币$a_i$，我们可以理解是一桶位于$a_i-1$处的汽油，它可以让我们额外行驶$a_i$距离。问最远我们可以将车停在哪里（我们的实际答案还需要额外加1）。

这当然是一个贪心问题，我们可以$O(n)$求解。

题目2：给定$n$个面值为$a_1,\ldots,a_n$的硬币，其中$1\leq a_i\leq 10^9$。之后给定$q$个请求，请求分两类：

  1. 每个请求给定一个区间$l\leq r$，要求仅考虑硬币$a_l,a_{l+1},\ldots,a_r$，要求找到最小的非负价格$p$，满足不存在一个硬币子集，它们的和为$p$。
  2. 将第$i$个硬币的面额修改为$x$，其中$1\leq x\leq 10^9$。

其中$1\leq n,q\leq 10^5$。

提供一道题目。

借助题目1的思路，我们可以把问题看成加油站问题。

由于涉及区间查询和单点修改，我们果断将结构丢到线段树上维护。每个线段树结点维护区间中的所有汽油信息。每个汽油有两个属性，所在位置和油量。

之后我们考虑如何实现上推操作（合并两个孩子的状态）。可以发现上推会导致顶点的汽油数爆炸，越往上单点维护的汽油数越多，上推难度也越大。但是可以注意到如果有一桶汽油，左边的所有汽油油量总和超过汽油所在的位置，那么这个汽油的油量可以直接加入到它左边的汽油中去，并且删除右边汽油。因此一个结点实际维护的汽油，一定满足左边的油量前缀和小于这个汽油的坐标，此时我们每次在尾部增加一桶汽油，那么总的油量会至少翻倍，而汽油的坐标不超过$10^9$，因此最多一个结点需要维护$\log_210^9$的汽油，约$30$个元素。

因此总的时间复杂度为$O((n+q)\log_2n\log_210^9)$。

几何

到中心最小距离问题

题目1：给定$n$个二维平面点$(x_1,y_1),\ldots,(x_n,y_n)$，要求找到一个中心$(a,b)$，满足所有点到中心的曼哈顿距离之和最小。

由于是曼哈顿距离，所有不同的维度可以分别计算。

现在的问题变成了有$n$个数值$x_1,\ldots,x_n$，找一个中心值$a$，满足$\sum_{i=1}^n|x_i-a|$最小。这里我们直接取$a$为$x$的中间数即可。

题目2：在一个无穷大的棋盘上，给定$n$个网格点$(x_1,y_1),\ldots,(x_n,y_n)$，这些网格内放置了棋子。之后我们要将这些网格点移到到一块，即所有棋子占用的行恰好为连续的$n$行，而所有棋子占据的列恰好是连续的$n$列。每次移动棋子，可以将其移动到有公共边的网格中。问最少需要的移动次数。

这里我们可以把行和列拆开来计算。现在的问题是存在$n$个整数$x_1,\ldots,x_n$，很显然在移动的时候不会改变这些整数的顺序。要求找一个整数$a$（与$x_1-1$对齐），满足$\sum_{i=1}^n|x_i-(a+i)|$最小。我们修正一下公式可以发现为$\sum_{i=1}^n|(x_i-i)-a|$，因此$a$实际上是$x_1-1,x_2-2,\ldots,x_n-n$的中位数。

提供一道题目SRM 795 div1的第二题。

题目3：给定$n$个二维平面点$(x_1,y_1),\ldots,(x_n,y_n)$，要求找到一个中心$(a,b)$，满足所有点到中心的2范数距离之和$J(a,b)=\sum_{i=1}^n(a-x_i)^2+(b-y_i)^2$最小。

考虑偏导数：

\[\frac{\partial}{\partial a}J(a,b)=2\sum_{i=1}^n(a-x_i)\]

由于极值点在偏导数为$0$的时候取到，因此有：

\[\begin{aligned} &2\sum_{i=1}^n(a-x_i)=0\\ \Rightarrow &na=\sum_{i=1}^nx_i\\ \Rightarrow &a=\frac{1}{n}\sum_{i=1}^nx_i \end{aligned}\]

同样有$b=\sum_{i=1}^ny_i$。

题目4：给定$n$个二维平面点$(x_1,y_1),\ldots,(x_n,y_n)$，要求找到一个中心$(a,b)$，满足所有点到中心的欧几里德距离之和$J(a,b)=\sum_{i=1}^n\sqrt{(a-x_i)^2+(b-y_i)^2}$最小。

可以证明函数$J$是凸函数，因此可以上三分套三分，梯度下降，模拟退火啥的。

凸函数的证明。

一维点的匹配问题

题目1：给定序列$a_1,\ldots,a_n$以及$b_1,\ldots b_m$。要求找到一个1到m的置换$p_1,\ldots,p_m$。记置换的权重为$\sum_{i=1}^n |a_i-b_{p_i}|$。要求找到置换的权重的最小值。其中$1\leq n\leq m\leq 5000$。

不妨认为$a$和$b$序列都已经预先排好序了，那么最优解的情况下一定有$p_1<p_2<\ldots<p_n$。

因此我们可以记$dp(i,j)$表示从$1,\ldots,i$中选择$j$个作为$p_1,\ldots,p_j$，带来的最小权重。那么每个状态只需要考虑两种转移即可。总的时间复杂度为$O(nm+n\log_2n+m\log_2m)$。

题目2：给定序列$a_1,\ldots,a_n$以及$b_1,\ldots b_m$。要求找到一个1到m的置换$p_1,\ldots,p_m$。记置换的权重为$\sum_{i=1}^n |a_i-b_{p_i}|$。要求找到置换的权重的最大值。其中$1\leq n\leq m\leq 10^6$。

不妨认为$a$和$b$序列都已经预先排好序了。

考虑$a_i$和$a_{i+1}$，它们匹配的值为$b_{p_i}$和$b_{p_{i+1}}$。很显然如果$a_i\geq b_{p_i}$且$a_{i+1}\leq b_{p_{i+1}}$，那么我们交换$p_i$和$p_{i+1}$可以得到更大的一个权重。因此我们可以得出$a_i\geq b_{p_i}\Rightarrow a_{i+1}\geq b_{p_{i+1}}$。

根据上面的结论，我们可以找到一个点$k$，对于$i\geq k$，都有$a_i\geq b_{p_i}$，同时对于$i<k$，都有$a_i\leq b_{p_i}$。此时答案为$\sum_{i=1}^{k-1}(b_{p_i}-a_i)+\sum_{i=k}^n(a_i-b_{p_i})$。这时候我们要最大化$p_1,\ldots,p_{k-1}$，同时最小化$p_k,\ldots,p_n$，可以发现两者可以同时满足，此时若$i<k$，则$p_i=m+1-i$，若$i\geq k$，则$p_i=i-k+1$。

通过预处理前缀和，我们可以$O(n+m)$遍历所有可能的$k$。总的时间复杂度为$O(n\log_2n+m\log_2m)$。

概率和期望

概率

题目1：给定$n$个独立的随机变量$x_1,\ldots,x_n$，其中第$i$个随机变量从$1$到$t_i$中均匀随机取值，其中$m=\sum_{i=1}^nt_i$。要求对于$1\leq i\leq m$，求出$\max_{j=1}^nx_j=i$的概率。其中$1\leq n,m\leq 10^6$。

一种直接的想法是用DP的方式，但是这样会导致时间复杂度变成$O(nm)$。

一般遇到min-max概率或期望计算，都需要借助前缀和的技术。这里我们记$f(i)$表示最大值不超过$i$的概率。可以发现$f(i)=\prod_{t_j\geq i}\frac{i}{t_j}$。之后通过差分就可以得到$P(\max_{j=1}^nx_j=i)=f(i)-f(i-1)$。

上面过程的时间复杂度为$O(n\log_2n+m)$。

收集问题

题目1：一个游戏总共有$n$个奖章。每完成一局游戏，会固定得到一个奖章，其中得到的是第$i$个奖章的概率是$p_i$，其中$\sum_{i=1}^np_i=1$且$p_i>0$。要求计算搜集到所有奖章的期望游戏局数。其中$1\leq n\leq 25$。

这里我们可以使用min-max容斥。记$x_i$表示第$i$个奖章的获得时间。则

\[\begin{aligned} E[\max_{i=1}^nx_i]&=E[\sum_{I\subseteq N}(-1)^{|I|-1}\min_{i\in I}x_i]\\ &=\sum_{I\subseteq N}(-1)^{|I|-1}E[\min_{i\in I}x_i] \end{aligned}\]

其中$\min_{i\in I}x_i$表示多个奖章中最早获得奖章的获得时间。这等价于抛掷一枚不均匀硬币，第一次出现正面的时间，其等于$1/p$，其中$p$是出现正面的概率。因此化简可以得到：

\[\begin{aligned} \sum_{I\subseteq N}(-1)^{|I|-1}E[\min_{i\in I}x_i]&=\sum_{I\subseteq N}(-1)^{|I|-1}\frac{1}{\sum_{i\in I}p_i} \end{aligned}\]

上面的公式可以$O(2^n)$解决。

字典序

字符串合并

题目1：给定两个字符串$A,B$。以及一个空字符串$C$。之后我们可以不断的从$A,B$中选择一个非空字符串，将其头部元素删除并加入到$C$尾部。重复这个流程，直到字符串$A,B$都为空。要让$C$的字典序最大。

提供一道题目。

首先说做法。每次比较$A$和$B$，将其中字典序较大的字符串的头部元素删除追加到我们的$C$中即可。这个过程，可以直接通过暴力比较$O(nm)$，或者一些复杂的后缀处理技术，比如后缀数组来提速，时间复杂度为$O(n+m)$。

下面说明一下这样做为什么是对的。

首先我们可以在两个字符串尾部都加上一个代表无穷小的哨兵字符，这样就可以避免讨论两个字符串一者是另外一者的前缀这种情况（但是两个字符串还是可能相同的）。很显然最后构建的字符串的尾部两个元素就是我们加入的哨兵字符。

记$inv(A_i)$表示$A_i$在最终结果（$C$）中的下标。

如果$A=B$，很显然从哪个字符串头部删除都不会影响结果。下面认为$A\gt B$。我们记$t$为第一个不同的位置，即$A_1=B_1,\ldots,A_{t-1}=B_{t-1}$，但是$A_t\gt B_t$。

首先我们证明如果最终结果最优，则$A_t$一定出现在$B_t$之前。如果不是，记$L=inv(B_t)$，此时$B_t$在前。则对于所有$1\leq i\leq t$，我们将最终结果中$A_i$与$B_i$位置互换。此时可能发现换位后$B_i$出现在$B_{t+1}$之后的情况，我们可以将所有$B$占据的位置上的元素按照它们的下标重新排个序即可。可以发现修改后$C$的长度为$L-1$的前缀是不会改变的，而第$L$个元素从$B_t$变成了$A_t$，增大了，这说明了我们最终结果并不是最优的，与前提相悖。因此$inv(A_t)\lt inv(B_t)$。

之后我们证明至少存在一种最优结果，满足$inv(A_1)=1$，即$A$头部元素放在$C$的最前。证明方法也是构造性的，从任意一个最优解出发，如果此时最优解的头部元素是$B_1$而不是$A_1$，我们记$j$表示最大的下标，满足$inv(B_j)\lt inv(A_t)$。之后我们将$A_1$与$B_1$的位置互换。可以发现我们的最优解值是不会变的。但是这时候可能出现冲突，即$inv(B_1)\gt inv(B_2)$，$B_1$被交换到$B_2$之后了。我们可以继续让$B_2$与$A_2$交换位置。重复上面这个流程直到结束。很显然这个流程是会结束的，因为$B_j$不管是否交换都不会出现在$B_{j+1}$之后。而这个过程由于不会改变解的值，因此修改后的解依旧最优，且此时$inv(A_1)=1$。

因此根据上面的结果就可以放心大胆的使用贪心算法，因为无论如何都可以通过后续的手段将结果最优化。

题目2：给定$n$个字符串$s_1,\ldots,s_n$，要求将它们重新排列拼接，要求拼接得到的字符串字典序最大。

提供一道题目。

考虑两个结果中相邻的字符串$A,B$。如果字符串$A$排在$B$之前，那么一定有$AB\leq BA$，否则交换后可以得到更优的结果。

而考虑到$AB\leq BA$等价于$A^+\leq B^+$，因此保证偏序关系的成立，因此我们可以使用比较算法。

时间复杂度为$O(nm\log_2n)$。

带关联最大和问题

题目1：给定一个序列$a_1,\ldots,a_n$，要求对于$k=1,\ldots,n$，计算仅从序列中取$k$个元素$a_{I_1},a_{I_2},\ldots,a_{I_k}$，满足$I_1<I_2<\ldots <I_k$，使得式子$\sum_{i=1}^ki\cdot a_{I_i}$最大，输出这个和。

提供一道题目。

记$V(i)$表示仅取$i$个元素的最优集合，官方题解已经证明了$V(i+1)$可以通过向$V(i)$加入一个新元素得到。因此我们只需要每一步加入贡献最大的元素。

考虑已经加入$k$个元素，现在考虑元素$i$的贡献，它的贡献为$(p+1)a_i+\mathrm{suf}$，其中$p$表示$V(k)$中下标小于$i$的元素数量，而$\mathrm{suf}$表示下标大于$i$的元素和。

所以显然问题变成了有$n$条直线，第$i$条直线的公式为$a_ix_i+b_i$（这个$a_i$与题目中的$a_i$已经没有关系了，表示斜率），初始的时候$x_i=1$。要求支持三种操作：

  1. 删除一条直线。
  2. 将一段区间中的直线的$x$属性增大$1$
  3. 将一段区间中的直线的$b$属性增大$t$
  4. 查询当前贡献最大的直线。

这个用线段树是解决不了的，需要使用分块。一般分块结合排序的时间复杂度是$O(n\sqrt{n}\log_2n)$。但是由于属性$a$不会修改，因此我们实际上可以预先对$a$属性排序，相同$b$属性的我们取较大者即可。这样时间复杂度为$O(n\sqrt{n})$。

图论

拓扑序

题目1：给定一个包含$n$个顶点的树，记$G_v$表示将顶点$v$作为根，将所有边的改变为从父亲指向孩子的有向边。记$Topo(G_v)$表示这个有向图的总拓扑序的数目。要求找到$\max_{1\leq i\leq n}Topo(G_i)$。

提供一道题目。

考虑存在边$(u,v)$，$Topo(G_u)$和$Topo(G_v)$的区别。

记$f(G_u,v)$表示以$u$为根时，删除$v$为根的子树后的拓扑序，而$s(G_u,v)$表示以$u$为根，以$v$为根的子树的大小。可以发现$Topo(G_u)=f(G_u,v)\times f(G_v,u)\times {n-1\choose s(G_u,v)}$。同理有$Topo(G_v)=f(G_v,u)\times f(G_u,v)\times {n-1\choose s(G_v,u)}$。此时有$\frac{Topo(G_u)}{Topo(G_v)}=\frac{s(G_v,u)}{s(G_u,v)}$。

通过上面式子可以发现，如果顶点$u$下有一个子树大小超过$\frac{n}{2}$，则这个顶点一定不是最优的。因此最优的点仅可能是重心，重心如果有两个，则任意一个重心都是最优的。我们只需要找到重心，之后算一下拓扑序就可以了。

最长公共子序列问题

题目1：给定长度为$n$的序列$a$和长度为$m$的序列$b$，要求找到它们的最长公共子序列的长度。其中$1\leq n\leq 1000$，$1\leq m\leq 10^6$。

最简单的LCS算法是定义$dp(i,j)$，表示$a$长度为$i$的前缀和$b$长度为$j$的前缀的最长公共子序列的长度。但是这样做的时间复杂度是$O(nm)$，太慢了。

由于LCS的长度不会超过$\min(n,m)$，因此我们定义$dp(i,j)$为$a$的长度为$i$的前缀和$b$的某个前缀拥有长度为$j$的公共子序列，$b$的前缀的最小长度。这样我们的状态仅$n^2$个。但是这样转移需要快速解决这样一个问题：记$f(i,x)$表示$b$中最小的下标$j$，满足$j>i$，且$b_j=x$。这个问题可以通过持久化技术解决，这样我们的每次dp转移的时间复杂度为$O(\log_2m)$，总的时间复杂度为$O(n^2\log_2m)$。

最小总和

树上最小总和

题目1：给定$n$个顶点的树，每个顶点$i$有一个权值$w_i$。现在在其中$k$个顶点$a_1,a_2,\ldots,a_k$上各有一个棋子，要求将这些棋子移动到$b_1,b_2,\ldots,b_n$上，其中在$a_i$的棋子需要移动到$b_i$，每次你只能选择一个棋子向某个邻近的顶点移动。称所有棋子所在的顶点的总和（一个顶点上可能有多个棋子，则统计多次）为潜能，要求移动过程中出现的潜能的最大值最小。问这个最小的潜能值是多少。这里$1\leq k\leq n\leq 1000$。

提供一道题目。

首先我们可以用一个向量来维护所有顶点所在的顶点信息。接下来我们考虑贪心算法。记初始向量为$A$，$f(A,t)$表示字典序最小的向量（两个顶点的排序规则是第一关键字为权值，第二关键字为编号），满足在潜能上限不超过$t$的前提下能从$A$通过若干步骤转移到$f(A,t)$。

考虑到不同的棋子的移动是独立的，因此我们可以同时让所有棋子移动到最小的顶点。考虑给定潜能上限$t$，之后我们贪心将所有顶点向具有更小权重的顶点移动（在不违背上限的前提下）。这里我们给出了计算$f(A,t)$的算法，时间复杂度为$O(n^2\log_2n)$。

很显然在给定潜能上限$t$的前提下，是否能从$A$转移到$B$等价于$f(A,t)=f(B,t)$。我们要找到最小的$t$，满足这个公式。这里可以使用二分，则时间复杂度为$O(n^2(\log_2n)^2)$。但是我们可以通过增量的方式，不断增大$t$，同时考虑造成的影响，这样就能去掉二分，将时间复杂度优化到$O(n^2\log_2n)$。

给定和最大乘积

题目1：给定总和$m$，要求选择一个$n$并找到一组正整数$x_1,\ldots,x_n$，满足$\sum_{i=1}^n x_i=m$，且$\prod_{i=1}^nx_i$最大化。其中$1\leq m\leq 10^{18}$，输出$(\prod_{i=1}^nx_i)\mod p$，其中$p$为某个正数。

当$m\leq 1$的时候，问题是很简单的，这里不讨论。

首先我们可以发现对于$t\geq 4$，我们始终可以将其拆分为$t-2$和$2$，且二者的乘积不小于$t$。因此我们可以断言$x_i$仅可能为$2$或$3$。

同时可以发现当$2$出现达到$3$次的时候，由于$2^3<3^2$，因此我们可以将$3$个$2$替换为$2$个$3$。故我们只需要暴力枚举$2$出现的次数，仅可能为$0,1,2$次。

考虑$r=m\pmod 3$。

  • 如果$r=0$，那么$2$只可能出现$0$次。
  • 如果$r=1$，那么$2$只可能出现$2$次。
  • 如果$r=2$，那么$2$只可能出现$1$次。

这样我们不需要比较操作就可以得到最优解。

置换与交换

置换与交换类型的问题非常常见，问题一般就是现在有一个置换，每次操作允许交换置换中的两个元素。问最少排序需要的步骤数。

这个东西题目出的非常多。

题目1：给定一个$1,\ldots,n$的置换$p$，每次操作允许交换两个元素，要求计算将其排序的最少步骤数。

创建一个包含$n$个顶点的有向图，并对于$1\leq i\leq n$，加入边$(i,p_i)$。图可以分成若干个环，记环的数目为$C$。

考虑一次操作，最多使得一个环分裂成为两个，或者将两个环合并为一个。由于当置换有序的时候，总共会存在$n$个环，因此答案为$n-C$。

时间复杂度为$O(n)$。

题目2：给定$n$个二维平面点，不存在任意三个点共线。第$i$个点上写着数字$a_i$，且$a_1,\ldots,a_n$是$1,\ldots,n$的一个排列。每次操作选择两个点，在它们之间画一条线段，之后交换两者上写的数字。要求执行一些操作后，使得对于$1\leq i\leq n$满足第$i$个点上写着$i$，且画的线段除了端点外不会相交。

提供一道题目题目。

首先我们不考虑那些初始就写着目标值的点。建环后可以发现所有环的长度都至少为$2$。

接下来我们将所有环合并。具体的做法就是我们选择一个最靠下的点$z$（有多个就选择最靠左的）。之后将其余点按照以$z$为中心的极角排序。

之后可以按序遍历其余点，如果点$i$和点$i+1$不在同一个环中，就交换这两个点。

可以发现如此操作后，所有点都在一个环上了，并且出现的线段都是在相邻极角之间。这意味着$z$到任意点的射线都不会与这些线段相交。

之后问题我们可以把$z$与$z$上所写数字对应的点交换，重复这个过程直到$z$和$z$上所写数字相同。

时间复杂度为$O(n\log_2n)$。

最小差值问题

题目1：给定两个长度为$n$的序列$a_1,\ldots,a_n$和$b_1,\ldots,b_n$，可以任意选择一些下标，如果你选择了$i$，则会将$a_i$提换为$b_i$。要求让$a$中最大值和最小值的差值尽可能小，找到最小的差值。其中$1\leq n\leq 10^6$，$-10^9\leq a_i\leq 10^9$。

首先我们可以不妨认为对于所有$1\leq i\leq n$，都有$a_i\leq b_i$（否则你先交换两个数即可）。之后我们暴力枚举允许出现的最小值，并维护当前的最大值。由于最小值只有$2n$种情况，因此只会发生$2n$次的最小值替换，我们从小到大考虑这些最小值。假设我们选择了最小值$x$，那么由于我们现在维护的一些值可能因为小于$x$因此变得非法，我们需要尝试替换为较大的值。我们可以用一个最小堆来维护这些候选人，同时由于最大值始终递增，只需要一个变量维护即可。总的时间复杂度为$O(n\log_2n)$。

题目2：给定长度为$n$的序列$a_1,\ldots,a_{n}$。要求将这些数分成任意组，每组至少有一个数，最多有两个数。要求组中值之和的最大值和最小值的差距尽可能小，输出这个最小值。其中$1\leq n\leq 5000$，$-10^9\leq a_i\leq 10^9$。

提供一道题目。

假设$a$是从小到大排序的。

假设最终被配对的数从小到大排序为$b_1,\ldots,b_k$。如果$b_1$与$b_k$不配对，而$b_1$与$b_i$，$b_j$与$b_k$配对，那么我们重新将$b_1$与$b_k$配对，而$b_i$与$b_j$配对，由于$b_1+b_i\leq b_1+b_k,b_i+b_j\leq b_j+b_k$。因此新的配对不会违背任何约束。继而我们可以推出$b_i$与$b_{k+1-i}$配对。

首先如果所有数都不是正数，那么我们将所有数全部取反，这样得出的结果是不变的。

当所有数都非负的时候。如果存在$i<j$，$a_i$未参加配对，但是$a_j$参加了，那么我们可以知道最小值不超过$a_i$。这时候我们将$a_i$与$a_j$位置交换，可以发现新的结果不会变坏。因此我们可以断言参与配对的元素一定正好形成$a_1,\ldots,a_n$的一个前缀。我们可以暴力枚举所有前缀并计算差值，这样就提供了一个$O(n^2)$的算法。

最后我们考虑$a$中同时有正数和负数的情况，即$a_1<0$且$a_n>0$。那么可以发现$a_1$和$a_n$必定都参与匹配，根据第一块内容可知$a_1$与$a_n$在同一组情况是最优的。弹出$a_1$与$a_n$合并为同一组，重复这个流程直到$a$中只剩下非负或非正数，记录$L,R$为已知组形成的范围。之后用之前提到的算法即可$O(n^2)$解决剩下的内容。

区间减法问题

题目1：给定长度为$n$的序列$a_1,\ldots,a_n$，要求执行下面操作若干次，使得序列中所有元素都变成$0$。

  • 每次操作选择一段连续的区间，将区间中所有元素减少1。

要求找到达成目标的最小操作数，并输出。其中$1\leq n\leq 10^6$，且$1\leq a_i\leq 10^9$。

引入一个新变量$a_0=0$，如果存在$i\geq 1$，满足$a_i>a_{i-1}$，那么很显然我们至少需要有$a_i-a_{i-1}$个操作，起始于下标$i$。

于是我们找到了一个结果的下界$\sum_{i=1}^n\max(a_i-a_{i-1},0)$。接下来我们还要证明这个下界同时是可以达到的。

事实上，如果$a_i\leq a_{i-1}$，那么我们可以继承所有之前未终止的操作。而如果$a_i>a_{i-1}$，那么我们可以继承之前的$a_{i-1}$个操作，并额外创建$a_i-a_{i-1}$个操作，以$i$作为起始。很显然这种方式得到的操作数为$\sum_{i=1}^n\max(a_i-a_{i-1},0)$。

因此答案为$\sum_{i=1}^n\max(a_i-a_{i-1},0)$，时间复杂度为$O(n)$。

题目2：给定长度为$n$的序列$a_1,\ldots,a_n$，要求执行下面操作若干次，使得序列中所有元素都变成$0$。

  • 每次操作选择一段长度在至少为$L$，且最多为$R$的连续的区间，将区间中所有元素减少1。

要求找到达成目标的最小操作数，并输出。其中$1\leq n\leq 10^6$，且$1\leq a_i\leq 10^9$，$n\geq R\geq 2L-1$，$L\geq 1$。如果无解则输出$-1$。

提供一道题目。

首先考虑当$R=N$的时候，如何解决这个问题。很显然我们可以贪心来做。具体就是我们维护一个集合$S$，$S$中存储所有未闭合的操作区间。之后从左到右扫描我们的序列$a$。考虑现在处理的是$a_i$，这时候有两种情况：

  • 一种是$|S|>a_i$，这时候我们必须闭合$S$中的一些序列。我们可以随意挑一些长度至少为$L$的区间，关闭，并从$S$中移除。如果剩下的都是长度不超过$L$的区间，那么就无解。
  • 另一种情况就是$|S|<a_i$，这时候我们必须新建一些操作区间，我们可以插入$a_i-|S|$个新的操作区间（注意开始下标相同的操作区间，我们可以合并并记录它的重复次数），以$i$作为起始下标。

在扫描完所有的元素后，我们要关闭集合$S$中所有的操作区间（如果有长度小于$L$的区间，则无解）。

上面的算法正确性和最优性是很显然的。

下面我们考虑$R$任意的情况。这时候我们实际上可以认为一个操作区间长度可以超过$R$，只不过需要额外的费用而已。事实上，如果一个区间长度为$x\geq L$，那么我们一定可以将它分解为$\lceil x/R \rceil$个操作，具体就是按$R$切分成若干段，很显然只有最后一段长度$x \pmod R$可能小于$L$，这时候由于$R+(x\pmod P)\geq 2L$，因此我们可以将最后一段和倒数第二段合并后重新分解为两端长度满足条件的操作序列。同时可以发现继续复用之前遗留的操作区间比新建操作区间一定更优。

因此我们可以按照上面的逻辑来实现我们的算法，只不过在从$S$中删除序列的时候，应该贪心删除$b-i\pmod R$最小的操作区间，其中$b$表示区间的开始下标。

我们可以用一个队列来维护长度小于$L$的操作区间，并用链表来维护长度达到$L$的操作区间，用VEB Tree可以$O(\log\log R)$找到某个点的前驱和后继。因此总的时间复杂度为$O(n\log\log R)$。

树上最小遍历距离

题目1：给定一颗大小为$n$的树，每条边都有对应的边权。现在要求找到一个遍历顺序$v_1,\ldots,v_n$，其中$1,\ldots,n$在其中各出现一次，并且$\sum_{i=1}^{n-1}dist(v_i,v_{i+1})$最小化。其中$1\leq n\leq 10^6$，且边权非负。

首先考虑一个如果必须从$v_1$出发后回到$v_1$，那么很显然最优遍历序至少需要遍历每条边两次，并且这个下界是可以达到的（考虑最简单的递归算法）。因此这时候的解为$\sum_{e\in E}w(e)$。

现在回到这个问题，我们不要求必须回到$v_1$，那么相当于从$\sum_{e\in E}w(e)$中减去$dist(v_n,v_1)$，前者是常数，因此我们要让路径最短，等价于让$dist(v_n,v_1)$最大化。现在问题就成了找到树上最远的一对点，就是树上的直径，而这个问题可以$O(n)$解决。

题目2：给定一颗大小为$n$的树，每条边都有对应的边权。现在要求选择$k$个$1$到$n$之间的不同的数$v_1,\ldots,v_k$，并且$\sum_{i=1}^{k-1}dist(v_i,v_{i+1})$最小化。其中$1\leq n\leq 3\times 10^3$，且边权非负。

提供一道题目。

先阅读题目1的解法。

考虑包含所有$k$个选中顶点的最小连通块（仅保留必要的顶点，让选中顶点两两连通），如果这个最小连通块中包含非选中顶点，我们一定可以将某个选中顶点替换为其中的非选中顶点，且结果不会变差。

因此现在复述一下问题，我们要找到一个大小正好为$k$的连通块，且它的总边权之和减去直径长度最小。

我们可以建立$dp(u,i,j)$表示以连通块以$u$为根，包含正好$i$个顶点，包含直径的$j$个端点，最小的总边权之和减去包含的直径部分长度的值。

这个dp实际上类似树上卷积，每对顶点仅在lca处贡献一次。因此总的时间复杂度为$O(9n^2)$。

向量

最小切割向量

切割向量是指给定一组$k$维向量$A$，要求找到一个最小向量$v$，满足$0\leq v_i$，且对于所有$a\in A$，都至少存在一个下标$1\leq i\leq k$，使得$a_i\leq v_i$。在多个满足条件的$v$中，要求$\sum_{i=1}^ka_i$最小化。

考虑$k=1$的情况下的最优解。很显然我们要选择最大值。时间复杂度为$O(n)$。

考虑$k=2$的情况下的最优解。我们可以通过排序去掉一个维度。具体做法就是我们先按照第2个维度排序。很显然我们需要选择一个后缀，后缀部分通过第二个维度来解决，而其余的前缀部分通过第一个维度来解决。当我们从后向前扫描的时候，我们可以同时维护后缀的最大值，而前缀的最大值有前缀最后一个元素决定。时间复杂度为$O(n\log_2n)$。

考虑$k=3$的情况下的最优解。这时候也是可以做的。具体做法就是按照第三个维度排序，从而类似$k=2$的情况，我们需要考虑后缀。现在的问题变成，我们需要维护一个数据结构，其保存一个二维向量集合。它需要支持插入一个二维向量，并且回答这个向量集合的最小切割向量。

我们考虑如何维护这样的集合。我们可以把二维向量看成平面上的一个点，如果一个点右上角有其它点，这个点可以被删除而不会影响结果。现在剩下的点，按照第一维排序后，第二维呈现递减的性质。

我们可以发现切割向量一定是相邻的两个向量所决定。我们可以用一个多重集合维护所有的间隙以及这些切割相连的状态。而插入新的点，可以会导致一些旧点被删除，我们可以同时维护间隙的删除和插入。

于是总的时间复杂度为$O(n\log_2n)$。

提供一道题目。

对于$k>3$的情况，我也不知道有什么好办法。

最大线段分组交

给定$n$条线段，要求将它们最多分成$k$个组。每一组的价值为其中所有线段的交的长度，而总价值为所有组价值之和。要求找到在给定条件下的最大价值。

提供一道题目。

要解决这道问题需要以下观察。

  • 最多一个组的价值为$0$
  • 如果线段$a$包含线段$b$，则$a$要么和$b$同组，要么$a$单独构成一组。

因此我们可以分类讨论：如果有一个组的价值为$0$，那么这时候我们会选择长度最大的$k-1$个线段单独构组，这时候问题是非常简单的。

现在考虑所有组价值都不是$0$。我们把线段分成两类，如果一个线段包含至少一个子线段，那么这个线段为第一类，其余线段为第二类。

这时候问题变成了计算$f(t)$，即将第二类线段分成$t$组的最大价值，而另外$k-t$组则分配给第一类线段。我们要计算$f(0),f(1),\ldots,f(k)$。可以发现第二类线段之间相互不包含，我们将第二类线段按照左端点进行排序。结合所有分组的价值均非0，可以直接得出结论，最优方案下同组线段一定是下标连续的若干个线段组成。

于是我们可以得出一个dp算法，令$dp(i,j)$表示将前$j$个线段分成$i$组的最大价值。这个dp可以$O(nk)$进行计算。

因此总的时间复杂度为$O(n\log_2n+nk)$。

矩阵最少上色

提供一个$n\times m$的矩阵，初始所有的单元格的值都是$-1$。之后可以执行多次操作，每次操作选择一行/列以及一种整数$c$，将选中的所有元素都改成$c$。

现在给定最终的01矩阵$A$，判断是否可能通过上述操作得到该矩阵，如果可以，则需要找到最少操作次数。其中$1\leq n,m \leq 2000$。

提供一道题目。

我们逆向操作，上色等价于删除同色的一行或一列，要求最终将整个矩阵全部消除。

很显然我们可以贪心删除，得到一个$O(nm)$的算法来判断是否有解。

由于要么行被全部删除，要么列被全部删除，不失一般性，我们可以认为列被全部删除。

现在考虑在列全部删除的情况下，没有被删除的行的数值显然是固定的，因此我们可以得出一个结论，最后只能剩下一些完全相同的行。我们要最小化总的操作步数，等价于要最大化保留的行数。并且在最优解的情况下，很显然相同的行是被同时删除或同时保留的。

现在我们将行按照行的值进行分组。对每个组验证是否存在一种方法，在不删除这组行的前提下删除所有的列。

如果我们使用上面提到的贪心算法，这样得到的时间复杂度为$O(n^2m)$的算法。

下面我们给出一个结论，在存在解的前提下，我们可以选择保留任意一组相同的行（或列），这时候同样有解。于是我们得到了一个$O(nm)$的算法。

这个结论证明非常直观。首先我们考虑在整个流程中，可以发现相同的行始终保持相同，而不同的行则始终不同，列同样。因此我们可以将相同行合并，同样将相同列合并。

考虑有解的情况下，我们记$R(A)$表示$A$中有多少行值全相同，$C(A)$表示$A$中有多少列值全相同。可以发现初始的时候有$R(A),C(A)\leq 2$。并且我们如果我们选择删除一行，则$R(A)$必定减少$1$，而$C(A)$最多增加$1$。对应的如果我们删除列，那么$C(A)$必定减少$1$，而$R(A)$最多增加$1$。

下面我们假设我们要保留某行$r$，那么我们始终优先删除其余行列。最好的情况是最后只剩下$r$。否则我们这时候应该有$R(A)=1$且$C(A)=0$。由于存在解，因此应该每次删除行后会新增一个可行列，删除一列后会新增一个可行行。实际上如果允许行列重新排列，会发现这样的矩阵形如：

00000
10001
11011
11001
10000

或

0000
1001
1101
1000

很显然这时候有$R(1)=C(1)=1$。因此不可能会出现$R(A)+C(1)=1$的情形。这也意味着我们一定可以保留第$r$行。

最大和交错数列

给定长度为$n$的整数数组$a$。定义$S(k)$表示$a$的所有长度为$k$的子序列。记$f(S(k))=\max_{b\in S(k)} g(b)$，其中$g(b)=\sum_{i=0}^{|b|-1} (-1)^i b_i$。要求找出$f(0),f(1),\ldots,f(n)$。

原题。

这里我们可以用DP做到$O(n^2)$的时间复杂度，但是我们实际上可以做到$O(n\log_2n)$。

我们记$B_i$表示$a$的某个长度为$i$的子序列，满足$g(B_i)=f(S(i))$。可以证明$B_i$一定可以通过$B_{i+2}$删除两个元素后得到。证明放在后面。

我们可以将$f(i)$按照$i$的奇偶性分成两类，分别计算。如果我们已经知道$B_i$，要计算$B_{i+2}$，它的计算很类似于DP，并且可以发现分治的时候需要维护的状态是常数大小的，因此我们可以在线段树上做DP，时间复杂度优化到$O(n\log_2n)$。

下面给出证明。对于$B_{k+2}$和$B_{k}$，对于给定$l<r$，且$a_l,a_r\in B_{k+2}$，从$B_{k+2}$中删除$a_l$和$a_r$后得到的新的序列$B'k$，记$c(l,r)=g(B{k})-g(B'_k)$，显然我们要最大化$c(l,r)$，设$c(l,r)$为最优解。

如果$g(B'k)<g(B_k)$，考虑存在一个数组$d$，初始都是$0$。如果$a_i\in B{i+2}$，我们将$d_x$增加$1$，如果$a_i\in B_{i}$，则将$d_x$减少$1$。

首先我们找到最小的下标$R$，满足$d_R=2$，同时我们可以找到最大的下标$L<R$，满足$d_L=0$，可以发现$d_{L+1}=1$。可以发现对于$i\in (L,R)$，$a_i$只有可能同时出现或不出现在$B_{k}$和$B_{k+2}$之中。我们可以发现从向$B_{k}$中加入$a_L$和$a_R$后得到$B'{k+2}$，有$g(B'{k+2})=g(B_{k})-c(L,R)>g(B'k)-c(L,R)\geq g(B'_k)-c(l,r)=g(B{k+2})$，而由于$g(B_{k+2})$是最大结果，因此这是不可能的。

最小字典序矩阵

要求找到一个$kn$行$m$列的矩阵，每个单元格中包含$0$到$k-1$之间的值，且对于每一列，对于任意$0\leq i<k$，$i$都出现正好$n$次。且不存在相同行（所有行两两不同）。

判断是否有解，如果有解，则要求最小化最大字典序行。其中$1\leq kn\leq 10^5$，$1\leq m\leq 20$，$1\leq k<10$。

提供一道题目。

显然必要条件是$k^m\geq kn$，否则一定无解。

我们可以把每一行视作一个$k$进制整数。

很显然正好有$n$行的第一列值为$k-1$，而为了让最大字典序行最小化，同时每行都不同，我们希望能令这$n$行为$(k-1)k^{m-1}+i$，其中$0\leq i<n$。

下面我们考虑其他行。对于$j$开头的行，我们可以令这$n$行为$j\times k^{m-1}+i$，其中$0\leq i<n$。

可以发现上面我们可能无法保证每一列每个整数出现次数均为$n$。但是我们可以做一个简单的置换，将以$j$起始的行，每一个单元格（除了第一列）都应用置换$(i+1 i+2 \ldots i)$。

这时候可以发现每一列的所有整数都应该拥有相同的出现次数，即正好$n$次。

多重排列最大相同元素距离

对于$1\leq i\leq n$，有$a_i$个$i$。我们要将这$S=\sum_{i=1}^na_i$个元素进行排列，对于所有排列中我们要求最近的两个相同元素距离最大（下标的差的绝对值最大）。记$M=\max_{i=1}^na_i$，保证$M\geq 2$。

这个问题有非常简单的贪心解法。记共有$k$个不同元素出现次数为$M$。答案的一个上界为$\left\lfloor \frac{S-kM}{M-1}+k \right\rfloor$。

我们现在来聊聊具体的一个做法，非常简单我们把$k$个出现次数最多的元素（不妨设为$1,2,\ldots,k$），创建$k$个槽，每个槽维护一个链表，最终结果就是将这$k$个链表前后连接得到。首先每个槽中的元素均为$1,2,\ldots,k$。接下来我们分别考虑元素$k+1,\ldots,n$。对于第$t$个被考虑的元素，插入到第$t\pmod{k-1}$个槽的尾部。

这样我们就可以得到上界，自然也就是最优解。

最少逆序对

题目1：给出长度为$n$和$m$的两个序列$a$和$b$。现在希望将两个序列合并为一个长度为$n+m$的新序列，且要求序列$a$中元素的相对顺序不变。要求找到所有新序列中逆序对最少的。其中$1\leq n,m\leq 10^6$。

提供一道题目。

结论1：在最优解中序列$b$的子序列一定是有序的。

不妨设$p_i$表示$b$中最小的第$i$个元素在新序列中的出现位置。如果最优解中$b$无序，则存在某个下标$i$，满足$p_i>p_{i+1}$。这时候我们可以发现交换$p_i$和$p_{i+1}$后可以得到更少的逆序对。

记$f_i$表示$b$中最小的第$i$个元素$x$的最优插入位置（0到n），使得$x$与$a$的逆序对最少。

结论2：$f_1\leq f_2\leq \cdots \leq f_m$。

证明与上面类似，可以通过交换两个相邻的不满足条件的元素从而得到更优解。

因此我们可以发现这个问题中我们可以通过计算局部最优得到全局最优，通过计算$f_i$恢复出$p_i$。

而怎么计算$f_i$，我们可以用分治。类似整体二分，可以保证时间复杂度为$O((n+m)\log_2(n+m)$。