2022.10 做题记录

P2634 [国家集训队] 聪聪可可

钦定根为 $1$．

令 $C_u$ 表示 $u$ 的儿子构成的集合，$F_u$ 表示节点 $u$ 的父亲，$\operatorname{w}(u,v)$ 表示 $(u,v)$ 这条边的权值，$\operatorname{d}(u,v)$ 表示 $u$，$v$ 之间的距离．

设 $f_{u,k}$ 表示在 $u$ 的子树中满足 $\operatorname{d}(u,v)\bmod3=k$ 的 $v$ 的个数，$g_{u,k}$ 表示在树中满足 $\operatorname{d}(u,v)\bmod3=k$ 的 $v$ 的个数．

容易得出 $f$ 的转移:

$$f_{u,k}=\sum_{v\in C_u}f_{v,k-\operatorname{w}\left(u,v\right)\bmod3}$$

我们由换根 dp 套路可以得到 $g$ 的转移:

$$g_{u,k}=f_{u,k}+g_{F_u,k-\operatorname{w}\left(F_u,u\right)\bmod3}-f_{u,k-2\operatorname{w}\left(F_u,u\right)\bmod3}$$

答案即为:

$$\frac{1}{n^2}\sum_{i=1}^{n}g_{i,0}$$

P3953 [NOIP2017 提高组] 逛公园

令原图为 $G(V,E)$，$(u,v)\in E$ 的权值为 $\operatorname{w}(u,v)$，图中从 $1$ 到 $u$ 的最短路长为 $d_u$．

设 $f_{u,k}$ 表示从 $1$ 到 $u$ 长度为 $d_u+k$ 的路径条数．

考虑转移．假设 $f_{u,k}$ 可由 $f_{v,x}$ 转移而来．我们有下式:

$$d_v+\operatorname{w}(u,v)+x=d_u+k$$

解得 $x=d_u-d_v+k-\operatorname{w}(u,v)$．

那么我们有转移:

$$f_{u,k}=\sum_{(u,v)\in E}f_{v,d_u-d_v+k-\operatorname{w}(u,v)}$$

答案即为:

$$\sum_{i=0}^{k} f_{n,i}$$

P7453 [THUSCH2017] 大魔法师

考虑向量序列 $\alpha_1,\alpha_2,\cdots,\alpha_n$，其中 $\alpha_i=\left(a_i,b_i,c_i,1\right)$．

考虑修改操作．发现所有修改操作都可以通过矩阵乘法的形式来表示，具体如下:

1. $a_i=a_i+b_i$，修改时乘上的矩阵如下:

$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}$$

2. $b_i=b_i+c_i$，修改时乘上的矩阵如下:

$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}$$

3. $c_i=c_i+a_i$，修改时乘上的矩阵如下:

$$\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}$$

4. $a_i=a_i+v$，修改时乘上的矩阵如下:

$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ v & 0 & 0 & 1 \\ \end{pmatrix}$$

5. $b_i=vb_i$，修改时乘上的矩阵如下:

$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & v & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}$$

6. $c_i=v$，修改时乘上的矩阵如下:

$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & v & 1 \\ \end{pmatrix}$$

把我们的向量序列丢到线段树上，只需要提供区间和查询和区间乘修改即可．

不知道为什么大家都在说卡常，我没卡常也能过．

P5607 [Ynoi2013] 无力回天 NOI2017

令 $\oplus$ 代表按位 $\mathrm{xor}$ 运算．

记原序列为 $a$．

设序列 $b$，其中 $b_i=a_i\oplus a_{i-1}$．

可以发现这样的序列 $b$ 具有和差分数组类似的性质，这样我们的区间修改就变成了单点修改．

对于每次查询的区间 $[l,r]$，我们可以发现对于 $i\in[l,r]$，我们有：

$$a_i=a_l\oplus\bigoplus_{k=l+1}^{i}b_k$$

也就是说 $a_l,a_{l+1},\cdots,a_r$ 可被 $a_l,b_{l+1},b_{l+2},\cdots,b_{r}$ 表出，所以二者的基等价．

那么我们直接在线段树上维护 $b$ 的线性基，查询时取出 $b_{l+1},b_{l+2},\cdots,b_r$ 的线性基，然后插入 $a_l$ 进行查询即可．

注意对 $l=r$ 和 $r=n$ 的判定．

P3177 [HAOI2015] 树上染色

看到题目容易想到设 $f_{u,i}$ 为 $u$ 子树中选择 $i$ 个节点染成黑色时的最大受益．但是这样没法转移，所以寄．

考虑每条边的边权对答案的贡献，容易得到对于每种颜色的节点，$1$ 条边对答案的贡献即为其两侧同为这种颜色的节点数的乘积．

令 $s_{u}$ 表示以 $u$ 为根的子树的大小，$C_u$ 表示 $u$ 的儿子构成的集合，$\operatorname{w}(u,v)$ 为树上 $(u,v)$ 这条边的权值．

设 $f_{u,i}$ 表示在 $u$ 的子树中选择 $i$ 个节点染成黑色时对答案的贡献，我们可以得到转移：

$$f_{u,i}=\max_{v\in C_u}\left\{\max_{j=0}^{s_v}\left\{f_{u,i-j}+f_{v,j}+\operatorname{w}(u,v)\times j(k-j)+\operatorname{w}(u,v)\times(n-k+j-s_v)(s_v-j)\right\}\right\}$$

树形背包转移即可．

P1284 三角形牧场

发现三角形的周长一定．设为 $c$．

设 $f_{i,j}$ 表示是否存在边长为 $i,j,c-i-j$ 的三角形．

设 $i$ 为当前考虑到前 $i$ 位，容易得到转移：

$$f_{j,k}=f_{j-a_i,k}\lor f_{j,k-a_i}$$

转移时注意负下标．

最后枚举可行方案，Heron 公式计算面积即可．

比题解第 1 篇的效率高不少．

P1282 多米诺骨牌

注意到数据范围允许我们枚举差值．

设 $f_{i,j}$ 表示考虑前 $i$ 个骨牌，差值为 $j$ 的最小旋转次数．

显然有 $f_{x,y}=\infty,f_{0,0}=0$．

枚举差值 $j$，我们有转移：

$$\begin{aligned} f_{i,j+a_i-b_i} &= \min\left\{f_{i,j+a_i-b_i},f_{i-1,j}\right\} \\ f_{i,j+b_i-a_i} &= \min\left\{f_{i,j+b_i-a_i},f_{i-1,j}+1\right\} \end{aligned}$$

转移后找到绝对值最小的 $x$ 使得 $f_{n,x}\not=\infty$，$\min\left\{f_{n,x},f_{n,-x}\right\}$ 即为答案．

P1850 [NOIP2016 提高组] 换教室

记图中 $u,v$ 两点间的最短路距离为 $w_{u,v}$，显然可以用 Floyd 预处理．

设 $f_{i,j,0}$ 为考虑了前 $i$ 个时间段，已经申请了 $j$ 次换教室，且本次不申请的消耗的体力值总和的期望的最小值；$f_{i,j,1}$ 为本次申请的．

显然有 $f_{1,0,0}=0,f_{1,1,1}=0$．

考虑转移：

$$\begin{aligned} f_{i,j,0} \leftarrow \min\{&f_{i-1,j,0}+w_{c_{i-1},c_i},f_{i-1,j,1}+k_{i-1}w_{d_{i-1},c_i}+\left(1-k_{i-1}\right)w_{c_{i-1},c_i}\} \\ f_{i,j,1} \leftarrow \min\{&f_{i-1,j-1,0}+k_iw_{c_{i-1},d_i}+\left(1-k_i\right)w_{c_{i-1},c_i}, \\ &f_{i-1,j-1,1}+k_{i-1}k_iw_{d_{i-1},d_i} \\ &+\left(1-k_{i-1}\right)k_iw_{c_{i-1},d_i} \\ &+k_{i-1}\left(1-k_i\right)w_{d_{i-1},c_i} \\ &+\left(1-k_{i-1}\right)\left(1-k_i\right)w_{c_{i-1},c_{i}}\} \end{aligned}$$

答案即为：

$$\min_{i=0}^m \{f_{n,i,0},f_{n,i,1}\}$$

CF372C Watching Fireworks is Fun

先考虑朴素 dp．

设 $f_{i,j}$ 表示放第 $i$ 个烟火的时候在第 $j$ 个区间的最大开心值．

不难想到转移：

$$f_{i,j}\leftarrow \max_{k=j-d\left(t_i-t_{i-1}\right)}^{j+d\left(t_i-t_{i-1}\right)}\left\{f_{i-1,k}+b_i-\left|a_i-k\right|\right\}$$

然而注意到 $n\le1.5\times10^5,m\le300$，朴素 $O\left(n^2m\right)$ 的转移会 TLE．

考虑优化转移过程．

首先显然可以滚掉 1 维，然后不难发现转移瓶颈在求：

$$\max_{k=j-d\left(t_i-t_{i-1}\right)}^{j+d\left(t_i-t_{i-1}\right)}f_{i-1,k}$$

所以我们直接套上线段树，维护滚掉 1 维之后的 $f$ 即可．

然而 $O\left(nm\log n\right)$ 仍然会 TLE．

发现每次转移求最值的区间固定为 $[j-d\left(t_i-t_{i-1}\right),j+d\left(t_i-t_{i-1}\right)]$，可以想到单调队列．

时间复杂度为 $O\left(nm\right)$，可以通过本题．

P2962 [USACO09NOV] Lights G

首先基于模拟退火的随机化可以拿到优秀的 88 分．

首先可以先把每个点和其直接相连的点压到一个 uint64_t 里，操作相当于给当前状态异或上该点的状态．

显然对每个点进行的操作次数不会超过 $1$．

观察到 $n\le 35$，朴素 $O\left(2^n\right)$ 暴力会 TLE．

考虑 meet in the middle，分前后两块分别暴力，合并直接取 $\min$ 即可．

CF1689C Infected Tree

容易发现病毒感染会在叶子节点和只有 $1$ 个儿子的节点停止，且途经从根到该节点的链上所有节点．

记最后被感染的点的深度为 $d$．

被感染的节点的数量为 $d$．

当在叶子节点处停止时，删除的点的数量为 $d-1$．

当在只有 $1$ 个儿子的节点处停止时，删除的点的数量为 $d$．

从根开始搜索，遇到满足条件的点记录并更新答案即可．

CF1689D Lena and Matrix

考虑 Manhattan 距离转 Chebyshev 距离．

对点 $A\left(x_0,y_0\right)$ 进行变换得到点 $A^\prime\left(x_0+y_0,x_0-y_0\right)$，记该变换为 $\operatorname{F}\left(A\right)$．变换后 $2$ 点之间的 Chebyshev 距离即为原来的 Manhattan 距离．

记 $\texttt{W}$ 点的集合为 $W$，$\texttt{B}$ 点的集合为 $B$．

对于点 $P\in W$，能对 $P$ 点的答案造成贡献的只有以下 $4$ 个值：

$$\begin{aligned} \max_{Q\in B}x_{\operatorname{F}\left(Q\right)},\min_{Q\in B}x_{\operatorname{F}\left(Q\right)}\\ \max_{Q\in B}y_{\operatorname{F}\left(Q\right)},\min_{Q\in B}y_{\operatorname{F}\left(Q\right)} \end{aligned}$$

遍历每个点，答案取 $\min$ 即可．

P1453 城市环路

基环树上的 没有上司的舞会．

随意在环上选择一条边断掉，设这条边所连接的 $2$ 个点为 $u,v$．

分别以 $u,v$ 作为根进行树形 dp，状态和转移与没有上司的舞会相同．

答案取 $\max\{f_{u,0},f_{v,0}\}$，可保证 $u,v$ 不被同时选中．

P3572 [POI2014] PTA-Little Bird

设 $f_i$ 为到第 $i$ 棵树消耗的最小体力．

容易想到朴素转移：

$$f_i=\min_{j=i-k}^{i}\left\{f_j+\left[a_j\le a_i\right]\right\}$$

发现复杂度瓶颈在于求：

$$\min_{j=i-k}^{i}f_j$$

用单调队列维护即可．

P2627 [USACO11OPEN] Mowing the Lawn G

设 $f_i$ 为在前 $i$ 个牛中的最大效率．

有 $1$ 个显然的转移：

$$f_i=\max_{j=i-k}^i\left\{f_{j-1}+\sum_{x=j}^iE_i\right\}$$

显然可以前缀和优化．记 $s_x=\sum_{i=1}^{x}E_x$，有：

$$\begin{aligned} f_i &= \max_{j=i-k}^i\left\{f_{j-1}+s_i-s_j\right\} \\ &= \max_{j=i-k}^i\left\{f_{j-1}-s_j\right\}+f_i \end{aligned}$$

单调队列维护 $\max_{j=i-k}^i\left\{f_{j-1}-s_j\right\}$ 即可．

P6554 Promises I Can’t Keep

观察到电流流经的路径必为当前点到 $1$ 个叶节点的路径．

令 $d_u$ 表示在以 $u$ 为根的子树中的叶子节点的个数，$V_u$ 表示 $u$ 的点权，$C_u$ 为 $u$ 的儿子构成的集合．

设 $f_{u}$ 表示 $u$ 到 $u$ 的子树中的所有叶节点路径上的点权和的和，$g_u$ 表示在 $u$ 到树中所有叶子节点路径上的点权和的和．

对于 $f_u$ 显然有转移：

$$f_u= \begin{cases} V_u & \text{if }u\text{ is leaf node} \\ d_uV_u+\sum_{v\in C_u}f_v & \text{otherwise} \end{cases}$$

然后换根 dp 计算 $g$：

$$\forall v\in C_u,g_v= \begin{cases} g_u+V_v\left(d_r-2\right)-V_u & \text{if }v\text{ is leaf node} \\ g_u+V_v\left(d_r-d_v\right)-d_vV_u & \text{otherwise} \end{cases}$$

其中 $r$ 为随意选取且不为叶节点的根节点．

答案即为：

$$\max_{i=1}^n\left\{\frac{g_i}{d_i-\left[i\text{ is leaf node}\right]}\right\}$$

P7961 [NOIP2021] 数列

设 $f_{i,j,k,p}$ 表示当前讨论了 $S$ 的低 $i$ 位，已经选择了 $j$ 个元素，$S$ 低 $i$ 位中有 $k$ 个 $1$，当前位进位 $p$．

转移时枚举 $a$ 中 $i$ 的出现次数 $t$，当前状态造成贡献的状态为：

$$f_{i+1,j+t,k+(p+t)\bmod 2,\left\lfloor\frac{t+p}{2}\right\rfloor}$$

考虑当前状态对下 $1$ 个状态的贡献。对于当前未选择的 $n-j$ 位中，我们可以选择 $t$ 位进行填入，所以转移如下：

$$f_{i+1,j+t,k+(p+t)\bmod 2,\left\lfloor\frac{t+p}{2}\right\rfloor}\leftarrow f_{i,j,k,p}\times{v_i}^t\times\binom{n-j}{t}+f_{i+1,j+t,k+(p+t)\bmod 2,\left\lfloor\frac{t+p}{2}\right\rfloor}$$

答案即为：

$$\sum_{i=0}^{k}\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}f_{m+1,n,i,j}$$

P2569 [SCOI2010]股票交易

设 $f_{i,j}$ 表示第 $i$ 天持有 $j$ 股的最大收益．

然后大力分讨转移：

1. 第 $i$ 天不进行操作时：

$$\forall j\in\left[0,\mathrm{MaxP}\right],f_{i,j}\leftarrow\max\{f_{i,j},f_{i-1,j}\}$$

2. 第 $i$ 天直接购买股票时：

$$\forall j\in\left[0,{AS}_i\right],f_{i,j}\leftarrow -{AP}_i\times j$$

3. 第 $i$ 天买入股票时：

$$\forall j\in\left[0,\mathrm{MaxP}\right],f_{i,j}\leftarrow\max_{k\in\left[j-{AS}_i,j\right)}\{f_{i-W-1,k}-\left(j-k\right)\times{AP}_i\}$$

4. 第 $i$ 天卖出股票时：

$$\forall j\in\left[0,\mathrm{MaxP}\right],f_{i,j}\leftarrow\max_{k\in\left(j,j+{BS}_i\right]}\{f_{i-W-1,k}-\left(k-j\right)\times{BP}_i\}$$

$3$，$4$ 两种情况显然可以单调队列优化．

答案即为 $f_{T,0}$．

P8595 「KDOI-02」一个网的路

约定：$\operatorname{mbx}$ 表示第 $2$ 大的数，$C_u$ 表示 $u$ 的儿子构成的集合，$d_u$ 为 $u$ 的度数．

由于每次是炸掉和 $1$ 个点相连的所有边，所以我们先炸路再修路一定不劣．

于是我们的策略是把每个连通块内的树炸成 $1$ 条链，再把这几条链连接起来．

显然最终连成的链中的边是 $n-1$，那么我们在炸完后需要进行的操作 $2$ 的个数便为 $n-1-(m-x)$，其中 $x$ 是炸掉的边数．

那么我们只需要让 $x+y$ 最小，其中 $y$ 为操作 $1$ 的次数．

考虑对每个联通块随意选择 $1$ 个点做根，进行树形 dp．

设 $f_{u,0}$ 表示 $u$ 的子树已经被炸成链且 $u$ 被炸时最小的 $x$；$f_{u,1}$ 表示 $u$ 的子树已经被炸成链，$u$ 未被炸且 $\left|C_u\right|=1$ 时的 $x$；$f_{u,2}$ 表示 $u$ 的子树已经被炸成链，$u$ 未被炸且 $\left|C_u\right|=2$ 时最小的 $x$．

考虑转移：

1. 对于状态 $0$，转移显然：

$$f_{u,0} \leftarrow \sum_{v \in C_u} \min\left\{f_{v,0}-1,f_{v,1},f_{v,2}\right\} + d_u + 1$$

2. 对于状态 $1$，若想要其子树为链，其儿子中最多有 $1$ 个点不被炸，选择使得 $f_{v,1}$ 最小的 $v$ 不炸即可，当然还可以选择全部炸掉，转移如下：

$$f_{u,1} \leftarrow \sum_{v \in C_u} f_{v,0} - \max\left\{0,\max_{v\in C_u} \left\{f_{v,0}-f_{v,1}\right\}\right\}$$

3. 对于状态 $2$，若想要其子树为链，其儿子中最多有 $2$ 个点不被炸，那么再在 $f_{u,1}$ 的基础上选择使得 $f_{v,1}$ 第 $2$ 小的 $v$ 不炸即可，转移如下：

$$f_{u,2} \leftarrow f_{u,1} - \max\left\{0,\mathop{\operatorname{mbx}}\limits_{v\in C_u}\left\{f_{v,0}-f_{v,1}\right\}\right\}$$

最终以 $r$ 为根的联通块的答案即为 $\min\left\{f_{r,0},f_{r,1},f_{r,2}\right\}$，最后的 $x$ 将所有联通块的答案求和即可．