zcmimi's blog

arrow_back单调队列共15篇文章

avatar
zc
2020-10-22 10:06:14

查看原题

点击跳转

根据平方和公式可以发现分越多段越好

而进一步又可以发现最后一段的总和越小越好

以下是88分代码(高精什么的懒得写了):

avatar
zc
2020-05-16 21:36:00
查看原题

点击跳转

相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串

那么我们差分之后再判断即可

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

首先用后缀数组求出height数组

可以发现,重复出现的子串在sa数组中一定是连续的

那么在height中也是连续的

那么我们只需要求出 height数组中 连续k-1个数中 最小的数 最大可以是多少 即可

单调队列就可以解决

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

点击跳转

首先要知道选定一个区间首先要减去的是最大的连续d区间的和

可以用单调队列维护当前区间最大连续长度为d的子区间和

我们可以发现如果[l,r]合法,那么[l+1...r,r]都合法

可以使用双指针来优化

复杂度\Theta(n)

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

点击跳转

题目大意:

给定一个长度为 n\leq 500000 的序列 a_1, a_2, \cdots, a_n ,要求对于每一个 1 \leq r \leq n ,找到最小的非负整数 f_{r} 满足

\forall l\in\left[1,n\right]:a_l \leq a_r + f_{r} - \sqrt{|r-l|}

解法

考虑l<r,r>l的将序列翻转后再来一次就可以了

f_r= \max(a_l+\sqrt{r-l})-a_r(l\in[1,r])

可以证明f_r的最优决策点是递增的

可以打表

分治解法

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

点击跳转

f_i表示前i个拆分后最大战斗力和

f_i=\max_{j=1}^{i-1}(f_j+a(s_i-s_j)^2+b(s_i-s_j)+c)

这个很明显是斜率优化式子

设任意0\le j<k < i,若从j转移到i优于从k转移,那么:

f_j+a(s_i-s_j)^2+b(s_i-s_j)+c\ge f_k+a(s_i-s_k)^2+b(s_i-s_k)+c \\ 2as_i\le\frac{(f_k+a{s_k}^2-bs_k)-(f_j+a{s_j}^2-bs_j)}{s_k-s_j}

维护个下凸壳就完事了

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

点击跳转

f_i为前i个任务的费用,t_i为前i个任务时间的总和,w_i为前i个任务费用的总和

f_i=\min_{j=0}^{i-1}(f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j))

设任意0\le j<k<ij转移比从k转移优,那么

f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j) \le f_k+s\times(w_n-w_k)+t_i\times(w_i-w_k) \\ t_i(w_k-w_j)\le f_k-f_j+s(w_j-w_k) \\ t_i\le \frac{f_k-f_j+s(w_j-w_k)}{w_k-w_j}

维护了个下凸壳交了上去,结果听取\color{red}\text{WA}声一片

仔细看了看|T_i|\le 2^8

这也就意味着我们每次截取的直线的斜率不再单调递增,单调队列不能再满足需要

为了保证决策状态的有序性,我们还是选择用一个单调栈维护下凸包。

因为决策集合已经有序,对于任意直线,我们只用在队列中二分出使截距最小的交点

由于出题人十分毒瘤,我们要把斜率大小的判断从相除改成十字相乘

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

点击跳转

题目大意:

给定一个长度为 n\leq 500000 的序列 a_1, a_2, \cdots, a_n ,要求对于每一个 1 \leq r \leq n ,找到最小的非负整数 f_{r} 满足

\forall l\in\left[1,n\right]:a_l \leq a_r + f_{r} - \sqrt{|r-l|}

解法

考虑l<r,r>l的将序列翻转后再来一次就可以了

f_r= \max(a_l+\sqrt{r-l})-a_r(l\in[1,r])

可以证明f_r的最优决策点是递增的

可以打表

分治解法

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

点击跳转

f_i表示[1,i]最多变成多少个

f_i=\max_{s_i=s_j}(f[j-1]+s_j\times (\sum_{i=j}^i[s_i=s_j])^2)

我们可以发现如果s_j=s_{j'}(j'< j),从j'转移一定比从j

这一条件满足决策单调性!

我们可以用单调队列维护单调性

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

点击跳转

显而易见:

f_i = f_j + [ a_i \le a_j ] (i < j \le n)

题目要求是复杂度O(nq)

一看有个步伐限制

那么显然加个单调队列就完事了

1/2
Search
search