【算法】徘徊在一分和三分之间的算法:

请注意,本文编写于 256 天前,最后修改于 114 天前,其中某些信息可能已经过时。

二分!

二分是指在一个 单调 的有序数列上快速查找某特定值的方法

e.g. 求一个正整数 $x$ 开根后的结果

显然其结果应该是单调的
每次检验区间 mid 是比答案大还是比答案小

将求解问题转化为判定性问题

Problem 1

两个长度为 $n$ 的数组 $a$ 和 $b$ ,生成一个 $n * n$ 的数表,第 $i$ 行第 $j$ 列的元素为 $a[i] * b[j]$ , 求第 $k$ 小

$n \leq 1e6$
$1 \leq a[i] , b[i] \leq 10^9$

显然是不能将数表全部建出来的
假设将 $a , b$ 从小到大排序,那么数表中前 $k$ 小元素应该集中在左上角

所以二分一下第 $k$ 小的值,对于每行 two point 记录一下比它小的元素个数 check 即可


中位数相关问题

一些求中位数或者第 $k$ 大的数,可以通过二分将数值简化为 0 1 问题

Problem 2

有一个底部宽为 $2n - 1$ 的金字塔,除了底层以外,每一个位置的数都是下面三个数的中位数,求塔顶的数是多少

$n \leq 10^5$

二分一下顶端的数是多少,把大于等于二分数值的变成 1 ,小于的变成 0
得到 0 1 序列

观察发现 2 个 1 的上面必然是两个 1 , 2 个 0 的上面必然是两个 0
而 0 1 0 1 0 这样的序列必然会取反一部分(看左右端点)
相当于这样的序列每次会被两边的连续 0 和连续 1 蚕食 (也会被边界蚕食)
连续 0 和连续 1 同样也会被边界蚕食,所以看最后留下的什么,只需要从两边到中间扫一遍即可

时间复杂度 $O(n \log n)$

Problem 3

有一个长度为 $n$ 的序列,每个数在 $[1,n]$ 之间
进行 $k$ 次操作,每次操作指定一个区间,然后将这个区间的元素升序排列
询问第 $x$ 个数的数值是多少

$n , k \leq 10^5$

二分最后一个元素
把大于等于二分数值的变成 1 ,小于的变成 0
然后用线段树优化区间区间排序(区间求和,区间赋值)

难道不觉得很神奇么
不觉得
:(


01 分数规划

有一些物品,有一些贡献 $a_i$ , 费用 $b_i$ ,在某些限制条件下,设 $f(x)$ 为收益, $g(x)$ 为费用,求 $r(x) = \frac{f(x)}{g(x)}$ 最大值

二分一下 $r(x) = y$ ,把问题变为验证 0 与 $f(x) - y * g(x)$ 的大小关系,取合法点即可

Problem 4

一张 $n$ 个点 $m$ 条边的有向图,每条边有一个边权 $w_i$
求一个环满足使之的平均边权最大

$n , m \leq 5000 , - 10^9 \leq w_i \leq 10^9$

二分平均边权,每条边减去这个权值,找正环
BFS ?

Problem 5

一个 $n$ 个点 $m$ 条边的图(不一定连通)。一个子图的优美程度定义为 $\frac{\text{子图的边数}}{\text{子图的点数}}$
求最大优美程度

按照以往惯例,我们二分一下答案 $x$ ,将原题转化为判定性问题

即 $x * \text{子图的点数} - \text{子图中边数}\ ?\ 0$

这个东西的话我们可以将点一个正权,边一个负权,选边就必须选点,做最大权闭合子图,用最小割求解


带权二分

解决一系列带有 $K$ 限制的问题
这类问题一般来说会有这样的性质:操作次数越多,结果越大

一般来说这样的问题需要枚举操作次数
就可以通过将操作带上一个权值的方法来使得 $O(\text{有限制的问题})$ 变为 $O(\text{无限制的问题}) * \log(v)$ ,其中 $v$ 为二分值域

Probelm 6

给定一个 $n$ 个点 $m$ 条边的无向带权连通图,每条边是黑色或者白色,让你求一棵最小边权的恰好有 $K$ 条白色边的生成树

$n \leq 5*10^4 , m \leq 10^5$

显然要是没有个数限制,肯定选一个边尽量小的
但是现在有个数限制

如果白色边选多了话需要尽量用黑色边替代
反之亦然

如果给定白色边一个额外的边权 $C$ ,那么白色边被选的数量就会在 $[0 , num]$ 之间浮动,当恰好被选 $K$ 条时,达到原题最优(有几条白色边在额外权值的作用下替代黑色边/被黑色变替代)

注意细节:随着 $C$ 的增加,白色边边数单调不减,所以还要加上 eps 判断

Problem 7

BZOJ 3675 [APIO 2014]序列分割

这个题目显然是可以斜率优化的
所以说就过了?

没错,你就 A 掉了
时间复杂度 $O(nk)$

修改一下 $k$ 的范围
原题:$1 \leq k \leq min(n - 1 , 200)$
修改:$1 \leq k \leq n - 1$

来来来,继续 $nk$ ?

发现切 $K$ 刀的性质同样是可以利用的(切的越多答案越大),所以考虑二分权值,同样还是套一个斜率优化 DP
时间复杂度 $O(n \log v)$

Probelm 8

BZOJ 4518 [SDOI 2016]征途

详见 题解

题目要求变为最小化

$$\sum_{i = 1}^{m}b_i^2$$

转移方程 $f[i] = min(f[j] + (sum[i] - sum[j])^2)$

发现这个东西是可以斜率优化的

然后老套路带权二分一下,时间复杂度 $O(n \log v)$ 通过了这道 $n \leq 3000$ 的题

Probelm 9

有一颗 $n$ 个点的树,每条边有边权,你现在需要把这棵树使用不超过 $k$ 条 边不相交的链 覆盖 ,最小化所有未覆盖边的长度之和加上使用的链的条数 $*d$

$n,k,d \leq 10^5$

这个题它自带了一个边权,但是还是一样的给它一个额外权值

唯一不同的是需要在开始的时候判断一下能否用少于等于 $k$ 条解决问题,要是能,直接输出答案即可,最终就是一个二分 + 树形 DP


二分专题就搞完啦!
看起来的东西其实并不那么简单
继续加油~

(明天不考试有点小兴奋呢)

Comments

添加新评论