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
考虑一张左部 个点,右部 个点的二分图,那么题意所述网格图则是将其行列对应连边。
问题转化为本质不同无标号二分图的数量。
由于每个点度数最多为 ,于是联通块的形状只有如下 种:
- 左部 个点,右部 个点的环。
- 左部 个点,右部 个点的链。
- 左部 个点,右部 个点的链。
- 左部 个点,右部 个点的链。
因为右部点一定够用,考虑以左部点数量为元的生成函数。
第一种的 GF 为 ,其余 ,简单相乘即可。
此时已经可以直接先 ln 加起来再 exp 无脑做,但是如果常数大的话可能过不去。
仔细观察发现这是五边形数的四次方取逆乘上 ,因此只需一次求逆和若干次乘法,时间复杂度 。
全部评论
(5) 回帖