牛客挑战赛 64 解题报告

A

两种做法，第一种是建出完整图的最小生成树，可以发现最小生成树上点 到点 的路径上最小边权就是点 的答案。时间复杂度 。

第二种做法是使用并查集维护连通块，某个连通块与点 联通时就更新答案，启发式合并即可。时间复杂度 。

B

首先我们可以写出一个简单的暴力：根据汉诺塔的常规套路，将除了最大盘之外的盘子堆到除 最大盘所在柱 的另一个非目标柱上，然后将最大盘移动到目标柱上，不断递归下去即可。

具体地说，假设当前需要将 号盘从 移动到 柱，那么我们将 号盘全部堆到除 外的那个柱子上，然后再将 号盘堆到 上即可。

代码如下：

#include <bits/stdc++.h>

using namespace std;

int n, b[65];

void dfs(int k, int t) {
    if (b[k] == t) return ;
    for (int i = k - 1; i; i--) dfs(i, 3 - b[k] - t);
    b[k] = t, printf("%d %c\n", k, t + 'A');
}

int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i += 2) b[i] = 2;
    for (int i = n; i; i--) dfs(i, 1);
    return 0;
}

然后用这个暴力打出移动次数的表，可以发现（记 为 个盘子时的移动次数）：

直接递推即可。

C

发现如果越过距离为 ，则跳跃的路径会形成以 为起点，循环节为 的一个循环。

那么列出式子，设 ，则有：

可以通过枚举因数的倍数的方式 时间内求出， 筛法或者质因数分解求出。总时间复杂度 。

（一个数所有因数的和是 级别的。）

D

我们先考虑 的情况，即固定左端点求贡献。 的情况我们将序列翻转再做一遍即可。

当左端点固定时，可以发现合法的右端点一定是以 开头的一段区间，可以拆位求出该区间右端点。

那么现在我们只需要实现求以 开头一段区间的前缀最大值之和以及移动 时维护前缀最大值之和，使用线段树维护。

然后我们发现这样子做会算重 的情况，使用单调栈去重。

时间复杂度 。

E

考虑一张左部 个点，右部 个点的二分图，那么题意所述网格图则是将其行列对应连边。

问题转化为本质不同无标号二分图的数量。

由于每个点度数最多为 ，于是联通块的形状只有如下 种：

1. 左部 个点，右部 个点的环。
2. 左部 个点，右部 个点的链。
3. 左部 个点，右部 个点的链。
4. 左部 个点，右部 个点的链。

因为右部点一定够用，考虑以左部点数量为元的生成函数。

第一种的 GF 为 ，其余 ，简单相乘即可。

此时已经可以直接先 ln 加起来再 exp 无脑做，但是如果常数大的话可能过不去。

仔细观察发现这是五边形数的四次方取逆乘上 ，因此只需一次求逆和若干次乘法，时间复杂度 。