【题解】牛客NOIP暑期七天营-提高组1

T1: 最短路

对于第一档部分分，构造一朵菊花，直接从 向其他节点连对应权值的边即可。期望得分 分。

对于第二档部分分，我们希望每一个点都从最近的那个点连过来。也就是说，对于某个点 ，我们可以找到一个 ，满足 并且 尽可能大，然后从 向 连一条权值为 的边。可以证明这样构造出的图一定是最优的（最大边边权最小的），因此若找不到点 （即 ）或 ，则一定无解。暴力找前驱 可以做到 的复杂度。结合上一档部分分可以拿到 分。

对于所有数据，可以优化这个找点的过程。我们不妨将所有节点按照权值先排序，然后我们发现，随着 的增大，点 一定不会减小，因此用双指针扫描法即可找到这个 。当然用二分查找也是可以的。复杂度 ，期望得分 分。

代码

T2: 最小生成链

首先简单地说一下某几档部分分的做法：

• ，枚举每条链，得到最小值即可。时间复杂度 。

• ，类似于旅行商问题的做法，状压 DP 维护一个数组 表示目前这条链延伸到节点 ，链中包含的节点集合为 时，链中最大值的最小值。每次 枚举下一个节点直接转移过去即可。时间复杂度 ，由于遍历到的状态不多，是可以通过 的数据的。

• ，能够证明最小生成链最大边权一定是最小生成树的最大边权。暴力写个 Prim 可以做到 ，用 Boruvka + Trie 树求最小生成树可以做到复杂度 ，详见 CF888G Xor-MST。

  证明：首先最小生成树的最大边一定不大于最小生成链的最大边，然后按照下文的做法分为 两块后，中间这条边就是最小生成链最大边。如果不连上这条边，那么 的连通块和 的连通块无法连通。因此这条边一定在最小生成树中，也就是说最小生成树的最大边不小于最小生成链的最大边。于是就证明了两种的最大边相等。

原问题在完全图上，边数达到了 级别。直接在原图上处理显然是不行的，因此考虑转化问题。

众所周知，我们可以从左往右唯一的遍历一条链，这样得到的遍历序实际上就是一个序列。因此，一条链与一个序列是可以一一对应的。也就是说，对于一个 个点若干条边的图，它当中存在的所有生成链对应的就是 到 的一个排列，且这个排列满足相邻元素间在原图中有边。

由于题目中给出的图是完全图，因此 到 的所有 种排列都是符合要求的。于是原题就可以转化为：

给出一个长度为 的序列 ，请找出一个排列，使得相邻两元素间异或值的最大值最小。

现在我们看到特殊性质：序列中的元素只有 或 。

相信大家都能推得出来这个子任务的结论：当序列中所有元素都是 或都是 时，答案为 ；否则——序列中既有元素 又有元素 时，答案为 。

为什么会这样呢？感性理解一下，就是原序列中既有 也有 ，那么无论如何都避免不了有至少一组 和 相邻，因此最大值至少就为 。

我们把这个情况推广一下。由于位运算任意两位是不会互相影响的，我们考虑提取出原数列中的第 位，单独考虑这一位的情况。我们容易发现，对于这独立的一位，同样满足类似性质——当原序列中所有数在这一位上都是 或都是 时，这位的答案一定是 ；否则这位答案一定是 。

相信大家可以已经有一些想法了。

接下来我们需要回想起进制的一个有趣的性质，这也是我们经常利用的来做贪心的性质。也就是对于该进制的某一位 ，如果有两个数 ，满足 高于 的位全部相等并且 在第 位比 在第 位上的数大，那么无论低于 的位是什么样的， 一定大于 。

二进制也满足这个性质。因此我们考虑找出最高的一位满足原数列中所有数在这一位上既有 也有 ，那么我们就可以根据这一位的值将原序列分成这一位为 和这一位为 的两部分。我们不难发现，对于这每个部分内，由于这个最高位是 ，因此永远不可能出现最大值。这个序列的最大值一定是出现在 和 交界的部分。

我们希望这个交界的部分两元素异或值最小。也就是说，我们需要从这一位为 的元素中和这一位为 的元素中各找出一个元素，使得这两个元素的异或值最小。

于是有一个显而易见的 做法，枚举任意两个元素，找出异或值的最小值。解决了 。

接下来这个找最小值的过程可以进行优化。这里有异或操作，很自然地能够想到 0-1 Trie。我们可以维护一棵 0-1 Trie，我们将序列中所有这一位为 的元素插入这棵 Trie，然后用所有这一位为 的元素去 Trie 中查异或最小值。最后所有最小值的最小值就是答案了。

要注意特判一下所有元素都相同的情况，因为这会找不到这个最高的位满足这一位上有 和 。

时间复杂度和空间复杂度都是 。

代码

T3: 最小字典最短路

这是一道码农题 QwQ 思路可能很简单，但是代码写起来有点麻烦。我在此为自己的毒瘤向大家致歉。。。

对于 均不超过 的部分分，每次询问的时候都枚举起点 ，然后跑 SPFA 并路径还原找到 和 这两条最短路径，求一下公共路径长度，然后更新一下最大值即可。复杂度 。

对于数据随机的部分分，可以把询问先读入进来。将出发点提前枚举，求出到每个点的最短路径，然后再处理这个出发点对每个询问的贡献。由于数据随机，因此最短路经过边数的期望可以视作小常数 ，应该不会超过 。复杂度 。

的部分分是准备给写挂或者被卡空间的正解的。

对于 的数据，使用 SPFA 算法（您应该能猜到为什么不是“对于所有数据”了）跑出每个起点到其它点的最短路树。最短路树是一种满足如下条件的树：

1. 这是一棵有根树，以起点 为根节点。
2. 每个节点的父亲就是它在起点 到它的最短路径上的前驱节点。换句话说， 点的父亲节点 就是在最短路转移时最终的 这个 节点。

最短路树拥有一个很重要的性质：每个节点 到根 的这条路径，就是原图上 到 的最短路。

于是本问题转化为，对每个询问，找到一个根节点，使得 在最短路树上的 LCA 到根距离最长。

这样本题就基本完成了，先用 DFS 跑出每个点的最短路树，然后对最短路树树剖，然后枚举每个询问，用树剖查找在这个最短路树上的 LCA，用根到 LCA 的最短路长度直接更新这个询问对应的答案即可。但是这题空间只开 32 MiB，建出 棵最短路树会炸空间。因此要把询问离线读进来，枚举最短路树的根，然后再对每一个询问进行查询，用完后把最短路树滚动掉，让下一个起点接着用。复杂度 ，~~ 是基于图的小常数~~。

不知道 SPFA 加一些奇奇怪怪的优化能不能通过本题，至少我的 SLF+LLL 优化都被卡了。如果想要做到满分，需要一种类似于解决费用流时我们学过的原始对偶算法的 Johnson 算法。

Johnson 算法大致过程是，先建一个虚拟的 号点，从 号点向 号点都连一条权值为 的有向边，然后跑一遍 SPFA。得到的最短路数组我们记作 ， 称为 号点的势。

之后我们把原图进行一些奇妙的改造：将原图上每条边——不妨记作一条 连向 权值为 的有向边——的边权变为 。这样一来所有边权就都是非负的了，可以直接把 SPFA 换成 Dijkstra 算法（这是因为最短路满足三角形不等式 ，移项之后可得 ）。

而且对于一条路径 ，则路径长度为 ，中间所有 项全部消掉了，最后剩下 项之和加上 减掉 。也就是说，在这张新图上任意两节点最短路 ，都与它们在原图上最短路 有如下等式关系：。由于 是一个常数，因此在新图上最短路路径的形状也是不会改变的，改变的只是路径长度而已，而路径长度改变量又是可以推回去的，因此 Johnson 算法就没有问题了。

在 做法的基础上，用 Johnson 替代 SPFA 即可，时间复杂度 ，空间复杂度 。

代码