zcmimi's blog
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

树形dp 长链剖分

加强版

先来考虑1 \le n \le 5000

f[i][j]表示在i的子树中与i距离为j的点数

显然f[i][j] = \sum f[to][j-1](f[i][0] = 1)

g[i][j]表示以i为根的子树中,点对(x,y)满足x,ylca(x,y)距离都是d,并且lca(x,y)i的距离为d-j的点对数

g[i][j] = \sum g[to][j+1]

ans = \sum_{i=1}^n (g[i][0]+g[i][j] \times f[to][j-1])

我们来考虑加强版

n \le 100000

有点像静态链分治和树链剖分

我们计算长链的时候结果不需要清空,其他儿子节点重新计算

这样可以省下长链的时间

长链剖分真是个毒瘤(指针毒瘤)

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

点击跳转

显而易见:

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

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

一看有个步伐限制

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

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

点击跳转

反转子序列相当于多次交换子区间的两端

f[l][r][d][u]为区间[l,r],值域为[d,u]

f[l][r][d][u]=max( \\\\ f[l][r][d+1][u], \\\\ f[l][r][d][u-1], \\\\ f[l+1][r][d][u]+(a[l]==d), \\\\ f[l][r-1][d][u]+(a[r]==u), \\\\ f[l+1][r-1][d][u]+(a[r]==d)+(a[l]==u))(\text{反转})

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,结束程序

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

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

点击跳转

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

点击跳转

缩点后跑最长路

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,k)表示将前i个分k次的分数

我们可以dpk次就可以了

f_i为前i个,g_i为上一次dp的结果

f_i=\max_{j=1}^{i-1}(g_j+s_j\times(s_i-s_j))

取任意0\le k<j <i且从j转移比从k更优,那么

g_j+s_j\times(s_i-s_j)\ge g_k+s_k\times(s_i-s_k) 展开得

g_j+s_is_j-{s_j}^2\ge g_k+s_is_k-{s_k}^2 移项得 s_i(s_j-s_k) \ge {s_j}^2-{s_k}^2+g_k-g_j 整理得 s_i\ge \frac{({s_j}^2-g_j)-({s_k}^2-g_k)}{s_j-s_k}

注意s_j-s_k有可能为0,要特判

因为要求的是最大值,所以我们维护一个上凸壳就可以了

56/74
Search
search