8 月做题笔记

· · 个人记录

暑假过了一半了才想起来做题笔记的事（（（

AC 自动机，先建出 fail 树

发现字符串 x 在字符串 y 中出现的次数即为以 x 的结束节点为根的 fail 树的子树中 y 节点的个数，于是用 fail 树的 dfs 序+树状数组维护一下即可

然后考虑把询问离线下来，挂到对应的节点上，然后在 trie 树上 dfs 一遍处理询问

首先看到了一个 01 分数规划的柿子，先二分答案

假设当前二分到了 \alpha，则需要 \frac{\sum val_e}{cnt}\ge \alpha \to \alpha\times cnt+\sum val_e\ge 0\to \sum(val_e-\alpha)\ge 0

于是将每条边的边权减 \alpha，看树的最长链是否大于等于 0 即可

接下来，由于题目有边数的限制，所以考虑 dp

令 f_{u,k} 为以 u 为根的子树中，相对 u 深度为 k 的最长链

然后发现下标中有深度，考虑长链剖分

然后发现每条边有一个权值，不太好在长链剖分的过程中处理

于是记录一个 g，就是当前的 u 沿长链一直往下走的边权和，此时 f 记录的其实是 f-g

然后用线段树维护一下即可，时间复杂度 \mathcal O(n\log n)

树剖裸题，但是出题人的本意不是考树剖（（

两只 \log 的解法：树剖直接上

一只 \log 的解法：维护两个树状数组，用树上差分的思想解题

当我们要修改一条路径 u\to v 的时候，在 u 节点上增加 d，在 v 节点上增加 d ，在 u 和 v 的 LCA 减少 d，在 LCA 的父亲节点减少 d

查询一个节点上的值即为子树和

但是要求查询的是一个节点为根的所有子树的和

发现要求的东西即为 \sum dep_{u,v}\times tag_u

然后转化一下，用一个树状数组记录 $\sum dep_v\times tag_v

这里 dep_v 指 v 的绝对深度，也就是相对于根节点的深度

另一个树状数组记录 \sum tag_u

于是很明显答案就是第一个树状数组的查询结果减去第二个树状数组的查询结果 \times (dep_u-1)

前置芝士：最大权闭合子图

以建立 n 个代表通讯信号中转站的节点，点权为 -p_i，建立 m 个代表用户的节点，点权为 c_i，接下来根据 a_i,b_i 建立后继节点的关系，跑一遍最大权闭合子图即可

我网络流还是没有一遍写对过咋办啊（

双倍经验（甚至还是弱化版）：Luogu P2774 方格取数问题

前置芝士：二分图最大权独立集

棋盘网格图是一个天然的网格图

然后由于选了一个格子四周的四个格子的值都变为 0，而且可以在一个点待着不懂，所以很容易想到这是一个裸的二分图最大权独立集问题

好像布丁怪还蛮可爱的

先将二维问题拍扁到一维序列问题上

对于样例即为：

行：1 2 3 4 5
列：1 4 2 3 5

然后就是要求有多少区间满足 \max-\min=r-l\Leftrightarrow \max-\min-r+l=0

有性质： \max-\min\ge r-l\Leftrightarrow \max-\min-r+l\ge 0

接下来我们固定一个 r，求以 r 为右端点的满足要求的区间数量

由于那个性质，我们可以用线段树维护一个区间最小值，看最小值是否等于 0 即可

接下来，考虑维护 \max 和 \min

然后这个东西可以用单调栈维护，每次有栈的弹出操作的时候区间修改即可

每次将 r 加一的时候所有线段树上的值都要减一，直接区间修改即可

然后很明显这个线段树还要维护一个最小值的个数，所以在合并两个区间的时候更新一下就好了

终于一遍写对网络流了（

双倍经验：Luogu P2763 试题库问题

比较套路的网络流建模

建立 m 个节点代表单位，建立 n 个节点代表桌子

然后源点分配 r_i 容量给每个单位，表示人数；桌子向汇点连 c_i，表示人数限制；单位和桌子之间两两连容量为 1 的边，表示每个餐桌上最多只能有一个同一单位的人，然后跑网络流

考虑输出方案，我们对于每组单位和桌子，记录一个对应在网络流图里的边；这条边满流就说明这个单位有一个人坐了这张桌子

强行三合一差评（

第一问：暴力 dp 即可

第二、三问：把每个可能的 dp 的转移作为一条网络流图里的边，拆点控制每个数选取的次数，跑网络流即可

同「[NOI2006]最大获利」

讲一讲方案的输出

最后输出的所有试验、工具都是残量网络中与源点联通的点，这个结论理解较容易

于是在输出的时候判断最后一遍 bfs 的时候每个节点的 dep 值是否大于 0 即可

区间dp

则 $f_{i,j}=\min\{f_{i,k}+f_{k+1,j},f_{i,k}+2+bit(\frac{j-i+1}{k-i+1})\} 暴力转移即可，时间 $\mathcal O(n^3\log n)

树形dp

设 f^{(i)}_{u,k} 为 u 子树内考虑前 i 个子树走 k 步不回到 u 最多走几步

设 g^{(i)}_{u,k} 为 u 子树内考虑前 i 个子树走 k 步回到 u 最多走几步

接下来考虑转移：

f^{(i)}_{u,k}=\max\{g^{(i-1)}_{u,k-j}+f_{v,j-1},f^{(i-1)}_{u,k-j}+g_{v,j-2}\} g^{(i)}_{u,k}=\max\{g^{(i-1)}_{v,k-j}+g_{v,j-2}\}

初值：f^{(0)}_{u,0}=g^{(0)}_{u,0}=1

复杂度 \mathcal O(n^3)

不会后缀数组，只会后缀自动机（

转化一下柿子：\text{lcp}\to\text{翻转字符串后的 lcs}\to \text{两字符串的 lca}

\text{len(s)}\to\text{parent tree 上的深度}

于是这个柿子就被转化成了 parent tree 上任意两点之间的距离和，计算每条树边对答案的贡献即可

第一问简单贪心

第二问显然是个背包，要求剩下的 \sum a 尽可能小，于是就是选中的 \sum a 尽可能大

f^{(i)}_{k,j}$ 表示前 $i$ 个物品选 $k$ 个并且 $\sum b=j$ 的最大 $\sum a

然后背包转移即可

时间复杂度 \mathcal O(n^2\sum b)，空间复杂度 \mathcal O(n\sum b)

贪心+dp

sz_u$ 为从 $u$ 出发遍历整棵子树最后回到 $u$ 所需时间，显然有 $sz_u=\sum_{v\in son(u)}(sz_v+2)

设 f_u 为 u 子树全部 安装好 游戏所需的时间，有 f_u=\max \{sz^{(i)}_u+f_v+1\}

这里加一是因为 v\to u 已经算在 f_v 里了，无需再加进去

考虑相邻的两个决策点 v_1,v_2，易知先转移 v_2 比先转移 v_1 更优时有 f_{v_1}-sz_{v_1}\le f_{v_2}-sz_{v_2}

排序转移即可，时间复杂度 \mathcal O(n\log n)

挺好玩的一个 dp

$g^{(i)}_{u,k}$ 表示考虑 $u$ 的前 $i$ 个子树，将大于等于 $k$ 级后代中关键节点全部覆盖最少的代价 则 $f^{(i)}_{u,k}=\min\{f^{(i-1)}_{u,k}+g_{v,k},g^{(i-1)}_{u,k+1}+f_{v,k+1},f^{(i)}_{u,k+1}\} g^{(i)}_{u,k}=\min\{g^{(i-1)}_{u,k}+g_{v,k-1},g^{(i)}_{u,k-1}\}

直接转移即可

时间复杂度 \mathcal O(nd)

神一样的树形 dp

$g_{u,k}$ 为以 $u$ 为根的子树中有多少对二元组 $(x,y)$ 满足 $dis_{x\to lca(x,y)}=dis_{y\to lca(x,y)}=dis_{u\to lca(x,y)}+j

于是有转移：

对答案的贡献：f_{u,k-1}\times g_{v,k}\to ans,\ f_{v,k}\times g_{u,k+1}\to ans,\ g_{u,0}\to ans

转移：f_{v,k}\to f_{v,k+1},\ g_{v,k}\to g_{v,k-1},\ f_{v,k}\times f_{u,k+1}\to g_{v,k+1}

发现下标只和深度有关，所以长链剖分优化即可做到 \mathcal O(n)

双倍经验：Luogu P2619 [国家集训队2]Tree I

wqs 二分，给每个黑边设置一个代价跑最小生成树

注意排序的时候要以黑边边权为第二关键字

而上面那个题初始边权可以随机一个，但是尽量大一点

时间复杂度 \mathcal O(n\log n\log w)，w 为边权

树哈希板子，对于每一个节点为根都跑一遍哈希，最后把这些哈希值排序判断两棵树是否同构

哈希直接自然溢出完事（

时间复杂度 \mathcal O(mn^2\log n)

SAM 比较套路的题

对于每个后缀自动机上的节点 u，记 sz_u 为 u 的 right 集合的大小；f_u 为过 u 的字串有多少个

第一次 dfs 在后缀树上统计 sz，第二次 dfs 在后缀自动机上统计 f，第三次 dfs 在后缀树上输出答案，比较类似于平衡树/权值树查询 k 大问题的写法

对于 t=0 的情况，我们直接把 sz 归一即可

时间复杂度 \mathcal O(n)

智商不够，数据结构来凑（

同样地，对于后缀自动机上的节点 u，记 sz_u 为 u 的 right 集合的大小，而 u 能更新的范围即为 [len_{fa_u}+1,len_u]，很容易想到用线段树维护

而求两杯酒乘积的最大值，我们很明显需要维护最大值、次大值、最小值、次小值；在后缀树上 dp 的时候顺便更新一下即可

时间复杂度 \mathcal O(n\log n)

稍微有点卡常差评（

把问题转化为二维体积的 01 背包问题，第一维是集合的总和，第二维是集合中的数可以凑出的和

按照背包问题转移即可

时间复杂度 \mathcal O(n^2k)

同步赛 long long \to int，100\to 20 /dk/dk

第一眼是个费用流，后来发现就是个 DAG 最长路

然后显然这个图可以分层（反正就莫名其妙想到了，鬼知道为啥），边是有向无权边，点上有点权

按照时间分层，u\to v 的权值为 w 的边就在分层图上连 (i,u)\to (i+w,v)，二元组 (i,u) 表示第 i 层的点 u

点权即为到达一个点的收益，美食节直接在对应的点上改即可

然后跑 (0,1)\to (T,1) 的最长路即可

利用拓扑排序即可做到 \mathcal O(Tn+Tm)

然后直接爆炸

然后我又无端联想到了「超级跳马」这个题，于是想到了用矩阵加速

于是便有了一个 (5\times n)\times (5\times n) 的一个矩阵，资瓷 \max 运算和 + 运算

每次美食节直接暴力修改即可做到 \mathcal O(125kn^3\log \frac T k)

然后直接爆炸

然后我又无端联想到了「魔法值」这个题，于是想到了预处理矩阵的 2^i 次幂，k 次矩阵乘法中每次矩阵乘法就由 \mathcal O((5n)^3) 变成了 \mathcal O((5n)^2)

总复杂度 \mathcal O(125n^3\log T+25kn^2\log \frac T k)

即可通过此题

不难的 dp 题

令 f_{i,k} 为当前修到第 i 层，第 i 层修了第 k\in\{0,1\} 种房间的最小代价

容易发现这就是一个序列分段问题，易得 f_{i,k}=\min\{f_{j,k\text{ xor }1}+\text{cost}(j+1,i,k)\}

接下来处理 $\text{cost}$ 函数 很容易发现有一个分界点 $mid=\lfloor\frac{l+r}2\rfloor$ 使得小于等于 $mid$ 的楼层都往 $l-1$ 走，其他的都往 $r+1$ 走，使用二阶前缀后缀和维护即可 $\mathcal O(1)$ 求解 注意特判 $l=1$ 和 $r=n$ 的情况 时间复杂度 $\mathcal O(Tn^2)

首先想到换根dp，但是处理 (x+1)^k 需要二项式展开，复杂度就上去了，还特别麻烦，显然不能直接硬上

于是我们把普通的幂转化为下降幂，有 (x+1)^{\underline k}=x^{\underline k}+kx^{\underline {k-1}}

于是，令 f_{u,k} 为以 u 为根的整棵树的答案，g_{u,k} 为 u 对 u 的父亲的答案的贡献

第一次 dfs，显然有 f_{u,k}=\sum f_{v,k}+k\sum f_{v,k-1}，g_{u,k}=f_{u,k}+k\cdot f_{u,k-1}，特殊处理一下 k=0

第二次 dfs，有 f_{v,k}=f_{v,k}+(f_{u,k}-g_{v,k})+k(f_{u,k-1}-g_{v,k-1})，对于 k=0，有 f_{v,0}=n

接下来，由于我们求的是下降幂，要把它转化为普通的幂，则需要算出第二类斯特林数作为系数

时间复杂度 \mathcal O(k^2+Tnk)

写出每个糖果的生成函数：G_i(x)=1+x+x^2+\cdots+x^{m_i}=\frac{1-x^{m_i+1}}{1-x}

则所有生成函数乘积：G(x)=\frac{\prod (1-x^{m_i+1})}{(1-x)^n}=\prod (1-x^{m_i+1})\sum \binom{n-j-1}{n-1}x^j

记 f(a) 为吃掉至多 a 个糖果的方案数，g(k) 为 \prod (1-x^{m_i+1}) 中贡献的 x^k 的系数

显然 g 可以直接 dfs 求，则 f(a)=\sum g(k)\sum \binom{n-i-1}{n-1}=\sum g(k)\binom {n+a-k}{n}

爆搜的时候统计组合数即可，注意 g 的符号

时间复杂度 \mathcal O(2^nn)

限制条件特别多，所以考虑网络流

发现取了 d_{i,j} 就必须取 d_{i+1,j} 和 d_{i,j-1}，所以很容易想到最大权闭合子图模型

建立 d 之间的后继关系之后还要处理花的钱

对于一次项，我们直接在 d_{i,i} 上减即可；对于二次项，我们新建若干代表编号 a 的节点，权值为 a\times a，并且建立和 d_{i,i} 的后继关系

接下来跑一遍最小割就好了

神仙网络流建模，听说这玩意和线性规划有关？

建立 n 个代表天数的节点，第 i 天和第 i+1 天连边容量为 \infty-a_i，把第 n+1 天当做汇点即可

源点向第 1 天连容量为 \infty 的边

接下来考虑志愿者，对于每个志愿者，连费用为 c_i，容量为 \infty，从 s_i 到 t_i 的边

然后跑费用流即可

简单数学题

首先把 f 转化成下降幂多项式：

\begin{aligned} f(k)&=\sum_{i=0}^{m}a_ik^i\\ &=\sum_{i=0}^m a_i\sum_{j=0}^i \{^i_j\}k^{\underline j}\\ &=\sum_{i=0}^m k^{\underline i}\sum_{j=i}^{m}a_j\{^j_i\}\\ &=\sum_{i=0}^m b_ik^{\underline i} \qquad (b_i=\sum_{j=i}^{m}a_j\{^j_i\}) \end{aligned}

带回原式：

\begin{aligned} \sum_{k=0}^n\sum_{i=0}^m b_i k^{\underline i}x^k\binom nk&=\sum_{k=0}^n\sum_{i=0}^m b_ix^k\binom{n-i}{k-i}n^{\underline i}\\ &=\sum_{i=0}^m b_in^{\underline i}\sum_{k=i}^n\binom {n-i}{k-i}x^k\\ &=\sum_{i=0}^mb_in^{\underline i}x^i\sum_{k=0}^{n-i}\binom{n-i}{k}x^k\\ &=\sum_{i=0}^mb_in^{\underline i}x^i(x+1)^{n-i} \end{aligned}

然后暴力预处理第二类斯特林数和 b 即可

时间复杂度 \mathcal O(m^2)

暴力维护一个动态加边/删边的网络流图

每次用加边来维护导师和学生的优先级，看能否增广，不能增广就删边

第二问二分答案，在二分出来的那张网络流图上继续加边增广

然后用前向星可能会 T，所以用 vector

dsu 裸题，用 map 维护字符串的计数器，记录一下深度即可

时间复杂度 \mathcal O(n\log^2 n)

还是 dsu 裸题，只是这里要记录的是计数器的后缀和

于是开一个权值树状数组维护即可

时间复杂度 \mathcal O(n\log ^2n)

首先发现 m 很小，于是直接对于每一个箱子状压

于是问题转化为选若干个数使它们按位或为全集

继续转化一下，把每个箱子取个反，问题就变成了选若干个书使它们按位与为空集

接下来考虑 dp

f_i$ 表示状态 $i$ 是多少个箱子状态的子集，$g_i$ 表示状态 $i$ 是多少个状态交集的子集，显然有 $g_i=2^{f_i}-1$，于是我们只需要计算 $f

有方程：f_i=\sum_{i\in j}f_j，于是直接上 sos dp 即可

注意这里与标准 sos dp 方程 f_i=\sum_{j\in i}f_j 有区别，在实现的时候反一下就行了

计算出来 f 和 g 之后计算答案

答案要求按位与为空集，考虑容斥，全集即为 g_0

对于一个状态 i，若它有奇数个 1，则需要从答案里减去 g_i，否则就加上 g_i

于是这道题就被做完了，时间复杂度 \mathcal O(2^nn)