Gym-102465k Dishonest Driver 给出一个字符串，两个相邻且相同子串可以进行压缩，问压缩后字符串最少有多少字符，n≤700n \le 700n≤700。 将两个相邻区间合并，且 nnn 很小，就很像是区间 DP。 定义 dpi,jdp_{i, j}dpi,j​ 表示 [i,j][i, j][i,j] 的压缩后最少字符数。 显然有两种合并，直接拼起来相加，或者将右区...

$\mu$ 的定义，性质，和几道例题。

邮局 加强版 加强加强版 普通版 dpi,k=min⁡j=0i−1dpj,k−1+w(j+1,i)dp_{i, k} = \min_{j=0}^{i-1}dp_{j, k - 1} + w(j + 1, i)dpi,k​=minj=0i−1​dpj,k−1​+w(j+1,i) 其中 dpi,kdp_{i, k}dpi,k​ 表示前 iii 个放 kkk 个邮局的最小代价，w(l,r)w(l...

简述 对于一个 dpi=min⁡/max⁡j=1i+val(i,j)dp_i = {\min/\max}_{j=1}^i + val(i, j)dpi​=min/maxj=1i​+val(i,j)。 如果 valvalval 中同时有和 i,ji, ji,j 相关的项，我们就不能直接用单调队列优化。 如果 val(i,j)=ci+dj+eifjval(i, j) = c_i + d_j +...

一定要会 trie，不一定要会 kmp。 作者是个 fw，有些话不是很标准，还请见谅。 为了方便，接下来的 AC，没有特殊表明，均表示 AC自动机。 我们直接引入一道题目 P5357。 这题就是标准的模板，从中，我们可以得到 AC 的作用：统计文本串内各个模式串的个数。 我们回忆一下 trie 的作用：判断一个字符串在不在一堆字符串里。 这和题目很像，我们想想怎么建这棵 trie。 我们要找...

我们有这样一个问题：修改点权，询问链上的点权和。这明显是个树链剖分模版。
但如果还有这些操作呢：断开一条边，连上一条边，保证一直是森林。这就是动态树的一种问题。
而 LCT 就是解决这些问题的优秀数据结构。

普通最大流的实现与一些例题。

luogu 阅读链接。 题目链接。 题目的边用的是倍数关系（偏序）。 当 x→y,y→zx \rarr y, y \rarr zx→y,y→z，就必然有 x→zx \rarr zx→z。 为了避免这种情况，意味着每个点要么只有因数，要么只有倍数。 我们将每个点拆成两个点，x0x_0x0​ 表示图中 xxx 只能保留其的因数，x1x_1x1​ 表示其倍数。 再用一条边 (x,y)(x, y)(...

题目链接：HDU5828 rikka with sequece 简要题面：实现 333 中操作：区间开根，区间加，区间求和。 如果直接暴力递归，区间加操作会破坏复杂度，例如交替的 2,32, 32,3 序列，我们反复做全局 +6+6+6，再开根，单次复杂度就变成 O(n)O(n)O(n) 了。 所以我们不能完全暴力，要单独维护一下懒标记。 注意到，有很多数开根后答案相同，比如 161616 ...

替罪羊树是一个优雅的暴力，以均摊 O(log(n)) 的时间复杂度和简单的代码闻名。