zcmimi's blog

arrow_back二分共23篇文章

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

可以先考虑离散化

离散话后是1~n

一般要求中位数可以:

二分中位数x

将区间中<x的赋值为-1,\ge x的赋值为-1

若区间和为0,那么x就是中位数

题目是要求左端点在[a,b],右端点在[c,d]的序列的最大中位数

区间[b+1,c-1]是必选的

我们可以求[a,b]的最大后缀和[c,d]的最大前缀

如果这三个部分的和大于零,那么当前二分的值是合法的

这个一看就可以用线段树维护

我们再来考虑x变成x+1会有什么变化:

  1. 原来<x的还是-1
  2. 原来>x的还是1
  3. 原来=x变成-1

所以我们只需修改值为x的位置(可以先用链表或vector存下所有值为x的位置)

其实从小到大排序后按顺序更改就完事了

数离散化后的大小不超过n

我们可以先预处理出所有x(中位数)对应的线段树

可是空间不够啊

这时候主席树就派上用场了

下面是简洁的代码:

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

首先二分出最大一段的最小值,然后dp找出方案数

f[i][j]表示前j个分成i组的方案数,求出的最小值为x

f[i][j] = \sum(f[i-1][k])(S_j-S_k \le x,k \le j-1)

\Theta(n^3m)当然会TLE

我们发现只要找到最小的k之后[k,j-1]都是合法的

这时我们就可以前缀和优化dp

sum[i][j] = \sum_{k=0}^j f[i][k]

f[i][j]=sum[i-1][j-1] - sum[i-1][k-1]

可是\Theta(n^2m)还是TLE

我们可以先预处理出第一个S_j-S_k \le xk

因为S_i具有单调性,所以k不需要每次都重新枚举

还没结束

因为f[i][j]每次更新的时候只需要用到f[i-1][...]这一维,我们可以用滚动数组滚掉数组的一维

但是\Theta(nm+n \log \sum L_i)的复杂度还是觉得很悬

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

在每条重链上搞一个set

或者用线段树+二分

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

直接二分天数即可

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

二分最大差值

然后bfs判断

我怎么又刷水了QwQ

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

首先,我们只用分析 NO 的情况,其他的都是 YES,NO 的情况有两种:

  1. x 既不在 A 中,也不在 B 中,即找不到 a-x 和 b-x,NO;
  2. x 既可以在 A 中,也可以在 B 中,也就是找到了 a-x 和 b-x,如果 x 在 A 中,那么 b-x 一定不在 B 中,因为数唯一,所以 b-x 只能在 A 中,也就是说必须存在 a-(b-x),如果不存在就行不通,同理得如果 x 在 B 中,则必须存在 b-(a-x),如果不存在就行不通,那么如果两个方案都行不通了,也就是说 NO 了。
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

二分

判断的时候枚举区间,用rmq或单调队列来求最值,还可以用堆(看题解的)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们可以发现gcd(a_l,...,a_r)是单调递减的,而or(a_l,...,a_r)是单调递增的

所以我们可以两次二分来找到合法区间

至于求gcd(a_l,...,a_r),or(a_l,...,a_r)我们可以用rmq来求

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

这题真的很妙

可以想到二分最大值

问题就转化为如何判断是否合法

从左到右扫描区间的左端点,扫描到的就把右端点放入堆

每个点的权值可以用线段树树状数组维护

扫描时遇到点值不够时,就从优先队列中找到最大的右端点,区间加一遍

当优先队列为空或次数不足时就不符合要求

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

考虑排序后的序列

i个人说有a_i个人分数比他高,有b_i个分数比他低

从大到小排序后分数和i相同的人的区间为[a_i+1,n-b_i]

我们设L_i = a_i + 1, R_i = n - b_i

那么如果L_i > R_i显然是假话

如果R_i-L_i+1小于这个区间的人数(L_{i'}=L_iR_{i'}=R_i),那么这也是假话

去掉所有一定是假的话后,问题变成:给若干个区间[l_i,r_i],价值为v_i,从中选出若干个没有交集的区间,价值和最大为多少?

2/3
Search
search