ICPC2023杭州站

A

$\quad$ 究极傻逼的大模拟题，因为金牌名额数与“至少通过一道题的队伍数”有关，所以存在令一个没切题的队伍切题从而增加金牌数的情况需要讨论，虽然可以分 $n \le 350$ 和 $n \ge 350$ 来讨论，但还是很傻逼，气的我直接不写了。

D

$\quad$ 左式为连加，右式为连乘，因此我们优先考虑将中间的项都变成1，考虑让 $a_2=a_4=...=a_{2n-2}=-2,a3=a5=...=a_{2n-1}=-1$，则左式等于 $2a_1-2n+4-a_{2n}$ ，而右式等于 $a_1a_{2n}$ ，容易构造出 $a_1=2n-3,a_{2n}=1$ 的特解。

E

$\quad$ 注意到 $s_i$ 实际上是 $s_{i-1}$ 无限循环后的一个前缀，因此对于一个确定的 $s_i$ 和 $len_{i-1}$ ，我们可以得出：

$\quad\quad$ 1.循环的次数 $cs$

$\quad\quad$ 2.$cs$ 次循环后剩余的 $s_{i-1}$ 的前缀长度 $last$

$\quad$ 根据这两个东西，我们可以推得 $s_{i-1}$ 的长度为 $last$ 的前缀中分别包含了每种字符各几个，并判断是否合法。

$\quad$ 显而易见地，若确定 $s_i$ 的某个前缀的字符组成是确定的，就也能依此法更新出 $s_{i-1}$ 的某个前缀的字符组成状态。又因为所有的字符串都可以由 $s_1$ 递归得到，因此只需要找到一个合法的 $s_1$ 即可。

$\quad$ 知道了所有串的组成状态，可以从后往前推知每一个串应符合的所有前缀状态，注意到所有串的前缀状态数加起来不会超过 O( $\sum |s_i|$ ) 级别。注意要时刻判断状态合法性。

F

$\quad$ 一个很有用的结论：对于一棵子树，若某个点距离这颗子树的直径端点的距离最大为 $k$ ，则这个点到这颗子树的任意点的距离都小于等于 $k$ 。

$\quad$ 尝试简略证明这个结论：令子树为 $T$ ，这个点为 $x$ ，直径端点分别为 $d_1$ 和 $d_2$ ，并设点 $y$ 为 $x$ 到两个直径端点的路径中第一个经过的子树上的点，则有：

$\quad$ 又根据直径的定义得 $\forall x \in T,dist(x,y) \le max{dist(d_1,y),dist(d_2,y)}$ ，因此：

$\quad$ 由此，先不考虑整棵树的权值mex，我们考虑把节点按权值由小到大排序，依次构建出权值最大值 $w_i$ 的树并找出他们的直径端点，注意到权值最大值更大的子树是完全包含权值最小值更大的子树的，因此对于每次查询可以用二分答案的方法来判断被询问的点是否离某棵子树的所有节点的距离都小于等于 $k$ ,由此把第一个没有出现的权值与整棵树权值的mex向比较即可。

$\quad$ 关于建树，显然不是对于每个 $w_i$ 都存在对应子树的，我们考虑每次加入一个新节点时先求出将要加入的节点 $x$ 和当前子树的根节点 $y$ 的lca—— $lc$ 然后分情况讨论：

$\quad\quad$ 1. $lc$ 和 $y$ 是同一个节点，则直接从 $x$ 一直向上，把沿途的节点全部加入树中，直到遇到已经在树里的节点停止。

$\quad\quad$ 2. $lc$ 的深度更浅，则分别从 $x$ 和 $y$ 引一条链上去。

$\quad$ 每次更新完树之后还要更新树的直径端点。考虑到每次加入树的都是一条链，则新树的直径端点一定是老树直径端点以及 $x$ 这三个点其中的两个，直接更新即可。

$\quad$ 最后，由于二分的时候求距离需要用到lca，倍增或者树剖求lca的log n复杂度会TLE，因此使用dfn序求lca，设两个点分别为 $x$ 和 $y$ 且 $dep_x \le dep_y$ ，分情况讨论：

$\quad\quad$ 1.若 $x$ 是 $y$ 的祖先，则 $x$ 一定是区间 $[dfn[x],dfn[y]]$ 中深度最小的那个。

$\quad\quad$ 1.若 $x$ 不是 $y$ 的祖先，则区间 $[dfn[x],dfn[y]]$ 中深度最小的节点的父节点一定是 $x$ 和 $y$ 的lca。

$\quad$ 因此，我们只需要求区间 $[dfn[x],dfn[y]]$ 中深度最小的节点就行了，用ST表预处理即可。

G

$\quad$ 假设一个点是蛇身的一部分，则令他是从尾到头第 $a_i$ 段，且蛇头到这个点的距离为 $d_i$ （考虑其他蛇身的影响），那么蛇头到达这个点的最短时间为 $max{d_i, a_i}$ 。当不存在 $a_i$ 或者 $d_i \ge a_i$ 时可以直接用普通队列存入并用bfs的处理方式，当 $d_i < a_i$ 时则用优先队列存入并用dijkstra的处理方式，每次优先比较队列和优先队列的队头谁的距离更小，选择更小的那个更新即可。

H

$\quad$ 将每个小朋友的事件抽象成一条从 $i$ 到 $b_i$ 的单向边，则所有事件构成一个基环树森林，我们对每条边分类：

$\quad\quad$ 1.$a_i < a_{b_i}$ ，即第 $i$ 个小朋友一定会得到 $w_i$ 个糖果。

$\quad\quad$ 2.$a_i \ge a_{b_i},a_i < a_{b_i}+w_{b_i}$ ，即第 $i$ 个小朋友要在第 $b_i$ 个小朋友得到糖果之后触发事件才能得到糖果。

$\quad\quad$ 3.$a_i \ge a_{b_i}+w_{b_i}$ ，即第 $i$ 个小朋友一定得不到糖果，可以把这一类边直接处理成断边。

$\quad$ 要判断一个小朋友能否得到糖果，我们可以一直延二类边走，直到走到一个一定能或一定不能得到糖果的小朋友，记录一下路径长度 $d$ ，则第 $i$ 个小朋友收到额外糖果的概率为 $\frac{1}{d!}$ 。容易发现，一个全部都是二类边的基环树，树里的所有节点都一定得不到额外的糖果。

$\quad$ 记忆化搜索求出每个点的路径长度再计算即可。

J

$\quad$ 这题感觉上有很多种做法，只讲述其中一种。

$\quad$ 用 $\lceil\frac{n}{2} \rceil$ 次询问分别查询是否存在形如 $(2k-1,2k)$ 的边（若 $n$ 为奇数则查询 $(n,1)$ ）。若都不存在则一定是链，否则取一条边的两点分别判断其是否为菊花图的中心点即可。

M

$\quad$ 找到谷底 $d$ ，先考虑 $d$ 左侧数的个数确定后该如何决定右侧数的个数。

$\quad$ 设谷底及左侧共有 $k$ 个数，和为 $s$ ，右边数的前缀和为 $ps_i$ ，则选择右边 $i$ 个数的平均值为： $\frac{s+ps_i}{i+k}$ 。

$\quad$ 考虑二分答案，当期望平均数为 $c$ 时，有：

，我们发现在 $c$ 固定的情况下， $i$ 的选取与 $k$ 和 $s$ 没有任何关系，无论如何取最大的判断即可，因此每次check的时候先求出最大的 $ps_i-ic$ ，再枚举左侧数的个数判断是否成立即可。

$\quad$ 记得注意实数二分时的精度，不要用 while(fabs(r - l) > 1e-9) 这样的条件，容易精度爆炸，建议使用 for (int i = 1; i <= 80; ++ i) 。