一些最值问题

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:给定$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})$。