补题情况
| 题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
|---|---|---|---|
| B | 2 | 0 | 0 |
| E | 0 | 0 | 0 |
| F | 0 | 0 | 0 |
| G | 2 | 0 | 0 |
| H | 2 | 0 | 0 |
| K | 0 | 0 | 0 |
题解
B. discount
题意
给定 $n$ 种商品，对于每个商品 $i$，有两种策略，一种是花费 $a_i$ 购买同时赠送商品 $j$，一种是花费 $b_i$ 购买。$(b_i\le a_i)$
问至少获得所有商品各一种的最小费用。
题解
假定花费 $a_i$ 购买商品 $i$ 可以赠送商品 $j$，则连边 $j\to i$，其中 $i$ 是 $j$ 的儿子结点。
于是可以得到基环树森林，定义每个结点的状态 $0/1/2$ 表示不购买该结点/以 $b_i$ 购买该结点/以 $a_i$ 购买该结点。
于是原问题等价于使得每个结点的状态如果为 $0$ 则至少有一个儿子状态为 $2$ 的最小费用。
先考虑树的解法，设 $\text{dp}(u,0/1/2)$ 为只考虑子树 $u$ 的情况下的最小费用，不难得到状态转移方程。
接下来考虑每个基环树上的环，任取一个点，枚举该点在环上的子节点状态是否为 $2$，然后进行线性 $\text{dp}$。
G. transform
二分答案 $+$ 滑动窗口，赛后一分钟过样例 $\to$ 过题，乐。
H. travel
题意
给定一棵点权树，从树上选三条不相交的路径，每条路径的权值定义为路径上的点权和，要求最大化三条路径权值和。
题解
设 $\text{dp}(u,0/1/2,i)$ 表示只考虑 $u$ 的子树，结点 $u$ 的状态为 $0/1/2$ 时，已经选中了 $i$ 条链此时的最大路径权值和。
我们需要维护一条正在生成的链，这条链不包含在已经选中的 $i$ 条链当中，如果 $u$ 状态为 $0$ 表示 $u$ 不在生成链中。
如果 $u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中， $u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。
考虑状态转移，利用生成链的合并，不难有
$$ \text{dp}(u,0,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,0,j)\\ \text{dp}(u,1,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,1,j)+a_u\\ \text{dp}(u,1,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,0,j)\\ \text{dp}(u,2,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,1,j)\\ \text{dp}(u,2,i+j)\gets \text{dp}(u,2,i)+\text{dp}(v,0,j) $$
注意上式的 $\gets$ 表示取最大值，另外为了防止选中复数条从 $v$ 生成的链，需要开一个临时数组存储中间量。
初始状态为 $\text{dp}(u,1,0)=a_u$，最后转移完要考虑将正在生成的链转化为已经选中的链，于是有
$$ \text{dp}(u,0,i)\gets \max(\text{dp}(u,1,i-1),\text{dp}(u,2,i-1)) $$
最终答案为 $\text{dp}(1,0,k)$，时间复杂度 $O(nk^2)$，其中 $k$ 表示最多能选中的链的个数。本题 $k=3$。
J. farm
题意
给定 $n\times m$ 的矩阵，每个位置一个植物，种类为 $a(i,j)$。接下来 $q$ 个操作，每次选定一个矩形区域施加种类为 $k$ 的药水。
当植物的种类与被施加的药水种类不同时植物死亡。问最后死亡的植物数。
题解 1
二维线段树维护区间赋值，最后查询时将所有操作下放到子节点暴力修改，时间复杂度 $O(nm\log n\log m)$。
题解 2
二维树状数组维护矩形区间加，先将所有操作加入矩阵，最后枚举种类，枚举种类 $k$ 的植物时先消除 $k$ 类药水的影响查询完成后再加回去。
时间复杂度同为 $O(nm\log n\log m)$，但常数小。
题解 3
随机给每个种类 $k$ 赋一个值 $f(k)$，然后哈希处理矩阵加，当种类 $k$ 的植物的所在位置的权值恰好为 $f(k)$ 的倍数时该植物存活。
如果不放心可以二重哈希，时间复杂度 $O(nm)$。
