[总结] wqs二分学习笔记

2019/02/15 08:56
阅读数 7

论文

提出问题

在某些题目中,强制规定只能选 $k$ 个物品,选多少个和怎么选都会影响收益,问最优答案。

算法思想

对于上述描述的题目,大部分都可以通过枚举选择物品的个数做到 $O(nk^2)$ 或 $O(nk)$ 的 $\mathrm{DP}$,如果没有选择个数的限制的话,复杂度大概会降为 $O(n)$ 级别。

先不考虑数量限制。

假设要最小化权值。

还是拿题说吧:给定长度为 $n$ 的正整数序列,要求将该序列划分为 $k$ 段,记每段之和为 $sum(i)$,求最小的 $\sum\limits_{i=1}^k sum(i)^2$。

如果没有段数限制,那我们肯定是每个数分成一段对吧。

如果加上段数限制呢?

先放上结论:打表可得如果以段数 $k$ 为横坐标,以该段数求得的最小和 $f(k)$ 为纵坐标,把这 $n$ 个点放在平面直角坐标系上,那么形成的图形会是一个上凸包。也就是相邻两点的斜率单调不增。

那就可以考虑$\mathrm{wqs}$二分了。

注意当前的问题是:我们知道这个图形是一个上凸包,但是并不知道具体的 $(x,f(x))$ 坐标。

我们可以二分一个权值 $mid$,这个 $mid$ 表示,我们要拿一条直线去切当前这个凸包,这个直线的斜率为 $mid$。因为是上凸包,那这条直线肯定会在交某个点 $(x,f(x))$ 时截距取到最小值。设当前截距为 $g(mid)$。

直线可以表示成 $y=kx+b$,所以 $f(x)=mid\cdot x+g(mid)$。

移项,$g(mid)=f(x)-mid\cdot x$。

观察上面的等式,如果当前横坐标为 $x$ 的话,$g(mid)$ 恰好是 $f(x)$ 减去 $x$ 个 $mid$。

$f(x)$ 不好求,那我求出来 $g(mid)$,再顺便求出来 $x$ 不就行了吗。

也就是说,如果能求出截距 $g(mid)$,并且知道当前切到点的横坐标 $x$,那就可以求得 $f(x)$,并且可以根据 $x$ 和题目中的 $k$ 来调整 $mid$ 了。

回到题目,我们假设当前没有分 $k$ 段这个限制,但是多了一个条件,每分一段都需要将代价额外加上 $mid$ 。

在这个条件下,我们做一遍没有取物品限制的$\mathrm{DP}$,得出当前的最优解 $a$ 和取最优解时候分出的段数 $b$,那就有 $g(mid)=a,x=b$。

这样就能求出来 $f(x)$ 了。

但是关键不在 $f(x)$,而在这个 $x$。如果使用的这个 $x$ 大于题目中的 $k$,那就得增大这个 $mid$,感性理解一下,代价增多了分的段数才会少,反之就要减少 $mid$。

这样通过二分就可以找到一条恰好切于 $(k,f(k))$ 这个点的直线,进而就知道答案 $f(k)$ 了。

还有一个问题没有解决,如果我们二分不出来这个具体的 $k$ 怎么办,也就是说,凸包上出现三点共线的情况怎么办。

如果这样,我们就再额外添加一个规则,比如说在满足 $g(mid)$ 为最大权值的情况下使得 $x$ 最小。这样就知道直线的最左端点 $t$ 了。又因为斜率和截距是相同的,所以即使 $t!=k$ 拿截距 $g(t)-k\cdot mid$ 也还是最终的答案。

例题

[国家集训队2] Tree I

Description

给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有 $k$ 条白色边的生成树。题目保证有解。

Sol

这就是$\text{wqs}$二分裸题了。二分一个 $mid$,然后把所有白边的边权加上 $mid$,然后求一下当前的花费和用了几条白色边,然后动态调整即可。

这里有一个细节就是会出现白边和黑边边权相等的情况,这时候就要用到上边的做法,强制规定一个规则。假设我们规定相等时先用白边,那二分就这么写:

while(l<=r){
    int mid=l+r>>1;check(mid);
    if(used>=k) ans=mid,l=mid+1;
    else r=mid-1;
}

关键在于是 $used>k$ 时记录 $mid$ 还是在 $used<k$ 时记录。

因为我们令 $x$ 尽可能大,所以要在 $used>=k$ 时记录 $mid$。

代码

[Luogu4983] 忘情

Description

定义一段序列的值为 $\frac{\left((\sum\limits_{i=1}^n x_i\times \bar x)+\bar x\right)}{\bar x^2}$ ,其中 $n$ 为该序列长度。

给定长度为 $n$ 的序列,要求分为 $m$ 段,使得每一段的值的和最小。

Sol

把这个式子拿出来推一推,发现这就是个斜率优化的式子了。

然后就套路二分 $mid$,$\text{check}$的时候用斜率优化 $O(n)$ 求就行了。

md这题wa了好几次竟因$\mathrm{define}$没加括号身败名裂

代码

[CF739E] Gosha is hunting

Description

有 $a$ 个宝贝球和 $b$ 个大师球。对于每个神奇宝贝,用宝贝球抓到的概率为 $p_i$,用大师球抓到的概率为 $q_i$ (咦不是100%吗) 。不能对一个神奇宝贝用多个相同种类的球,但是可以既用宝贝球又用大师球。问最优方案下期望抓到的神奇宝贝数量。

Sol

这题...因为有两个限制,所以要$\text{wqs}$套$\text{wqs}$。

每次二分出 $mid1,mid2$,表示每使用一个宝贝球就要支付 $mid1$ 的代价,每使用一个大师球就要支付 $mid2$ 的代价,然后正常做$\text{dp}$,记录三个状态:最优方案期望抓多少,最优方案下用多少宝贝球,最优方案下用多少大师球。然后转移取最大值就好了。

一个小细节就是,如果同时用宝贝球和大师球,那期望不仅仅是 $p_i+q_i$,而应该是 $p_i+q_i-p_iq_i$。这个推一推式子就知道了。

代码

[HEOI2018] 林克卡特树

Description

给定一棵 $n$ 个节点带边权的树,求 $k+1$ 条点不相交的链使得边权和最大。$k<n\leq 3\cdot 10^5$。

Sol

首先有个 $60$ 分做法,就是暴力树形$\text{DP}$。

通常设状态都是 $f[i][j]$ 表示点 $i$ 为根的子树,选了 $j$ 条链的最大边权和。但是我们发现这并不能转移。观察到最终由选出来的链构成的图上,每个点的度数只有 $0/1/2$ 三种,因此不妨将状态变为 $f[i][j][0/1/2]$ 表示点 $i$ 为根的子树,选了 $j$ 条链,现在点 $i$ 的度数为 $0/1/2$ 的最大边权和。这样就可以转移了。

假设当前点为 $x$,刚$\text{DP}$完 $x$ 的一个孩子 $y$,现在要进行背包合并。

转移根据取不取 $(x,y)$ 这条边分为两种情况讨论。

不取

设 $now=\max(f[y][k-i][0],f[y][k-i][1],f[y][k-i][2])$,让 $x$ 的每个状态和 $now$ 取个$\max$就好了。

设 $d$ 为 $(x,y)$ 的边权。

这个分开看比较好:

$f[x][k][1]=\max(f[x][k][1],f[x][i][0]+f[y][k-i][1]+d,f[x][i-1][0]+f[y][k-i][0]+d)$

后边两项分别表示,从子树 $y$ 中伸上来一条链然后连接上 $x$,或新建一条链,让 $(x,y)$ 单独作为一条链的两个端点。

$f[x][k][2]=\max(f[x][k][2],f[x][i+1][1]+f[y][k-i][1]+d,f[x][i][1]+f[y][k-i][0]+d)$

后边两项分别表示,让 $x$ 作为一条链中间的某个点,即将从 $x$ 其他子树伸上来的一条链和 $y$ 伸上来的一条链接在一起,或将 $y$ 直接与 $x$ 从其他子树伸上来的一条链合并。

初值就是 $f[x][0][0]=f[x][1][1]=f[x][1][2]=0$,其他都为 $-\infty$。

后边两项表示,让点 $x$ 作为一条向上延伸的链的最下方的端点,和让 $x$ 单独成为一条链。

这样就可以通过 $O(nk^2)$ 的$\text{DP}$拿到$60$分了。

60分代码

正解就是在此基础上进行$\text{wqs}$二分。

二分一个权值 $mid$,表示每选一条链就要付出 $mid$ 的代价。

然后进行没有选出链数限制的树形$\text{DP}$。每个状态 $f[i][0/1/2]$ 记录两个值,选出的最大边权和与在此基础上最多的链数。

然后二分就好了。

这里也有在凸包上三点共线的问题,解决方案就是,因为我们最大化了选出的链数,所以在二分过程中,选出的链数如果 $>=k$ ,那就得记录当前的 $mid$ 了。

代码

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部