2022.11 做题记录

CF1572E Polygon

问分割出图形面积最小值的最大值，容易想到二分答案．

考虑对一个确定的面积最小值 $s$ 进行检验，观察到切割的轨迹不能相交，而题目中的点又按照逆时针方向给出，所以可以对点的序列 $A_i$ 进行区间 dp．

设 $f_{l,r}=(x,y)$ 表示在 $[l,r]$ 这一区间中最多可以切割出 $x$ 块，目前未被切割到任意多边形内的最大面积为 $y$，那么我们最后只需要检查 $s+1\le x_{f_{1,n}}$ 即可．

考虑转移，如果对于一个 $k\in [l,r]$，我们可以计算 $\triangle A_lA_kA_r$ 的面积，然后决定是将它并入空闲区域或是将其和以前的空闲区域合并为一个新多边形，具体如下：

$$f_{l,r}\leftarrow \max_{k\in[l,r]} \left\{ \begin{cases} \left(x_{f_{l,k}}+x_{f_{k,r}}+1,0\right) & \text{if }s \le y_{f_{l,k}}+y_{f_{k,r}}+S_{\triangle a_la_ka_r} \\ \left(x_{f_{l,k}}+x_{f_{k,r}},y_{f_{l,k}}+y_{f_{k,r}}+S_{\triangle a_la_ka_r}\right) & \text{otherwise} \end{cases} \right\}$$

其中对二元组的比较定义为先比较第一个元素再比较第二个元素．

UVA10288 Coupons

设 $p_i$ 表示选到第 $i$ 个数的概率，$\epsilon_i$ 表示选到第 $i$ 个数的次数期望，显然有 $p_i=\frac{n-i+1}{n}$．

所以我们有：

$$\begin{aligned} \epsilon_i &= \sum_{i=1}^\infty i\times(1-p_i)^{i-1}\times p_i \\ &= p_i\sum_{i=1}^\infty i\times(1-p_i)^{i-1} \end{aligned}$$

令 $\displaystyle u=\sum_{i=1}^\infty i\times(1-p_i)^{i-1}$，我们有：

$$\begin{alignedat}{} && u &= \sum_{i=1}^\infty i\times(1-p_i)^{i-1} \\ & \Rightarrow & (1-p_i)\times u &= \sum_{i=1}^\infty i\times(1-p_i)^i \\ & \Rightarrow & u-(1-p_i)\times u &= \sum_{i=0}^\infty (1-p_i)^i \\ & \Rightarrow & p_i\times u &= \frac{1}{1-(1-p_i)} = \frac{1}{p} = \epsilon_i \\ \end{alignedat}$$

那么答案即为：

$$\sum_{i=1}^{n}\frac{n}{n-i+1}$$

P3147 [USACO16OPEN] 262144 P

由其 弱化版 可知，我们考虑 dp．

设 $f_{i,j}=k$ 表示区间 $[j,k]$ 可以合并出 $i$，那么我们有：

$$f_{i,j}\leftarrow f_{i-1,f_{i-1,j}}$$

答案取值在区间 $[0,58]$ 内，所以我们枚举答案 $x$，检验是否存在 $y\in[1,n]$ 使得 $f_{x,y}\not=0$，若存在这样的 $y$，这个答案就可行．

P4211 [LNOI2014] LCA

询问显然可以差分．

对于两个点 $u,v$ 的 lca $w$，从根到 $w$ 的链上所有的点对 $w$ 的深度的贡献为 $1$，所以可以将根到 $u$ 的链上所有点的点权加 $1$，然后统计根到 $v$ 的链上所有点的点权和，算出来的值即为 $w$ 的深度．

那么对于区间 $[l,r]$ 中的所有点与 $u$ 这个点的所有 lca 深度的和，我们容易想到可以将根到区间 $[l,r]$ 中的点的链上的所有点的点权加 $1$，然后统计根到 $u$ 的链上的点权和，算出来的值即为询问的答案．

由于我们拆开了询问，我们只需要按序给根到 $1\sim n$ 的链上点加 $1$，然后记录答案．有点像扫描线？

对于类似的询问都可以采用类似的套路，只需要考虑根到 lca 的链上的点对 lca 的答案的贡献，然后结合合适的数据结构维护．

P5305 [GXOI/GZOI2019]旧词

观察到这个问题的形式与 P4211 [LNOI2014] LCA 类似，采用套路解决．

考虑在原题中对根到点路径加 $1$ 的本质，是因为这个点相较其父亲的深度增加了 $1$，那么在本题中自然可以想到将对 $x$ 加 $1$ 变成加 $\mathrm{depth}(x)^k-(\mathrm{depth}(x)-1)^k$．

线段树上多维护一个值，代表区间内每次加的贡献的和，就可以维护．

P3396 哈希冲突

一般的数据结构做这个问题十分困难，我们考虑根号分治．

设定一个阈值 $w$，当模数 $p\le w$ 时，我们预处理答案；当 $p>w$ 时，我们暴力回答．

预处理答案的复杂度为 $O\left(nw\right)$．

询问时，当 $p\le w$，可以 $O(1)$ 回答，而当 $p>w$ 时，最多只有 $n/w$ 个数对答案造成贡献，所以复杂度为 $O(n/w)$．

修改时，直接暴力修改，复杂度为 $O(n/w)$．

$w=\sqrt{n}$ 时复杂度最优，总复杂度为 $O(n\sqrt{n})$．

P2890 [USACO07OPEN] Cheapest Palindrome G

设 $f_{l,r}$ 为将区间 $[l,r]$ 内变为回文串的最小花费．

记 $w_{i,0}$ 为添加 $i$ 的花费，$w_{i,1}$ 为删除 $i$ 的花费．

对于一个区间 $[l,r]$，转移时我们考虑在删除 $s_l$，或者在 $r$ 的左边插入 $s_l$，对于右端点做同样的讨论．

当 $s_l=s_r$ 时，我们可以直接从 $f_{l+1,r-1}$ 转移．

所以我们有如下转移：

$$f_{l,r}=\min \left\{ \begin{aligned} & f_{l+1,r}+c_{s_l,0}, \\ & f_{l+1,r}+c_{s_l,1}, \\ & f_{l,r-1}+c_{s_r,0}, \\ & f_{l,r-1}+c_{s_r,1}, \\ & \begin{cases} f_{l+1,r-1} & \text{if } s_l=s_r \\ \infty & \text{otherwise} \end{cases} \end{aligned} \right\}$$

答案即为 $f_{1,m}$．

CF607B Zuma

设 $f_{l,r}$ 表示将区间 $[l,r]$ 变成回文串或者消掉的最小代价，答案即为 $f_{1,n}+1$．

在合并两个已经成为回文串的区间 $[l,k],[k,r]$ 时，我们可以任选其中一个消掉. 所以新状态是 $f_{l,k}+f_{k,r}+1$．

所以我们有转移：

$$f_{l,r}\leftarrow\min \left\{ \begin{aligned} & \min_{k\in[l,r]}\{f_{l,k}+f_{k,r}+1\}, \\ & \begin{cases} f_{l+1,r-1} & \text{if }a_l=a_r \\ \infty & \text{otherwise} \end{cases} \end{aligned} \right\}$$

CF797E Array Queries

设 $f_{i,j}$ 表示 $p=i,k=j$ 时的答案，我们做如下递推：

$$f_{i,j}= \begin{cases} f_{i+a_i+j,j}+1 & \text{if }i+a_i+j\le n \\ 1 & \text{otherwise} \end{cases}$$

暴力求解或全部预处理均不可行，我们考虑根号分治．

我们考虑设定一个阈值 $w$，只预处理到 $f_{n,w}$，这样预处理的复杂度是 $O(nw)$．

而当回答询问时，若 $k\le w$，回答复杂度为 $O(1)$，当 $k>w$ 时，暴力回答，复杂度为 $O(n/w)$．

当 $w=\sqrt{n}$ 时，复杂度最优．

时间复杂度为 $O(n\sqrt{n})$.

P2679 [NOIP2015 提高组] 子串

设 $f_{i,j,k,0/1}$ 表示当前考虑到 $A$ 串的第 $i$ 位，$B$ 串的第 $j$ 位，已经使用了 $k$ 个子串并且选 / 不选当前字符的方案数．

转移时讨论是否选取当前字符：

1. 如果不选，则方案数就是第 $i-1$ 位选或不选方案数之和．
2. 如果选，当 $A_i\not=B_j$ 时，方案数为 $0$；当 $A_i=B_j$ 时，方案数为第 $i$ 位作为新子串，选 / 不选第 $i-1$ 位时的方案数与第 $i$ 位不作为新子串的方案数之和．

那么我们有如下转移：

$$\begin{aligned} f_{i,j,k,0} &\leftarrow f_{i-1,j,k,0}+f_{i-1,j,k,1} \\ f_{i,j,k,1} &\leftarrow \begin{cases} f_{i-1,j,k,1}+f_{i-1,j,k-1,0}+f_{i-1,j,k-1,1} & \text{if }A_i=B_j \\ 0 & \text{otherwise} \end{cases} \end{aligned}$$

P2757 [国家集训队] 等差子序列

我们只需要确认序列中是否有长度为 $3$ 的等差子序列即可回答询问．

对于原序列的前缀 $a_{1\cdots x}$，我们考虑一个 $01$ 序列 $\{b_i\}$，其中 $b_i$ 表示在该前缀中是否存在 $i$ 这个值．

我们发现如果原序列中存在长度为 $3$ 的等差数列，那么必然存在 $a_x-k,a_x+k$ 在 $a_x$ 的两侧，而此时必然有 $\forall k\in[k-\min\{n-x,x-1\},k+\min\{n-x,x-1\}],b_{a_x-k}\land b_{a_x+k}=0$，也就是说，$b$ 序列上区间 $[k-\min\{n-x,x-1\},k+\min\{n-x,x-1\}]$ 必然不是回文的．

可以使用哈希来判断回文．

P3792 由乃与大母神原型和偶像崇拜

考虑哈希，令我们的哈希函数 $h(x)=x^2$．

设区间 $[l,r]$ 的最小值为 $x$，最大值为 $y$，那么显然有 $\displaystyle\sum_{i\in[l,r]} h(a_i)=\sum_{i\in[x,y]}i^2$，容易维护左式的值，右式可以利用平方和公式进行计算．

方便求和且不容易被卡的函数都可以当作 $h(x)$．

P5278 算术天才⑨与等差数列

联想到 P3792，我们尝试用同样的哈希方法来解决这个问题．

注意到：

$$\begin{aligned} \sum_{i=0}^{r-l} (ki+b)^2 &= \sum_{i=0}^{r-l} k^2i^2+2kbi+b^2 \\ &= (r-l+1)b^2+kb(r-l)(r-l+1)+k^2\sum_{i=0}^{r-l}i^2 \end{aligned}$$

所以首项，公差确定的等差数列的和是可以直接计算的，那么把区间最小值作为首项，计算和与区间的哈希值，判断是否相等即可．

CF911G Mass Change Queries

注意到 $a_i\le 100$，我们可以给序列中的每个值开 $1$ 棵线段树，修改直接把值对应线段树的区间分裂出来，然后合并到另外的那个线段树上即可．

CF149D Coloring Brackets

记 $p_i$ 为位置 $i$ 上的括号所配对括号的位置．

设 $f_{l,r,a,b}$ 表示当前考虑到区间 $[l,r]$，左端点染成 $a$，右端点染成 $b$ 时的方案数．

所以当 $l,r$ 匹配时，我们有转移：

$$\begin{aligned} f_{l,r,1,0} &\leftarrow \sum_{ \begin{subarray}{l} i\not=1 \\ j \end{subarray}} f_{l+1,r-1,i,j} \\ f_{l,r,2,0} &\leftarrow \sum_{ \begin{subarray}{l} i\not=2 \\ j \end{subarray}} f_{l+1,r-1,i,j} \\ f_{l,r,0,1} &\leftarrow \sum_{ \begin{subarray}{l} i \\ j\not=1 \end{subarray}} f_{l+1,r-1,i,j} \\ f_{l,r,0,2} &\leftarrow \sum_{ \begin{subarray}{l} i \\ j\not=2 \end{subarray}} f_{l+1,r-1,i,j} \\ \end{aligned}$$

而当 $l,r$ 不匹配时，我们枚举 $l,r$ 的颜色 $a,d$：

$$f_{l,r,a,d}= \sum_{ \begin{subarray}{l} b\not=0 \\ c\not=b \end{subarray} } f_{l,p_l,a,b}\times f_{p_l+1,r,c,d}$$

答案即为：

$$\sum_{i,j} f_{1,n,i,j}$$

P3990 [SHOI2013] 超级跳马

首先我们有一个朴素 dp 方法. 设 $f_{i,j}$ 表示跳第 $i$ 行第 $j$ 列的方案数，我们有转移：

$$f_{i,j}=\sum_{p}f_{i-1,j-(2p+1)}+f_{i,j-(2p+1)}+f_{i+1,j-(2p+1)}$$

然后我们发现只有列编号的奇偶性与 $j$ 相同的点才会影响转移，于是我们重新设 $\displaystyle g_{i,j}=\sum_{k\bmod2=j\bmod2}f_{i,k}$．

然后我们有转移：

$$s_{i,j}=s_{i,j-1}+s_{i-1,j-1}+s_{i+1,j-1}+s_{i,j-2}$$

发现 $n\le 50$，允许我们把 $s$ 的转移表达成矩阵．

P2470 [SCOI2007] 压缩

设 $f_{l,r}$ 表示区间 $[l,r]$ 内不存在 $\texttt{M}$ 时压缩的最短长度，$g_{l,r}$ 表示区间 $[l,r]$ 内存在 $\texttt{M}$ 时压缩的最短长度．

如果当前考虑到的区间 $[l,r]$ 的前半段和后半段相同，显然可以在 $l-1$ 处插入 $\texttt{M}$，那么我们可以写下这样的转移：

$$f_{l,r}\leftarrow \min\{f_{l,r},f_{l,(l+r)/2}+1\}$$

然后考虑从上几个区间的答案转移过来．

当转移 $f$ 时，由于我们不能在区间 $[l,r]$ 内插入 $\texttt{M}$，所以我们有如下转移：

$$f_{l,r}\leftarrow \min_{k\in(l,r)}\{f_{l,k}+r-k\}$$

转移 $g$ 时，区间 $[l,r]$ 内可以随便插 $\texttt{M}$，此时转移的两个区间之间需要插入一个 $\texttt{M}$，所以我们有如下转移：

$$g_{l,r}\leftarrow \min_{k\in(l,r)}\{\min\{f_{l,k},g_{ll,k}\}+\min\{f_{k+1,r},g_{k+1,r}\}+1\}$$

答案即为 $\min\{f_{1,n},g_{1,n}\}$．

P3800 Power 收集

有一个朴素的 dp 想法，设 $f_{i,j}$ 为当前在第 $i$ 行第 $j$ 列所能收集到的最大 POWER 值，转移如下：

$$f_{i,j}=\max_{k\in [j-t,j+t]}\{f_{i-1,k}+v_{i,j}\}$$

其中 $v_{i,j}$ 代表第 $i$ 行第 $j$ 列的 POWER 值．

容易发现这样做的复杂度瓶颈在于求 $\displaystyle\max_{k\in [j-t,j+t]}f_{i-1,k}$ 的过程，我们使用单调队列维护．

P2254 [NOI2005] 瑰丽华尔兹

考虑对于时间段来 dp．

记 $s_i$ 代表第 $i$ 段时间的开始， $t_i$ 代表第 $i$ 段时间的结束．

设 $f_{i,x,y}$ 代表第 $i$ 段时间处于位置 $(x,y)$ 时的最大滑行长度，枚举当前时间段已经经过的时间 $t$，我们有如下转移：

$$f_{i+1,x^{\prime},y^{\prime}} \leftarrow \max_{p\in[1,t_i-s_i+1]} f_{i,x,y}+p$$

其中 $x^{\prime},y^{\prime}$ 为经过 $p$ 时间后的坐标．

其实这玩意复杂度是错的但是可以通过本题．

P3237 [HNOI2014] 米特运输

容易发现，树上任意一个节点的点权确定了，全部点的点权就确定了．

令 $g_u$ 表示 $u$ 节点点权不变时，根节点的点权．记点 $u$ 的儿子个数为 $C_u$，根到点 $u$ 的链上所有点构成的集合为 $F_u$，我们有如下递推：

$$g_u=a_u\times\prod_{f\in F_u} C_f$$

答案即为 $n$ 减去 $g_u$ 中众数的出现次数．

P4592 [TJOI2018] 异或

对于子树内询问，把树拍成 dfs 序然后在序列上使用可持久化 Trie 树维护．

对于链询问，采用类似 Count on a tree 的树上差分的方法，同样使用可持久化 Trie 树维护．

P5283 [十二省联考 2019] 异或粽子

首先做一个前缀异或和，记 $\displaystyle s_x=\bigoplus_{i=1}^x a_i$，这样问题就变成了求前 $k$ 大的 $s_i\oplus s_j,1\le i\le j\le n$ 的和．

发现这是对一个上三角区域求和，而我们有 $x\oplus x=0$，所以我们可以求前 $2k$ 大的 $a_i\oplus a_j,1\le i,j\le n$ 的和，最终将答案除 $2$．

实现上，我们维护一个大根堆，堆中初始插入 $s_i,1\le i\le n$ 与 $s$ 中元素异或的最大值．每次我们取出堆顶，若堆顶元素是 $s_i$ 与 $s$ 中元素异或的第 $k$ 大值，我们就将其与 $s$ 中元素异或的第 $k+1$ 大值插入堆中．

这样进行的第 $k$ 次操作，取出的就是 $s_i\oplus s_j,1\le i,j\le n$ 的第 $k$ 大值．做 $2k$ 次这样的操作，每次累计取出的值，最后除以 $2$ 即可．

P2048 [NOI2010] 超级钢琴

先做一个前缀和，记 $\displaystyle s_x=\sum_{i=1}^x a_i$．

对于一个左端点 $x$，由它开始的美妙度最大的超级和弦为 $\displaystyle\max_{i=x+L-1}^{x+R-1}\{s_i-s_{x-1}\}=\max_{i=x+L-1}^{x+R-1}\{s_i\}-s_{x-1}$．可以使用线段树或者 ST 表这样的数据结构来加速 $\max$ 的查询．

对于题目的询问，我们只需要找到美妙度前 $k$ 大的超级和弦，将其美妙度求和即可．

实现上我们维护一个大根堆，堆中初始插入以 $i,i\in[1,n-L+1]$ 为起始点的美妙度最大的超级和弦，以其美妙度为 key． 每次我们取出堆顶，将其右端点对应的合法区间以当前选取的右端点断开，然后将右端点分别在断开后的两个区间内的美妙度最大的超级和弦插入堆中．这样进行的第 $k$ 次操作，取出的就是美妙度第 $k$ 大的超级和弦，累计即可求出答案．

CF833B The Bakery

记区间 $[l,r]$ 中的颜色数为 $w(l,r)$．

设 $f_{i,j}$ 表示前 $j$ 个数，分 $i$ 段的最大价值．枚举当前点 $x$，考虑是否断开，我们有如下转移：

$$f_{i,j}\leftarrow\max_{x\in[1,j]}\{f_{i-1,x-1}+w(x,j)\}$$

这样做是 $O(n^2k)$ 的，显然会 TLE．我们考虑如何优化转移．

记 $a_x$ 上一次在序列中出现的位置为 $p_x$．

枚举 $j$ 的过程中，$\forall x\in[p_x+1,x],f_{i-1,x}\leftarrow f_{i-1,x}+1$，此时 $\displaystyle f_{i,j}\leftarrow\max_{x=1}^jf_{i-1,j}$，这一过程可以用线段树维护．

时间复杂度 $O(nk\log n)$．

P4137 Rmq Problem / mex

有一个显然的莫队做法．很遗憾，是假的．正确的莫队做法我不会．

询问右端点 $r$ 固定时，每个左端点 $l$ 的答案就是第一个最后一次出现位置小于 $l$ 的值．

询问离线之后挂在右端点上扫描线或者使用可持久化线段树都可以实现．

[SDOI2009] HH的项链

区间数颜色，但是 $n\le{10}^6$．

考虑右端点 $r$ 固定时，如何对每个左端点 $l$ 计算答案．容易发现，对于一个颜色 $x$，只有在 $r$ 前面最后一次出现的 $x$ 才会对答案造成贡献，所以，对于所有的 $x$，我们将其在 $r$ 前面最后一次出现的位置置 $1$，其他出现的位置置 $0$，询问就变成了区间求和问题．

可以采用扫描线或者可持久化线段树实现．

P2473 [SCOI2008] 奖励关

记所有可能的宝物选取状态构成的集合为 $S$．

容易设出 $f_{i,T}$ 表示当前在第 $i$ 轮，选取状态为 $T$ 时获得分值的期望．但是这样设状态有一个问题：第 $i$ 轮不一定能到达状态 $T$．这样的话我们的期望计算会出错．

所以我们改变设的状态，设 $f_{i,T}$ 表示 $1\sim i$ 轮宝物的选取状态为 $T$，$i\sim k$ 轮得分的最大值．

枚举这一步选取的宝物 $j$，我们有如下转移：

$$\forall T\in S,f_{i,T}\leftarrow f_{i,T}+\frac{1}{n}\times \left( \begin{cases} \max\{f_{i+1,T},f_{i+1,T\cup \{j\}}\} & \text{if }s_j\subset T \\ f_{i+1,T} & \text{otherwise} \end{cases} \right)$$

实现上，注意到 $n\le 15$，我们将选取状态压缩到一个 uint32_t 内．

P4396 [AHOI2013] 作业

去除 $a,b$ 的限制，问题就是区间求和区间数颜色，所以我们考虑莫队维护．

我们可以维护两个序列 $s,t$，$s_x$ 代表当前区间 $x$ 的出现次数，$t_x$ 代表当前区间 $x$ 是否出现，容易想到左右端点的转移．

如果每次暴力统计答案，复杂度是 $O(nV\sqrt{m})$，其中 $V$ 是值域，显然会 TLE．

我们可以发现，每次统计答案相当于对两个序列的区间 $[a,b]$ 进行求和操作，所以我们可以使用一些数据结构来维护两个序列．

我的实现使用了树状数组，复杂度为 $O(n\sqrt{m}\log V)$，开了 O2 才勉强跑过去．精细实现采用值域分块来平衡复杂度，复杂度为 $O(n\sqrt{m})$．

P4095 [HEOI2013] Eden 的新背包问题

题意是不考虑某个物品的多重背包问题．

一般的多重背包，我们会设 $f_{i,j}$ 表示考虑了前 $i$ 个物品，总重量为 $j$ 时的最大价值．为了减去某个物品的贡献，我们可以再设 $g_{i,j}$ 表示考虑了后 $i$ 个物品，总重量为 $j$ 时的最大价值．然后我们做两次 dp，分别计算出 $f,g$．

对于每个询问，答案为 $\displaystyle\max_{k=0}^e\{f_{d-1,k}+g_{d+1,e-k}\}$．

CF13C Sequence

本题有一个很重要的贪心结论~~（然而在我做的时候翻译直接给出了，并且我并不会证明．）~~，修改后的序列中只会出现原序列中的数．

记原序列升序排序后为 $c$．

所以我们设 $f_{i,j}$ 表示当前序列中区间 $[1,i]$ 已经满足要求，并且最大值不大于 $c_j$ 时的最小代价，那么我们有如下转移：

$$f_{i,j}\leftarrow\min\{f_{i,j-1},f_{i-1,j}+|a_i-c_j|\}$$

P1272 重建道路

记节点 $u$ 的儿子构成的集合为 $C_u$．

设 $f_{u,i}$ 为当前 $u$ 的子树中保留 $x$ 个节点所需要删除的边数．

对于每个节点 $u$，我们枚举它的儿子 $v$，考虑是否从以 $v$ 为根的子树中选点，我们有如下转移：

$$f_{u,i}\leftarrow\min_{v\in C_u}\min_{j=1}^i\{f_{u,i-j}+f_{v,j}-1\}$$

答案统计时，对于非根节点，我们需要加上其与父亲连接的那一条边，所以答案为：

$$\min\{f_{1,p},\min_{i=2}^n\{f_{i,p}+1\}\}$$

P6419 [COCI2014-2015#1] Kamp

记边 $(u,v)$ 的权值为 $w(u,v)$，节点 $u$ 的儿子构成的集合为 $C_u$，$h_u$ 表示 $u$ 的子树中家的数量，$f_u$ 表示送完家在子树内的人之后回到 $u$ 点的最小花费，$g_u$ 表示 $u$ 子树外的最小花费，$l_{0/1,u}$ 表示 $u$ 子树中的最长 / 次长链，$m_{u}$ 表示 $u$ 子树外的最长链．

求点 $u$ 的答案时，我们可以选择一个点作为结束点，贪心地选取对答案贡献最大，即由 $u$ 出发的最长链的结束点即可，答案为 $f_u+g_u-\max\{l_{0,u},m_u\}$．

容易得到 $l$ 的转移，转移 $m$ 时，分类讨论当前儿子是否在子树内的最长链上，转移如下：

$$\forall v\in C_u,m_v\leftarrow\max\left\{m_u, \left( \begin{cases} l_{0,u} & \text{if }l_{0,u}\not=l_{0,v}+w(u,v) \\ l_{1,u} & \text{otherwise} \end{cases} \right) +w(u,v)\right\}$$

$f$ 的转移容易得出：

$$f_{u}\leftarrow\sum_{v\in C_u}(f_{v}+2\times w(u,v))$$

进行 $g$ 的转移时，需要注意儿子 $v$ 的子树内是否有家，如果没有的话需要加上 $2\times w(u,v)$：

$$g_{v}\leftarrow g_{u}+(f_{u}-f_{v})+[h_v\not=0]\times 2\times w(u,v)$$

注意转移应当在转移目标中存在家时进行．

P3621 [APIO2007] 风铃

首先如果存在深度差超过 $1$ 的两个叶子节点，那么就无解，这个 dfs 即可判断．然后如果在 dfs 过程中发现左子树和右子树中同时存在最大和最小深度，那么也无解．

记存在的最大深度为 $x$，最小深度为 $y$，节点 $u$ 左子树中叶子节点构成的集合为 $L_{u,0}$，右子树中叶子节点构成的集合为 $L_{u,1}$，节点 $u$ 的深度为 $d_u$．

然后我们考虑如何计算最小交换次数，对于节点 $u$，有以下三种情况需要交换左右子树：

1. $\forall v\in L_{u,0},d_v=y\land\forall v\in L_{u,1},d_v=x$．
2. $\forall v\in L_{u,0},d_v=y\land\exists v,w\in L_{u,1},d_v=x,d_w=y$．
3. $\exists v,w\in L_{u,0},d_v=x,d_w=y\land\forall v\in L_{u,1},d_v=x$．

统计答案即可．

CF558E A Simple Task

常见套路，对 $\Sigma$ 中的每个字符建立一棵线段树，支持区间覆盖操作．

对 $[l,r]$ 的升序排序操作可以这样实现：对于每个字符，统计它在 $[l,r]$ 区间的出现次数，然后将 $[l,r]$ 推平，然后从值较小的字符开始依次覆盖，每个字符覆盖的长度是它的出现次数，这样覆盖出的区间就一定是升序排序的．降序排序类似．

CF961E Tufurama

以 $i$ 为 $x$ 轴，$a_i$ 为 $y$ 轴，将序列画到坐标轴中，对于每个 $j$，满足条件的 $i$ 的个数是以 $j$ 对应的点为原点重新建立坐标系，新坐标系中第 II 象限的点数，用主席树数点即可．

P2822 [NOIP2016 提高组] 组合数问题

答案为下式的值：

$$\sum_{0\le i\le n}\sum_{0\le j\le m} \left[\binom{n}{m}\bmod k=0\right]$$

用组合数的递推式计算 $\binom{n}{m}\bmod k$，然后二维前缀和即可．

P2827 [NOIP2016 提高组] 蚯蚓

容易想到一个用堆模拟过程的解法，长度增加的过程打标记即可，时间复杂度 $O(m\log n)$，无法通过本题．

我们容易发现，先被切掉的蚯蚓一定比后被切掉的蚯蚓长，所以我们可以用 $3$ 个队列模拟堆，取出时在三个队首取 $\max$ 即可．

严谨证明见：Link．

P7554 [COCI2020-2021#6] Index

我们使用莫队来解决这个问题．

考虑移动左右端点时，何时答案会改变．记当前答案为 $x$，$\displaystyle s_x=\sum_{i=l}^{r}[a_i\ge x]$；

若 $s_{x+1}\ge x$，说明 $x$ 可以变大；若 $s_x<x$，则 $x$ 应当变小．用一个变量维护 $s_x$ 即可．

P6835 [Cnoi2020] 线形生物

设 $f_x$ 表示在图中由 $x$ 走到 $x+1$ 的期望步数，由期望的线性性质可以得到答案为 $\displaystyle\sum_{i=1}^{n}f_i$．

记 $d_x$ 为点 $x$ 的度数，$A_x$ 表示 $x$ 返祖边的边集．那么对于 $f$，我们有如下转移：

$$f_x\leftarrow\frac{1}{d_x}+\frac{1}{d_x}\sum_{(x,y)\in A_x}\left(\sum_{i=y}^{x}f_i+1\right)$$

又 $|A_x|+1=d_x$，转移式化简如下：

$$f_x\leftarrow\left(\frac{1}{d_x}\sum_{(x,y)\in A_x}\sum_{i=y}^{x}f_i\right)+1$$

此时等式右边仍含 $f_x$，无法转移，将其挪到左边，化简可得：

$$\begin{alignedat}{} && f_x &= \frac{d_x-1}{d_x}f_x+\frac{1}{d_x}\left(\sum_{(x,y)\in A_x}\sum_{i=y}^{x-1}f_i\right)+1 \\ & \Rightarrow & \frac{1}{d_x}f_x &= \frac{1}{d_x}\left(\sum_{(x,y)\in A_x}\sum_{i=y}^{x-1}f_i\right)+1 \\ & \Rightarrow & f_x &= \left(\sum_{(x,y)\in A_x}\sum_{i=y}^{x-1}f_i\right)+d_x \end{alignedat}$$

照上式转移是 $O(n^2)$ 的，我们进行前缀和优化．

记 $\displaystyle s_x=\sum_{i=1}^n{f_i}$，我们有：

$$f_x\leftarrow\left(\sum_{(x,y)\in A_x}s_{x-1}-s_{y-1}\right)+d_x$$

这样即可在 $O(n)$ 的时间复杂度内解决这个问题．

CF1667B Optimal Partition

记 $v(l,r)$ 代表区间 $[l,r]$ 的价值．

容易想到一个暴力 dp 的方式，设 $f_i$ 表示区间 $[1,i]$ 分割后价值和的最大值，我们有如下转移：

$$f_i\leftarrow\max_{j=1}^{i-1}\{f_j+v(j,i)\}$$

暴力 dp 的复杂度是 $O(n^2)$，显然会 TLE．

记 $\displaystyle s_x=\sum_{i=1}^x a_i$，我们发现转移方程可以写成如下的形式：

$$f_i\leftarrow\max \left\{ \max_{s_j<s_i}\{f_j-j\}+i, \max_{s_j=s_i}f_j, \max_{s_j>s_i}\{f_j+j\}-i \right\}$$

采用线段树维护 $f$，时间复杂度 $O(n\log V)$，其中 $V$ 是 $s_i$ 的值域．

CF1637D Yet Another Minimization Problem

稍微玩一下这个式子可以得到：

$$\begin{aligned} \sum_{i=1}^n\sum_{j=i+1}^n(x_i+x_j)^2 &= \frac{1}{2}\left(\sum_{1 \le i,j \le n} (x_i+x_j)^2 - 4\sum_{i=1}^n x_i^2\right) \\ &= \frac{1}{2}\left(\sum_{1 \le i,j \le n} (x_i^2+2x_ix_j+x_j^2) - 4\sum_{i=1}^n x_i^2\right) \\ &= \frac{1}{2}\left(\sum_{1 \le i,j \le n} (x_i^2+x_j^2) + \sum_{1 \le i,j \le n}2x_ix_j - 4\sum_{i=1}^n x_i^2\right) \\ &= \frac{1}{2}\left((2n-4)\sum_{i=1}^n x_i^2 + 2\sum_{1 \le i,j \le n}x_ix_j\right) \\ &= (n-2)\sum_{i=1}^nx_i^2 + \sum_{1 \le i,j \le n}x_ix_j \\ &= (n-1)\sum_{i=1}^nx_i^2 + 2\sum_{1 \le i < j \le n}x_ix_j \end{aligned}$$

发现交换操作并不会对前面那一项产生影响，我们只需要最小化 $\displaystyle\sum_{1 \le i < j \le n} a_ia_j+b_ib_j$ 即可．

我们使用 dp 来解决这个问题．设 $f_{i,j}$ 表示前 $i$ 位已经确定，此时 $a$ 的前缀和为 $j$ 时的最小值．

转移考虑是否交换当前位置上的值，记 $\displaystyle s_x=\sum_{i=1}^x a_i,t_x=\sum_{i=1}^x b_x$，我们有如下转移：

$$f_{i,j}\leftarrow\min \left\{ \begin{aligned} & f_{i-1,j-a_i}+(j-a_i)\times a_i+(s_i+t_i-j-b_i)\times b_i, \\ & f_{i-1,j-b_i}+(j-b_i)\times b_i+(s_i+t_i-j-a_i)\times a_i \\ \end{aligned} \right\}$$

答案即为：

$$2\times\min_{i=1}^Vf_{n,i}+(n-1)\sum_{i=1}^na_i^2+b_i^2$$

P2122 还教室

对于一个区间 $[l,r]$，其元素平均值直接按照定义式 $\displaystyle\frac{1}{r-l+1}\sum_{i=l}^r a_i$ 计算．

记这段区间的元素平均值为 $\overline{a}$．

对于方差，要对式子做如下的变换：

$$\begin{aligned} S^2 &= \frac{\sum_{i=l}^r (a_i-\overline{a})^2}{r-l+1} \\ &= \frac{\sum_{i=l}^r (a_i^2-2\overline{a}a_i+\overline{a})^2}{r-l+1} \\ &= \frac{\sum_{i=l}^r a_i^2}{r-l+1}-\left(\frac{\sum_{i=l}^r a_i}{r-l+1}\right)^2 \end{aligned}$$

线段树维护 $\displaystyle\sum_{i=l}^r a_i,\sum_{i=l}^r a_i^2$ 即可．

CF11D A Simple Task

记给出的图为 $G(V,E)$．设 $f_{u,S}$ 表示当前在 $u$，已经经过集合 $S$ 中的所有点的路径条数，钦定 $S$ 中编号最小的点为路径的起始点．

统计答案时，我们枚举结束点，统计路径长度大于 $3$ 的路径条数，将其除以 $2$ 就是环数．

$f$ 的转移如下：

$$\forall(u,v)\in E\land v\not\in S,f_{u,S\cup v}\leftarrow f_{u,S\cup v}+f_{u,S}$$

实现上注意到 $n\le 19$，可以将点的集合压入一个 uint32_t 中，计算点集 $S$ 的大小时可以使用 __builtin_popcount 函数，找 $S$ 中编号最小的点可以使用 __builtin_ctz 函数．

CF165E Compatible Numbers

设 $f_{i}$ 表示一个数，使得 $i\operatorname{or}f_i=f_i$．显然有 $f_{a_i}\leftarrow a_i$．

若 $a_i\operatorname{and}a_j=0$，那么 $a_j$ 是 $a_i$ 二进制取反之后的子集．那么我们有如下转移：

$$\forall 2^k\operatorname{and}i\not=0\land f_{2^k\operatorname{xor}i}\not=0,f_i\leftarrow f_{2^k\operatorname{xor}i}$$

CF507D The Maths Lecture

我们使用数位 dp 来解决这个问题．

设 $f_{i,c,0/1}$ 表示当前在第 $i$ 位，$\bmod\ k=c$，后缀中不存在 / 存在 $k$ 的倍数的数的个数．

转移时考虑当前位上填入哪个数，如果填上数之后能被 $k$ 整除，那么当前后缀中存在 $k$ 的倍数的状态要加上原状态后缀中不存在 $k$ 的倍数的状态．

枚举当前位填入的数字 $d$，转移方程如下：

$$\begin{aligned} f_{i+1,\overline{dc}\bmod k,0} &\leftarrow f_{i+1,\overline{dc}\bmod k,0}+\left[\overline{dc}\bmod k\not=0\lor d=0\right]f_{i,c,0} \\ f_{i+1,\overline{dc}\bmod k,1} &\leftarrow f_{i+1,\overline{dc}\bmod k,1}+\left[\overline{dc}\bmod k=0\land d\not=0\right]f_{i,c,0}+f_{i,c,1} \end{aligned}$$

其中 $\overline{dc}$ 表示将 $d,c$ 的十进制形式按序拼接形成的新数．

P1799 数列

设 $f_{i,j}$ 表示考虑了原序列的前 $i$ 位，删除了 $j$ 个数的最大价值．

我们有如下转移：

$$f_{i,j}\leftarrow\max\{f_{i-1,j-1},f_{i-1,j}+[i-j=a_i]\}$$

P6564 [POI2007] 堆积木 KLO

P1799 数列 加强版．

在原题中我们给出的 dp 方式是 $O(n^2)$ 的，无法通过本题．

我们可以设出一个更好的状态. 设 $f_{i}$ 表示第 $i$ 个积木到达自己位置上，前 $i$ 个积木中最多能归位的个数．

我们有：

$$f_{i}\leftarrow\max_{j<i,0<a_i-a_j\le i-j}f_{j}+1$$

又 $a_i-a_j\le i-j$ 这个不等式可以化为 $j-a_j\le i-a_i$，然后就变成了一个偏序问题，用树状数组维护最大值即可．

P1948 [USACO08JAN] Telephone Lines S

既然有 $k$ 条边的价值可以白嫖，我们显然需要选择路径上权值最大的 $k$ 条边白嫖，这样我们的任务就变成了让路径上第 $k+1$ 大的权值最小，我们使用二分来解决这个问题．

我们的 check 函数需要对于参数 $x$，确定是否存在一条路径，使得最多有 $k$ 条边的权值大于 $x$．

每次 check，我们首先将原图中边权大于 $x$ 的边断开，这样原图就被划分成了几个联通块．

我们将每个联通块缩成一个点，点之间连上原本被断掉的边，边权为 $1$，这样我们只需要确定在新图中，原本的 $1$ 所在的联通块缩成的点到 $n$ 所在的联通块缩成的点的最短路长度是否大于 $k$ 即可．

我采用队列优化的 Bellman-Ford 来实现最短路，时间复杂度 $O(np\log V)$，其中 $V$ 是边权的值域．

P4688 [Ynoi2016] 掉进兔子洞

记原序列中区间 $[l,r]$ 的元素构成的可重集为 $S_{l,r}$．

那么每次询问的答案就是 $\displaystyle\sum_{i=1}^3(r_i-l_i+1)-\left|\bigcap_{i=1}^3S_{l_i,r_i}\right|$．

我们考虑用莫队去计算询问的所有区间构成的可重集，最后再按照上式计算答案．

为了快速对可重集求交，计算大小，我们使用 bitset 来维护可重集．

移动端点时注意我们维护的是可重集，插入元素 $x$ 时，需要将当前 bitset 的第 $x+c_x$ 位置 $1$，其中 $c_x$ 是 $x$ 在当前区间的出现次数．

但是这样做的空间复杂度是 $\displaystyle O\left(\frac{nm}{w}\right)$ 的，其中 $w$ 为字长，无法通过本题．

我们可以将询问分成常数大小的块，这样可以在不改变时间复杂度的情况下将空间复杂度变为 $\displaystyle O\left(\frac{nB}{w}\right)$，其中 $B$ 是块大小．

学艺不精，不是很会分析这个时间复杂度．