zcmimi's blog

arrow_back分治共7篇文章

avatar
zcmimi
2020-03-20 20:36:00

二维偏序

先按 第一维 排序, 第二维 用数据结构维护

例题: [SHOI2007]园丁的烦恼

离线操作

先将每个询问拆成4个点查询

(1,1)(x,y)中点数为s(x,y).

avatar
zcmimi
2019-11-01

点分治

点分治用于大规模处理树上路径

树的重心

树的最大子树最小的点

性质:每一个子树的大小都不超过\frac n2

```cpp int rt,mxs=inf,siz[N];// 当前 根,最大子树大小 void frt(int x,int f){ siz[x]=1

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

先钦定树的重心处理出答案

若当前点是距离最大点对的lca(即在它们之间的路径上),这个点就是最优的

否则最优答案一定在最大点对的lca的子树中

每次都选树的重心来处理,最多需要处理\log n次,总复杂度\Theta(n \log n)

avatar
zc
2020-01-04 10:21:00
查看原题

点击跳转

我们先预处理出L_i,R_i分别表示与a_i相同的数出现在i左边和右边的位置

我们可以使用分治来判断一个区间是否合法

我们设当前区间为[l,r]

从两边一起找

假设枚举到位置iL_i<lR_i>r,那么左端点在[l,i],右端点在[i,r]的区间都是"non-boring"

这时我们只需要判断区间[l,i-1][i+1,r]是否合法就可以了

复杂度可以降至\Theta(n \log n)

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

点击跳转

我们可以用分治愉快的解决这道题

答案统计的时候记得开long\ long

由于某种不可抗力,ai的值将会是1~10^9内随机的一个数。(除了样例)

看到这句话了没?

所以不用考虑分治是否会tle

不过我加了个rmq,就算没有这句话也可以过

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

点击跳转

类似Moo

我们可以发现字符串每次长度变成原来的两倍

我们可以把之前不需要的状态删去

一开始按套路用递归写

然后爆栈了

应该用循环写

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

点击跳转

把风铃看成一棵树

因为交换一根杆的两端不会影响它下面的子树的情况,所以可以采用分治+分类讨论

我们先预处理出最小深度和最大深度

如果差大于1,那么不满足要求

一个端点可以分成三种情况

  1. 都是最小深度

  2. 都是最大深度

  3. 两种都有

如果一根杆左右端点分别为0,10,22,1那么它就需要交换左右端点

如果左右端点都是2那么交换也没用,直接输出-1,结束程序

然后把状态向上传递就可以了

1/1
Search
search