2024.10.13 模拟赛

题目：2024.10.13 题目

一般图最小匹配

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

---

首先，我们将 $a$ 排序，那么我们必定会选择相邻的两项，否则不优。接下来我们考虑算法，不难观察到 $1\le 2\times m\le n\le 5000$，这代表着我们肯定可以使用 $\mathcal{O}(nm)$ 或 $\mathcal{O}(n^2)$ 的算法。

结合题目的性质，我们不难猜出这是一道简单的序列 dp。设 $d{p}_{i,j,0/1}$ 表示为在前 $i$ 个元素已经选择了 $j$ 对，第 $i$ 个元素是否被选择，的最小权值。

考虑转移。对于元素 $i$ $(i\ge 2)$，有两种可能：与 $i-1$ 绑定或不选。对于选择的情况，可以从 $i-1$ 不选择得来，即 $d{p}_{i,j,1}=d{p}_{i-1,j-1,0}+a_i-a_{i-1}$；不选的情况有两种，一种是 $i-1$ 被选择，一种是 $i-1$ 没有被选择，即 $d{p}_{i,j,0}=\min (d{p}_{i-1,j,0},d{p}_{i-1,j,1})$。最后 $\min d{p}_{n,m,0/1}$ 就是答案了。时间复杂度 $\mathcal{O}(nm)$。

需要注意一下本题在实现过程中的细节。本题最大的答案仅有 $10^9$，因此不用开 long long，如果你不小心使用了 long long 且定义了 $5000^2\times 2$ 的数组，那么就会遗憾 MLE。可以使用滚动数组优化。

好渴鹅因为在 dp 的过程中没有特判 $i\ge 2$，导致第 $1$ 个元素和第 $0$ 个元素配对，遗憾 $80$ 分。

重定向

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

---

由于字典序是从左往右找到第一个不相同的元素开始比较的，因此我们从左往右枚举 $i$ 判断 $i$ 能不能被删除且答案能最优。不难发现有三种情况：

• $a_i\ne 0$ 且 $a_{i+1}\ne 0$，即 $i$ 与 $i+1$ 都不为空，此时如果 $a_{i+1}<a_i$，就可以删除 $a_i$ 让 $a_{i+1}$ 顶替 $a_i$ 的位置；
• $a_i\ne 0$ 但 $a_{i+1}=0$，即 $i$ 不为空但 $i+1$ 为空，我们可以删除 $i$ 并拿最小的未填数填进去，仅当未填数比 $a_i$ 小不然不优；
• $a_i=0$，此时可以填两种：最小的未填数和最小的 $j$ 满足 $j\ge i$，任选一个小的填进去即可。

删除最优的位置后，就使用优先队列对 $a_i=0$ 的未填数填入即可。时间复杂度 $\mathcal{O}(n{\log }_{2}n)$。

斯坦纳树

给定一张图 $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$ 个 $1$，$10$ 分。

直径

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

---

体检，没时间做题，输出 $1$，$15$ 分。

总结

• 排名：$8$；
• 比赛分数：$205/400$；
• 情况：相比 2024.10.10 模拟赛，还行；
• 问题：dp 水平不算好，不注重细节。