menu zcmimi's blog

arrow_back 分治

二维偏序

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

例题: [SHOI2007]园丁的烦恼

离线

zcmimi
2020-03-20 20:36

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

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

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

每次都选树的重心来处理,最多需要处理$\log n

zc
2020-01-18 22:40

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

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

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

从两边一起找

假设枚举到位置$

zc
2020-01-04 10:21

把风铃看成一棵树

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

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

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

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

zc
2019-12-21 19:47

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

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

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

看到这句话了没?

所以不用考虑分治是

zc
2019-12-21 19:47

类似Moo

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

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

一开始按套路用递归写

然后爆

zc
2019-12-21 19:47

点分治

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

树的重心

树的最大子树最小的点

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

```cpp int rt,mxs=inf,siz[N];

zcmimi
2019-11-01
1 / 1
Search
search