「OI之路」07其他-9带权二分

wqs二分也是指这个,wqs当年论文

本文特点:看到有些几何意义显然的东西在别的文章瞎jb证明;对于实在没法非数学搞的证明直接予以省略

特征就是恰好wt个时最优化(下文如无特殊说明以最小化为例),这个特征就如01分数规划一般,标志性十足,所以套路感强烈

我们设$f(x)=选x个时最优解$(通常定义域、值域是整数),感受一下其实挺多模型都是凸函数或接近凸函数的形状($f(i)-f(i-1) \le f(i+1)-f(i)$),即x越接近最优解的选取数量,答案变优的幅度就越小。如果你能大胆猜测感性理解打表验证发现出函数真的是个定义域连续的凸函数,就可以使用带权二分达到不超过$O(logW*[求一次f极值的复杂度])$(也就是说不限制个数的问题的复杂度,而且具体问题还可能可以更快,因为可能可以预处理)

我们需要利用凸函数的性质(虽然我这么解释有些本末倒置,更多是从使用者而非发明者的思路吧)。具体地,我们二分斜率k(二分的值域显然是$f(x)-f(x-1)$的范围),根据凸函数的性质,任意点一定存在一个斜率切到它,不过如果不是严格凸函数的话,一条直线可能会对应共线的多个切点。固定斜率k求切点的过程,其实就是直线与函数有交的前提下最小化直线的$b=f(x)-kx=\sum(val-k*[选])$,发现相当于做一次不限制个数且每个物品权值-=k的问题。在解决这个问题时,b相同时不妨优先选,这样得到了这条直线上的「最右切点」。二分出在wt右边最左的「最右切点」,$f(wt)=k*wt+b$

至于构造,严格凸函数直接取切点的方案,但通常情况下我们只能直接求出共线那几个点中最左和右的点对应的方案,中间wt的方案没有通用的解法,需要具体题目具体分析

例题1:hdu6094 Rikka with K-Match等一类费用流解决的问题

前置:轮廓线dp、费用流

请先思考后再展开

对于模型本身也就是无关数据范围,黑白染色后费用流是解法,因此是逐渐增广的过程,每次的最短路不可能比上次短,所以是凸的,定义域也显然连续。因此带权二分+轮廓线dp,$O(2^mnlogW)$

例题2:「IOI2000」Post OfficeCF321E Ciel and Gondolas等恰k轮满足决策单调性的1d1d问题

前置:四边形不等式优化1d1d

请先思考后再展开

结论:其函数是凸函数。函数肯定是连续的,求切点方案相当于无个数限制的,满足决策单调性的1d1d,即单调栈+二分解决,总复杂度$O(nlognlogV)$。实现时,求「最右切点」可以考虑每次从最小的多个转移点中选最后那个,归纳可知段数最多

好消息是,这整类问题有着通用的构造方法:将最左右的切点(红、蓝)的方案求出,根据四边形不等式,在相同斜率(增量)下,下面的调整方式(紫、绿)依然保证是最短路,因此在「最右切点」的方案中选第$r-wt$个被完全包含的段,这个段左边是「最左切点」的方案,右边是「最右切点」的方案(实现时就是点集的前缀和后缀拼接起来)

例题3:「2012年国家集训队互测」Tree

其他oj:luogu2619、bzoj2654、hdu4253,暂时并不会构造

在题意上,CF125E MST-Company这题是本题的子集,但需要输出方案

比较靠谱的资料:clj当年题解LCA爷

请先思考后再展开

首先要证明函数连续

引理1:生成树的白边数成一个区间。证明:先黑再白跑MST得到白边集合$MUST$,然后先加入$MUST$再加入其它白边接着是所有黑边,用到不在$MUST$中的白边记作$GOOD$,那么在区间$[|MUST|,|MUST|]+|GOOD|]$中任何边数wt,在$GOOD$中取$wt-|MUST|$条即可

引理2:MST的白边数成一个区间。这个根据MST理论中,权值$<x$的边组成连通性与具体方案无关,而权值x内选边根据引理1是区间,所以整体也是区间

凸函数的数学证明见LCA。无脑做是$O(logW*mlogm)$,归并白边和黑边就是$O(mlogm+logW*(n*\alpha(n)+m))$,code

构造的话,这个做法可能是对的,因为本文重点在带权二分而非这题本身,没有进一步深入研究

例题4:「九省联考 2018」林克卡特树

请先思考后再展开

相当于断开一些边得到wt个块,最大化直径和。斜率k下,相当于每个联通块少k。相当于我们选若干条不交的链当做直径,每条链贡献为长度-k。里面是基本功:

$dp(x,0/1)=向上这条边选不选,dp(x,1)=\max { f(yy,1)+\sum f(y,0) }+e_x,dp(x,0)=(选出增量最大的1、2个y,和-k或不选)+\sum f(y,0)$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/2d112c47.html
转载请注明出处,谢谢!