Loading... ## A 不解释 ## B 不解释 ## C 不解释 ## D dp一下即可,设 $f_{i,0 \sim9}$ 表示第 $i$ 位最后留下了 $0 \sim 9$ 的方案数,每次转移就从前面那位枚举 $0 \sim 9$ 两种方式填一下表就行了。 初始状态注意 $f_{1,a_1} = 1$ ## E 比较巧妙的一道题,注意到是一棵满二叉树,分类讨论贡献。对于每一个点,记 $f(i)$ 为 LCA 为 $i$ 且距离为 $d$ 的点对的数量,那么答案就是: $ans = \sum \limits_{i=1}^{n} f(i)$ 考虑怎么计算 $f(i)$,记 $dep_i$ 为 $i$ 的深度。 第一种情况,如果 $i$ 是点对 $(u, v)$ 中的一者,也就是 $i = u$ 或 $i = v$ 。那么另外一者只需要在树上跳一条长度为 $d$ 的链即可。这部分的贡献就是 $0$ 或 $2^{d-1}$,因为如果 $d + dep_i > n$ 那么就是 $0$。 另外一种情况,也就是 $i \neq u \& i \neq v$,不妨设 $dep_u > dep_v$,那么 $u$ 可以先跳到 $i$ 再向下跳一段到 $j$。对于 $0 < k < d$,设 $u$ 在 $i$ 的左子树中且 $dep_u = k + dep_i$,那么 $v$ 就在 $i$ 的右子树中且 $dep_v = dep_i + (d - k)$,方案数就是 $0$ 或 $2^{d-2}$。取决于 $dep_i + k$ 且 $dep_i + (d - k)$ 要 $< n - 1$ 所以预处理 $2$ 的次幂后,上述均可 $O(1)$ 计算。 ## F 比 E 简单,随便换根 dp 即可(话说这几场 ABC 连续考了好多换根 dp ## G 考虑什么样的一组线段可以成为梯形的上下底: 1. 两线的中垂线重合 2. 四条线段中点不同 然后枚举两个点,算一下中垂线,然后按照权值排序以后,每次都选最大的组成就可以了。 ## H 待更新 最后修改:2021 年 10 月 19 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏