竞赛讨论区 > 牛客挑战赛 64 解题报告
头像
tmpOUO
发布于 2022-10-14 21:18 福建
+ 关注

牛客挑战赛 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 无脑做,但是如果常数大的话可能过不去。

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

全部评论

(5) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐