ICPC2023香港站

A

$\quad$ 注意到一个节点 $x$ 的所有儿子都被定义后就可以被覆盖，换句话说，一个节点被覆盖当且仅当他的所有儿子被定义。那么递归地考虑这个问题，假设一个节点有 $k$ 个儿子，定义以第 $i$ 个儿子为根的子树所需的空间为 $f_i$ ，因为兄弟子树之间互不干扰，所以把每个儿子子树处理完毕后再处理另一棵儿子子树是合理的。从小到大对 $f_i$ 排序，显然除了以最后一个儿子为根的子树外，处理完以第 $i$ 个儿子为根的子树后占用的空间大小为 $f_i + 1$ ，而处理完以最后一个儿子为根的子树时可以直接把最后一个儿子定义到父亲节点所在的空间，处理完后占用的空间大小就是 $f_k$ ，因此定义以 $x$ 为根的子树所需的空间大小就为 $\max {f_k，f_{k-1}+1}$ 。

$\quad$ 用dfs遍历整棵树，并用vector存储每个节点的儿子对应的 $f_i$ 并排序计算出自己对应的 $f_i$ ，注意讨论一下叶节点和只有一个儿子的节点的情况即可。

B

$\quad$ 注意到 $(n+1) \times (m+1)$ 的矩阵的最后一行和最后一列一定是白色，且所有的黑色方格一定联通，所以连通块数量至少有两个。

$\quad$ 接下来证明:多余的白色连通块中，每个连通块有且只有一个白色方格满足与其相邻的右方和下方的方格都是黑色的。

$\quad$ 显然，如果一个方格的上方和左方都存在白色方格，那这个方格一定是白色的。反过来说，一个黑色方格要么上方不存在白色方格，要么左方不存在白色方格，对于一个白色方格 $(i，j)$ ，若 $(i，j+1)$ 和 $(i+1，j)$ 都是黑色的，则说明 $(i，j+1)$ 的上方以及 $(i+1，j)$ 的右方所有方格都是黑色的，那么 $(i，j)$ 所在的白色连通块中就只存在行数小于等于 $i$ 且列数小于等于 $j$ 的方格，而在一个白色连通块中，这样的方格是唯一的。

$\quad$ 因此，分别计算出每个方格是上述的白色方格的概率，最后相加即可。

E

$\quad$ 考虑不同 $a_i$ 对计划数造成的影响:将所有的鹅push进对应 $a_i$ 的vector中，对每对在vector中距离为 $k-1$ 的鹅分别计算贡献，以下标为 $x$ 的鹅为例，设上一个任务与 $x$ 相同的鹅为 $y$ ，与 $x$ 在vector中距离为 $k-1$ 的鹅为 $z$ ，下一个任务与 $z$ 相同的鹅为 $t$ ，则不难推出满足 $l \in [y+1，x] \land r \in [z，t-1]$ 的计划全都不合法，边界的特殊情况不难推广。

$\quad$ 于是我们考虑固定计划的左端点，再维护出对于这个左端点有多少右端点是合法的，处理也很简单，维护一个线段树，满足区间加减和查询整个序列有多少个0两种操作，对于每对在vector中距离为 $k-1$ 的鹅计算出来的约束 $l$ 的区间 $[l_1，r_1]$ 以及约束 $r$ 的区间 $[l_2，r_2]$ ，顺序扫描左端点，每次在扫到 $l_1$ 处在线段树上对 $[l_2，r_2]$ 上区间加一，扫到 $r_1+1$ 处在线段树上对 $[l_2，r_2]$ 上区间减一，然后查询当前线段树上 $0$ 的数量，这个数量即为以 $i$ 为左端点的合法区间数。另外，每次扫描过 $i$ 后也在线段树上把单点 $i$ 加一。

$\quad$ 至于怎么维护这个线段树，注意到序列的每个数都不可能小于零，因此在线段树中维护最小值和最小值的数量即可。

F

$\quad$ 要将一个序列分成 $k+1$ 端并进行高精度加并比大小，我们注意最优情况下到相邻的两段之间的长度差不可能超过一，接下来试图证明。

$\quad$ 不妨设两段的长度分别为 $x$ 和 $y$ ，我们先讨论 $x > y$ 的情况，设两段的数字分别为 $a$ 和 $b$ ，第一段的最后一个数字为 $c$ ，在交换前得到的数是 $t_1=a+b$ ，交换后则变成了 $t_2=\frac{a-c}{10}+b+c \times 10^y$ ，两式相减得 $t_1-t_2=\frac{9}{10}a-(10^y-\frac{1}{10})c=\frac{9}{10}a-(10^{y+1}-1) \times \frac{c}{10}$ ，注意到 $9 \ge c$ 而当 $x-y \ge 2$ 时又有 $a \ge 10^{y+1}-1$ ，得证。同理可得 $x<y$ 的情况。

$\quad$ 于是只需要枚举出相邻两段之间的差再高精度加法并比较即可，注意卡常。

H

$\quad$ 签到题，等待时间 $a$ 肯定选 $l$ ，能杀就杀，推出答案为 $k \times b \times \left\lceil\dfrac{l}{b}\right\rceil$。

K

$\quad$ 我们先考虑想通过操作将 $x$ 转化为 $y$ 需要满足什么条件。即找到一个 $s$ 使 $x \div s=k......y$ ，则有 $x=ks+y$ ，推得只需满足 $x \ge 2y \lor x=y$ 即可，于是不难发现答案只能可能是最小的 $x$ 或最小的 $x$ 的一半，验证即可。

L

$\quad$ 只能删数而不能调整数的相对顺序，因此先判断 $a$ 和 $b$ 之间的数的相对顺序有没有变化，如果有直接输出NO。

$\quad$ 再考虑找出所有需要删的数，不难发现从大往小删一定是优的，因为先删大的数对于后续删小的数提供了优化的可能，一定是不劣的。确定了从大往小删后，我们可以通过ST表+二分的方法求出离某个数最近的且比它大的两个数作为删去每个数所需的最大区间的边界，注意要删除的数不能当区间的边界，也不能算入区间长度中，前者可以直接在ST处理时直接赋一个极小值，后者可以用树状数组动态维护这个区间内已经删去了多少数字。

$\quad$ 最后，将得到的区间长度从大到小排序，再把所有魔法工具的长度从大到小排序，双指针判断能否成功转化即可。