zcmimi's blog

arrow_back双指针共10篇文章

avatar
zc
2020-04-26 14:01:00
查看原题

点击跳转

建立新数c,使c_i=a_i-b_i

那么就是要找多少对i<jc_i>c_j

c排序,然后双指针统计一下就可以了

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

点击跳转

设当前区间为[l,r]

res=\sum_{i=l}^r p_i\times[\prod_{j=l,j!=i}^r(1-p_j)]

s_{[l,r]}表示\prod_{i=l}^r(1-p_i)

res=s_{[l,r]}\sum_{i=l}^r \frac{p_i}{1-p_i}

a_i=1-p_i,b_i=\frac{p_i}{1-p_i}

res=\prod_{i=l}^ra_i\sum_{i=l}^rb_i

假设现在区间变成了[l,r+1]

A=\prod_{i=l}^ra_i,B=\sum_{i=l}^rb_i

res'=A\times a_{r+1}(B+b_{r+1})

=A(a_{r+1}B+a_{r+1}b_{r+1})

=A(a_{r+1}B+p_{r+1})

res'>res,那么a_{r+1}B+p_{r+1}>B

1-p_{r+1}+\frac{p_{r+1}}B>1

\therefore B<1

那么对于每个l,只需要找到最远的r使\sum_{i=l}^rb_i<1

而这又具有单调性,那么\mathcal{O(n)}就可以解决了

avatar
zc
2020-01-20 22:35:00
查看原题

点击跳转

A,B总和不相同,显然是-1

由于元素都大于0,可以使用类似双指针的方法

两个指针在A,B数组中移动,若找到A,B中和相同的两端,答案就+1

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

点击跳转

f_{i,j} =f_{i,k}+1(|a_i-a_k| = |a_k-a_j|)

先对a排序,然后dp,双指针,记得数组开成short

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

点击跳转

记录S_i表示[1,i]中大于等于T的个数

[L,R]满足要求时,S_R - S_{L-1} \ge k

如果[L,R]满足要求[1...L,R]都满足要求

于是我们就可以用two\ pointer

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

点击跳转

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

点击跳转

先把血统编号离散化

两个点之前最多只能有k种血统的牛,所以我们考虑使用two\ pointers

O(n)

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
查看原题

点击跳转

H:minH , V:minV

  A \times (h-H) + B \times (v-V) \le C

A \times h + B \times v -C \le A \times H + B \times V

s = Ah + Bv - C,按s排序,确保i可以取j就可以取(j<i)

枚举H,V,然后用双指针,具体看代码

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

点击跳转

1/1
Search
search