2024.10.13 题目

题解：2024.10.13 模拟赛

一般图最小匹配

序列dp 排序

有 $n$ 个数，第 $i$ 个数为 $a_i$。需要选择 $m$ 对数，每次选择没有被选择过的数 $(i,j)$，该次权值则为 $|a_i-a_j|$。求 $m$ 次选择之后的最小权值。

重定向

贪心 优先队列

有长度为 $n$ 的序列 $a$，第 $i$ 个数为 $a_i$。可能会有若干位置上没有数，表示为 $a_i=0$。现在需要从 $n$ 个数当中删除任意一个数（可以删除空的位置），然后对于剩下的空的位置，可以填入 $[1,n]$ 的数，但是需要保证填写完之后 $a$ 没有重复的数，且字典序最小。输出填完后的序列。

斯坦纳树

并查集 树

给定一张图 $G=<V,E>$ 和点集 $V_1$，需要找到原图的一张子图，涵盖点集 $V_1$ 且连通，边权和尽量小。有一个问题：给定一棵树 $G$，每次给出点集 $V_1$，求 $V_1$ 在 $G$ 上的斯坦纳树边权和。

牛牛不会做这个问题，于是提出乱搞做法：建立新的完全图 $F^{\prime }$，每一个点都对应 $V_1$ 的一个点，两个点的边权为 $V_1$ 对应的点在 $G$ 的树上距离，最后将 $F^{\prime }$ 的最小生成树作为答案。

牛牛想要知道，这种乱搞算法在什么情况下是正确的。给出排列长度为 $n$ 的排列 $p$，牛牛想要知道对于 $i$ $(1\le i\le n)$ 在点集 $V_i=\{p_1,p_2,\cdots ,p_i\}$ 上的正确性。

直径

快速幂 递推 树

给定 $n,k,p$，求 $n$ 个点组成的无标号无根树当中，直径长度为 $k$ 且有 $p$ 条直径的树的数量有多少，答案对 $998244353$ 取模。