斜率优化dp复习

发现自己几乎忘记斜率优化怎么写了,就来复习了一下。

6-24

从长沙出发去北京ccf总部集合。

CTS2019 凉凉记

又被快速幂送走了

我永远讨厌快速幂

CF1119E

link

题意:你有长度为$2^0,2^1\dots 2^{n-1}$的木条分别$a_0,a_1,\dots a_{n-1}$根。

求最多能组成多少个三角形,使得每根木条最多用在一个三角形内,且每个三角形每条边仅有一根木条构成。$n\le 3\cdot 10^5,a_i\le 10^9$

CF1153F

link

题意:

在一个长度为$l$的区间里面$n$次随机选出一个子区间。

求至少被这$n$个子区间中$k$个覆盖的区间长度和的期望。

$1\le k\le n\le 2000,1\le l\le 10^9$

退役之后的日记

记一下退役之后的每天

CF1137F

link

题意

Lena在玩火柴的时候突然好奇用火柴烧树会怎么样。

由于Lena很善良不想烧树,所以她决定在脑子中模拟烧树的过程。

我们认为烧树的过程是这样的:

CF1140G

link

有一个无向带权图,由两棵树A,B组成,若A树中有边(u,v),则B树中有边(u,v)。并且两棵树的每个对应点都有边直接连接。

q次询问求两点间最短路。

CF1140F

link

给定一个点集,初始为空。

q次操作,每次操作给定一个点,若点集中存在这个点就删除这个点,否则插入这个点。

每次操作完之后,输出反复执行如下操作后点集的大小:

找出x1,x2,y1,y2使得(x1,y1)(x1,y2)(x2,y1)都在点集中,且(x2,y2)不在,并将(x2,y2)加入点集。

$q\le 3\cdot 10^5,TL=3.5s,ML=1G$

CF1132

link

降智严重……

已经不会cf 2k难度的题了……

于是三题滚粗……

这是lk新号第一场debuff吗……

技不如人就是技不如人,找什么借口……

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×