2024 牛客 OI 赛前集训营-提高组（第三场）题解

A

本题 std 有误。数据已修复。

首先把 a 和 b 一一对应起来，维护 b 在 a 中的位置。

比如 a = [3,2,3,1,2], b = [2,3,1,3,2]，那么对应一下就是 [3,4,1,2,0]，变成了一个 0 ~ n-1 的排列

然后只需要对这个数组进行排序，如果 shuffle 能将这个数组变成 [0,1,2,3,4]，那么等价的就会把 a 变成 b。

于是模拟快排并判断是否需要 swap。如果需要 swap，就让 quantum_rand 返回 1，否则就让 quantum_rand 返回 0。

quantum_rand 的执行次数和基准值的选择有关，应该让 quantum_rand 的执行次数越少越好。

对于长度为 n 的数列，quantum_rand 的最小执行次数为

一开始误以为一定在中间也就是 时取到最小值，但这个式子并不是一定在中点取到最小值，所以 std 错了。

实际上答案应该在 取到最小值。

证明过程详见：https://ac.nowcoder.com/discuss/1412177

因此，对于长度为 的区间，应该让第 大的数作为基准值，让 quantum_rand 的返回值对应基准值的位置。

B

注意到每个点开启的周期 t 很小（t <= 10），提取最小公倍数 2520。

那么对于所有点，t 和 t + 2520 对应的开启情况一定是一样的，所以对于每个点的最短路只需要考虑模 2520 时的最小答案即可。

所以把一个点 u 拆成 2520 * 2 份，还需要分为继续跃迁和停止两种情况。

令 (u, i, 0) 表示点 u，到达 u 的最短路模 2520 为 i，当前已经停止的状态。

令 (u, i, 1) 表示点 u，到达 u 的最短路模 2520 为 i，当前可以继续跃迁的状态。

考虑转移：

(u, i, 0) -> (v, (i + w + k) % 2520, 0)，假如有一条边起点为 u 终点为 v 权值为 w。

(u, i, 0) -> (v, (i + w + k) % 2520, 1)，假如有一条边起点为 u 终点为 v 权值为 w，且到达 v 点时 v 的星门是开启的。

(u, i, 0) -> (u, (i + 1) % 2520, 0)，表示停止。

(u, i, 1) -> (v, (i + w) % 2520, 0)，假如有一条边起点为 u 终点为 v 权值为 w。

(u, i, 1) -> (v, (i + w) % 2520, 1)，假如有一条边起点为 u 终点为 v 权值为 w，且到达 v 点时 v 的星门是开启的。

(u, i, 1) -> (u, (i + 1) % 2520, 0)，表示停止。

就变成了一个最短路。但是如果跑的是 dijkstra，那么复杂度会带一个 log，但是对于 n, m <= 5000 可能会超时，考虑去掉 log。

注意到 w + k < 2520，所以转移的时候只有进位和不进位两种情况，所以可以跑 01 最短路。

举个例子，比如转移是：(u, i, 0) -> (v, (i + w + k) % 2520, 0)

那么，如果 i + w + k < 2520，那么就连一条长度为 0 的边；如果 i + w + k >= 2520，必然有 i + w + k < 2520 * 2，那么就连一条长度为 1 的边。

最后如果 (u, i, 0) 的答案是 k，那么实际对应的最短路就是 2520k + i。

可以用双端队列 + bfs 实现，很容易通过时间限制。

C

问题等价于把 的排列放到 ，满足 ，问方案数

时，考虑状压 dp。

令 表示 已经放进去了，mask 维护每个位置有没有放的方案数。

把数一个一个放进去，并维护方案数。

m=1 时，也就是把 2 ~ n+1 这 n 个数放到 1 ~ n 的位置上，满足 。

1 ~ n 和 2 ~ n+1 里，2 ~ n 的部分是重叠的。

先把重叠的部分放到对应位置上，那么 1 是空出来的，然后考虑 n+1 的位置。

考虑这样一条满足整除关系的链：，满足 ，那么就有这样一种摆放方案：

放到 的位置上， 放到 的位置上，...， 放到 的位置上

举个例子，n = 5，m = 1，考虑链 [1, 2, 6]，那么就有摆放方案：[2, 6, 3, 4, 5]

可以证明，每种摆放方案和每一条链一一对应。

这是因为其他位置是没法动的。假如位置 i 上放的是 a[i] 且 i != a[i]，那么让 i 指向 a[i]。因为 i | a[i]，所以有 i < a[i]。那么最后一定会形成一条链，这条链的起点一定是 1，最后指向的一定是多余的 n+1，否则一定会有数没地方放。

考虑求以 为起点， 为终点的链的方案数。令 表示以 为起点， 为终点的整除链的方案数，那么有

这样的状态一共有 个， 表示 的因子数，直接枚举因子，用 map/unordered_map 维护一下答案即可，跑得很快。

对于原问题，相当于把 m+1 ~ m+n 这 n 个数放到 1 ~ n 位置上，满足 i | a[i]。

那么对于 1 ~ n 和 m+1 ~ m+n 里，m+1 ~ n 的部分是重叠的。

先把重叠的部分放到对应位置上，那么 1 ~ m 是空出来的，然后考虑把 n+1 ~ n+m 放进去。

考虑 条满足整除关系的链：

...

终点一定对应 n+1 ~ n+m。同样，每种摆放方案和这 条链也是一一对应的。

考虑固定 条链的起点和终点，并计算固定起点和终点后对应的方案数。

先考虑计算一条起点和终点固定的链的方案数。对于其中的一条链，假如起点是 ，终点是 ，计算方法和计算以 1 为起点，n+1 为终点的链的方案数相同。但是在计算时除了考虑 的所有因子，还必须让路径不经过 1 ~ m 的其他点，这是因为其他点已经出现在他们自己的链上了。

于是，这 m 条链是独立的。因为中间的点（m+1 ~ n）不可能出现在两条链上。因为假如两个终点 i, j（n+1 ~ n+m）的链同时经过了同一个点 k，那么一定满足 k | i, k | j，也一定有 k | (j - i)，不妨设 j > i，那么 j - i 一定小于 m，所以 k 也一定小于 m。

因此，对于固定 条链的起点和终点后的方案数，相当于直接计算每条链的方案数，然后乘起来即可。

接下来，考虑所有起点和终点的每一种对应，并计算总方案数

形式化上说，答案就是

其中， 是集合 上的置换的全体， 表示以 为起点， 为终点，且不经过 1~m 的其他点的整除链的方案数。

可以使用状压 dp 计算答案，时间复杂度 。每一个 的答案需要预处理。

D

考虑最简单的 dfs/bfs/dp，状态为 (x1, y1, x2, y2)，其中 (x1, y1) 为兔子所在位置，(x2, y2) 为帕格丽所在位置。

帕格丽每步可以向四个方向走一格。而当 (x1, y1) 和 (x2, y2) 相邻时，模拟兔子的运动即可。

如果能把兔子逼到无法移动，就说明能抓到。

时间复杂度

注意到只有 的状态是有意义的，设 R 所在的位置为 (x1, y1)，只有 P 与 (x1, y1) 距离小于等于 2 的情况是有意义的。

因为 P 的行动过程为：P 与 R 距离为 2 -> P 与 R 距离为 1（然后 R 跑开，距离为 2）-> P 与 R 距离为 2 -> ...

所以本质上需要维护的只有 与 R 距离为 2 的位置在不经过与 R 相邻位置的情况下的连通性。

对于每个兔子所在的点 (x1, y1)，考虑以 (x1, y1) 为中心挖去一个 3 * 3 的正方形。把正方形的上下两边延长，再加上左右两边，将整个方格分割成 5 个部分，类似下图所示。

..........
..........
..........
xxxxxxxxxx
....xRx...
xxxxxxxxxx
..........
..........
..........

用并查集维护这些点的连通性：

• x1-2 这一行的点在只经过上半部分的图的连通情况
• x1+2 这一行的点在只经过下半部分的图的连通情况

再加上中间这三行，一共 个点，直接 bfs，并排除 R 的相邻位置，这样就可以得到 8 个与 R 距离为 2 的位置的连通性。

预处理上述信息后，DP 的转移就变成了 ，状态为 ，时间复杂度 。期望得分 80 ~ 100 分。

转换成一个动态图连通性问题，也就是给一张无向图动态加边和删边，查询两个点是否连通。

对于兔子所在的每个位置 (x1, y1)，把周围的四个格子相关的边删去，查询与 (x1, y1) 距离为 2 的点之间的连通性，查询完了之后再把边连回来。

那么可以使用线段树分治 + 可撤销并查集。

考虑维护每条边存在的时间区间，也就是每条边在哪段时间存在。

用线段树维护这些区间，把边存在的时间区间拆成 log 份，打到线段树的节点上。

在线段树上进行 dfs，进入时把相关边连上，退出时把相关边删掉。用按秩合并但不进行路径压缩的并查集维护，复杂度也是 log 的。

时间复杂度