wqs二分学习笔记

· · 个人记录

什么是wqs二分？

wqs二分可以解决一类带限制最优解问题。

比较明显的就是带 恰好选 k 个物品这种限制。

如果这道题能用wqs二分做，它对于答案一定要具有凸性。

下面用上凸函数举例子

什么意思呢？

对于一个函数 f(x) 它的横坐标表示选了多少个个物品，纵坐标表示选了横坐标个物品时的最优答案。

那么他就是一个长这样的函数。

显然k等于时 6 ，取到最大值。

如果我们有一个复杂度为 O(w) 做法，可以求出无限制时的最大值，那么我们跑一边的出的结果就是 k=6。

但是我们的限制是恰好选 7 个物品，我们就要对这个函数做一些处理，使它的最大值向右移动并且不影响凸性。

这时我们给这个函数加一个一次函数，使它最大值移动。

感性理解就是我们二分一个奖励，如果你选一个物品，那么你的获得的值加上一个奖励值。

那么它最后的形态就是这个：

好耶，现在它的最大值就是 k=7 了！

注意问题!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

如果遇到的凸包是一个平的，需要统计的 k 一定是最左点或者最右点。

二分的上下界要大于k=0时的答案。

怎么找凸性

用超能力(bushi

一个通用的方法就是如果它能费用流模型，那么它一定就有凸性。

这里的费用流模型指的是 F(x) 是钦定从 s 连向 t 流量为 x 时的最小费用。

可以借此证明凸性。

例题

  1. 给定长度为 n 序列 a_i ，要求选择恰好 k 个不相交的非空子区间，使得选中元素的价值和最大。

先来一道论文题

如果证明凸性的话要考虑一段时间，但是费用流模型显然很好建。

感谢大佬Flying2018的图

然后贪心直接做就行，如果遇到负数就断开。

  1. 最小度限制生成树

简单题。

每次 check 时跑 Kruskal 别忘了保证选的关键边数量要最小。

3.Gosha is hunting

首先期望可以转化成转化成权。

宝贝球是 p_i，超级球是 u_i，都用是 p_i+u_i-p_iu_i。

朴素做直接 O(n^3) dp。

设 \texttt{dp[i][j][k]} 表示考虑前 i 个神奇宝贝用了 j 个宝贝球，用了 k 个宝贝球，能得到的最大权值。

显然这个背包具有凸性，考虑二分一维，复杂度变成 o(n^2logn)。

发现可以继续二分另一维，复杂度变成了O(nlog^2n)。

4.CF802O April Fools' Problem (hard)

轻易建出费用流模型:

wqs二分，发现一个点的决策有两种情况:

  1. 准备信

  2. 写出之前花费最小的信。

简单反悔贪心一下即可。

5.P4383 [八省联考 2018] 林克卡特树

贪心转化一下题意，发现把一条边删掉相当于将一棵树变成两个连通块，新加的边就连通那两个连通块的直径。

题意就变成了在树上寻找 k+1 条点不相交链，并且最大化这 k+1 条链的边权之和。

考虑树上背包，发现转移不好转移。

那就多维护状态。考虑一条链在一个点上可能是向下延伸一条，两条，不延伸。

设 \texttt{dp[i][k][0/1/2]} 表示以 i 为根的子树内已经选了 k 条边，当前点度数为 \texttt{0,1,2} 时的最大边权之和。

转移考虑是否选这条边。

注意如果选了的话，两个度数为0的转移会生成一条链，两个度数为1的链合并会少一条链。一旦两个点度数有一个为2了就无法转移。

边界：dp[u][0]=0,dp[u][1]=-INF,dp[u][2]=-INF

这样就完了？

仔细考虑是有问题的，因为如果只留一个点它也算是路径。

这咋整？

考虑将 dp[u][2] 初值设为0。这样表示单个点自己就是一个路径。

套用官方题解中的一句话，假设你是一名秒出dp，即将ak的julao，闲来无事的时候的打印了k=0~100的所有答案，你会惊奇的发现这个函数是一个上凸函数/差分单调递减

这样直接wqs二分，可以把背包的第二维 k 压掉了。

00 合并k+1,11 合并 k-1

统计的时候别忘了cnt要最小，可以用结构体重载运算符一下。

凸性证明可以类似例题1的树上扩展。