做题笔记 2023.2 Part 2
CF1784D Wooden Spoon
这类问题通常可以按两种顺序 dp，本题中我们需要限制每组中最小的数依次递减，一种显然的想法是从大到小 dp，对于每个数考虑该数是与之前的某些数构成一组还是不做任何操作，类似于 ARC093F，当然由于我们需要对第一个数的每种取值计算方案数，所以 dp 需要反向，转移过程中的组合系数可能会很反常。另一种是从后向前，从小到大 dp，在填数的过程中留下一些空位，在后期对每个数决策是去填上之前的空位还是新开一组。两种方法都是 $O(n2^n)$ 的。
各种划分类型的 dp，如果每一组的贡献只与某个元素有关，或者我们可以很方便的将一个元素加入一个组，我们会倾向于对于单个元素进行决策，这样往往复杂度更优，本质上是因为如果我们去枚举具体的划分方案就记录了多余的信息。
LG3354 [IOI2005] Riv 河流
一种显然的想法是设 $f_{i,j,k}$ 表示 $i$ 子树内建造了 $j$ 个伐木场，此时手里拿着的木料块数，但是由于木料块数值域过大，时空复杂度都无法接受，一种可行的思路是将 $k$ 的含义转化为距离下一个伐木场的距离（边数），当 $k=0$ 时强制在此处修建一个伐木场，相当于是在 dp 时提前进行了后面的决策，这样即可通过本题。本质上，单个村庄内木料的贡献为 木料个数 $\times$ 到上方伐木场的距离，由于木料个数不好统计，所以我们转而在状态中记录距离。
CF1788F Xor, Tree, and Queries
看到路径上边权的异或和，由于异或优秀的性质，我们考虑对每个点记录该点到根路径上所有边权的异或和 $p_u$，这样 $(u,v)$ 路径上所有边权的异或和可以表示为 $p_u\oplus p_v$。所有限制也可以抽象成一张图，我们先 dfs 随便构造一组方案，同时在此时判掉无解的情况，接下来考虑如何最小化答案。$a_i=p_{x_i}\oplus p_{y_i}$，那么如果我们将所有 $a_i$ 异或在一起，不难发现只有奇度点是有贡献的，另外注意到在限制图中一个连通块内所有的值都是一起变化的，我们只能将一个联通块内的所有数同时异或上一个数，于是如果一个连通块内有偶数个奇度点，这些奇度点的异或和我们是无法更改的。那么只要存在一个连通块内有奇数个奇度点，我们就可以将答案变为 $0$。注意 $p_1=0$，这个是无法更改的。
LG3175 [HAOI2015] 按位或
所有位都变成 $1$ 的期望时间，那么如果我们将第 $i$ 位变为 $1$ 的时间设为 $t_i$，我们要求的实际上是 $\mathbb{E}[\max_i\{t_i\}]$，注意在期望中不能直接拆掉 $\min,\max$，考虑使用 min-max 容斥，而这里 $\min$ 的意义就是我们取出某些位，这些位中第一次有某位变成 $1$ 的期望时间，这个模型服从几何分布，考虑计算随机选取集合与当前集合有交的概率 $p$，期望时间即为 $1/p$，除了可以去算无穷级数外，解方程也可以得出这个答案：
$$
\mathbb{E}(X)=(1-p)(\mathbb{E}(X)+1)+p
$$
假人
Description
$n$ 个人，第 $i$ 个人手上拿着 $k$ 道题，第 $j$ 道题长度为 $j$（1-index），权值为 $a_{i,j}$。
从每个人手中恰好选取一道题，对于每个 $x\in[n,\sum k]$，计算所有题目长度和为 $x$ 的最大权值。
$n\le 10^5,k\le 5$
Solution
将长度值域的 $[1,5]$ 变为 $[0,4]$。
设 $f_{i,j}$ 表示考虑了前 $i$ 个人，长度和为 $j$ 的最大权值，一个结论是将 $f_i$ 按照 $j\bmod 12$ 分组，每组都是凸的。
考虑证明这个凸性，证明思路是，如果我们能将任意一个长度增加 $24$ 的过程分解成两个长度增加 $12$ 的过程，我们一定是先选择权值大的一组，再选择权值小的一组，这样贡献一定是单调不增的，而不难发现对于任意一个任意元素在 $[0,4]$ 中，和为 $24$ 的可重集合一定能划分为两个和为 $12$ 的集合（感性理解 / 程序验证），这样就证明了凸性。
那么我们可以将 dp 数组表示为 12 个凸包，分治，闵可夫斯基和合并凸包即可。
闵可夫斯基和是坐标对一个相加，当我们的 dp 有凸性且可以转化为两维对应相加求最值时就可以使用闵可夫斯基和了。
小 T 与灵石
Description
给出若干点集，对于每个点计算 到每个点集中点距离最大值 的最小值。
距离为最短路径上的边数。
Solution
每个点集中只有直径的两个端点有用，接下来我们要求每个点到达与自己距离较远的直径端点，换言之，我们需要强制每个点经过直径中点，考虑取出直径中点，在这里挂出一个新点并将边权设为直径长度的一半，如果直径长度为奇数，就在中间边的两个端点上都挂一个新点即可。将所有新建点一起设为起点跑一次最短路即可。
LG5298 [PKUWC2018] Minimax
因为这题是 cmd blog 里线段树合并的一个例题，拿到这题的时候知道应该用线段树合并，所以就秒了。不难想到设 $f_{u,i}$ 表示 $u$ 权值为 $i$ 的概率，不难发现初始一共只有 $O(n)$ 个点值，剩下的就是对 dp 数组进行合并，于是使用线段树合并即可，需要在合并过程中维护一个前缀和。
当 dp 是对初始若干个点值进行合并，同时转移方程有很好的性质（对应相加，前缀和，全局加等等），我们就可以使用线段树合并进行优化。
CF932F Escape Through Leaf
设 $f_u$ 表示 $u$ 到任意叶子的最小花费，有转移：
$$
f_u=\min_{v\in \mathrm{subtree}_u}\{f_v+a_u\cdot b_v\}
$$
斜率优化时我们考虑将每个已经计算好的 dp 值看作一个点，每次转移看作用直线去切凸包（把 dp 值放在 $b$ 的位置），这里由于横坐标没有单调性，所以无法直接使用斜率优化，我们考虑李超树。
使用李超树时，我们转而考虑将己经计算好的 dp 值看作一条直线，转移看作单点求值，这样即可方便的用李超树维护。本题中将 $b_v$ 看作 $k$，$f_v$ 看作 $b$ 即可。
合并两棵李超树时可以直接套用线段树合并，将线段在李超树上能被下放的次数设为势能函数，每个线段只可能往某一棵子树下放，不难发现总复杂度为 $O(n\log n)$，也可以直接启发式合并做到 $O(n\log^2 n)$。
CF1792F1 Graph Coloring (easy version)
一个结论是，如果我们取完全图的一个生成子图，它不连通，则他的补图一定是连通的，证明显然。
于是我们其实只用关心不连通的颜色，另一种颜色一定是连通的。红蓝等价，不妨设不连通的颜色为蓝色。
考虑 dp，设 $f_i$ 表示 $i$ 个点的完全图不蓝联通的方案数，转移时考虑 $1$ 所在的蓝连通块，枚举连通块大小，剩余部分可以蓝连通（对应一个蓝连通块）也可以红连通（对应多个蓝联通块），块间的边都是红边。
复杂度 $O(n^2)$。
CF1789F Serval and Brain Power
看到这题会感觉好像没什么思路，看到数据范围很小，考虑一种类似根号分治的暴力。
如果序列只被分成了 2 或 3 段，那么我们可以 dp 求出答案。4 段的情况被 2 段包含。
接下来只考虑 5 段以上的情况，将序列均分成 5 块后，循环节一定在某个段内，所以枚举所有可能的子序列然后子序列自动机匹配（贪心）计算答案即可。
看到这种似乎只能暴力的题不妨往根号分治或类似的方法上思考。
CF526F Pudding Monsters
首先将题目描述的网格拍扁成一个排列，问题被转化为满足 $\max-\min+1=len$ 的区间数。
数区间，我们考虑类似扫描线的方法，枚举右端点，然后数据结构维护每个左端点的信息。这里直接线段树维护即可。后缀最大值 / 最小值可以直接单调栈然后在线段树上区间加减，如果用 segbeats 多一个 $\log$。
将式子化为 $\max-\min+1-len=0$，接下来我们希望数线段树上某个值的个数，这是不好做的，但是不难发现 $\max-\min+1-len\ge 0$，所以我们转而数最小值个数，这样这题就做完了，复杂度 $O(n\log n)$。
CF997E Good Subsegments
在上一题的基础上，我们要求进行区间查询。沿用上一题的做法，我们现在要统计多个右端点时的答案，也就是结点信息的历史版本和。
历史版本和的套路是，我们将版本更新视作标记打在线段树上，具体的，用一个 tag 表示当前结点处延迟了多少次版本更新操作，在本题中，我们统计的是最小值的个数，修改操作是区间加减，所以对某个结点修改并不会造成被统计信息的变化，于是我们不用再记录更多的信息。如果统计信息是区间和，修改操作是区间加减，我们还需要维护每次版本更新时加法标记的总和，这样才能下放标记。
本题中还要注意版本更新标记只会下放给最小值和当前结点相同的儿子，实际上我们统计的是最小值为 0 的结点的信息，不过由于可能 pushdown 是在修改过程中进行，所以我们不能直接判断 mn == 0。
历史信息问题通常很难理清思路，做线段树题很重要的一点是要聚焦于儿子信息能否正确合并，以及标记是否能正确下放给儿子上，视角不能太宏观，要不然想不明白。
nnntxdy
Description
$n$ 个正整数 $a_{1\dots n}$，$m$ 次操作，每次操作随机从 $>0$ 的数中选出一个将其减一，求期望有多少个数被减到了 $0$。
保证 $m\le \sum a_i$。
Solution
难点在于，由于不断有数被减到 $0$，概率也在不断变化，一种直接的想法是我们要在 dp 中记录一维 $S$ 表示集合中的数都被删光了，但这样还是不行，因为我们每次随机选取一个数，但不知道这个数减完之后会变成多少，没办法更新 $S$。
这里的技巧是，我们并不在每次操作时对操作对象进行决策，考虑两种转移，一种是当前操作对象没被减到 $0$，一种是被减到 $0$ 了，第一种转移我们将操作对象视作待定，第二种转移我们考虑从前面还没有确定的操作中挑出 $a_i-1$ 个作用在自己身上，相当于是一种延迟的思想。dp 结束后还会剩下一些操作，这些操作都不会将数删光，再做一次背包即可。
可以使用 meet in the middle 优化。
脑力
Description
$n$ 个长度为 $m$ 的由小写字母构成的字符串，其中有些位置是问号，在问号处随机填上小写字母，将所有字符串插入字典树，问期望结点个数。
$1\le n\le 12,1\le m\le 1000$
Solution
直接 dp 很难做，因为转移过程中我们需要将集合划分成若干子集，这很难处理。
考虑容斥。字典树是一个天然的容斥结构，和容斥原理的定义式类似，字符串的并就是字典树，字符串的交是他们的 $\mathrm{lcp}$，于是现在我们只需要求若干字符串的期望 $\mathrm{lcp}$ 长度，这就很好做了。
最后的复杂度是 $O(nm2^n)$。
这里正难则反的容斥思想非常重要，划分是不好做的，但交是容易处理的。
CF1796D Maximum Subarray
大概有三种做法。
看到最大子段和，考虑前缀和之后转化为一个求前缀 $\min$ 的问题。
于是第一种考虑 dp，设 $f_{i,j}$ 表示前 $i$ 个数中有 $j$ 个数 $+x$ 能达到的最小前缀和，转移考虑当前位置 $+x$ 或 $-x$，当前位置的前缀和可以直接计算，边转移边用 $sum'_i-f_{i,j}$ 更新答案即可。代码非常短。复杂度 $O(nk)$。
接下来两种做法，我们考虑若 $x<0$，令 $x\gets -x,k\gets n-k$。
第二种做法，我们发现被 $+x$ 的一定是序列上的一个连续段，证明考虑调整法，将 $+x$ 的位置放在一起一定不劣，于是枚举连续段的位置，用线段树单点修改并维护全局最大子段和即可，复杂度 $O(n\log n)$。不会维护最大子段和可以去看维护序列那个题。
第三种做法，如果我们选出的子段长度 $\le k$，我们一定会将每个元素 $+x$，那么相当于求原序列上所有长度 $\le k$ 的最大子段和，前缀和之后滑动窗口最值即可，这部分如果用单调队列是线性的，如果用 multiset 则多一个 log。如果选出的子段长度 $>k$，那么将会有 $k$ 个元素 $+x$，$len-k$ 个元素 $-x$，具体的，$[l,r]$ 的子段和为 $sum_r-sum_{l-1}+kx-(r-l+1-k)x=sum_r+(2k-r)x-(sum_{l-1}+(l-1)x)$，于是我们在向右移动 $r$ 的时候动态维护 $sum_{l}+lx$ 的最小值即可，$l$ 满足 $r-l>k$。复杂度视实现为 $O(n)$ 或 $O(n\log n)$。
CF1799F Halve or Subtract
有的数会既使用 half 又使用 sub，这是不方便处理的，所以我们考虑枚举使用两种操作的数的个数。另外注意到如果一个数使用了两种操作，一定是先 half 再 sub，同时使用两种操作的数一定应该尽可能大，这很符合直觉，官方题解提供了证明，以 casework 为主，这里就不赘述。
我不知道为什么我想到这就不想往下了，其实后面非常简单。
一种是按照题解做法，发现将所有剩余的数从大到小排序后，一定可以被分为三段，分别使用 half - sub - half 操作，被操作的数都是越大越好，直接暴力枚举第一段的长度即可。
另一种是考虑贪心。先让所有数使用 half，然后根据 delta 从大到小选择一些数使用 sub。
除此之外还有一种做法，考虑暴力 dp，设 $f_{i,j,k}$ 表示考虑前 $i$ 个数，half 和 sub 操作分别使用 $j$ 和 $k$ 次可以达到的最优答案，从若干个数中独立的选出一些进行操作，这样的形式显然是满足凸性的，因为我们一定会先选择较优的数，于是用 wqs 二分可以去掉两维，复杂度为 2log。
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
