多校 A 层冲刺 NOIP2024 模拟赛 09

Qyun / 2024-10-25 / 原文

多校A层冲刺NOIP2024模拟赛09

T1 排列最小生成树 (pmst)

特殊性质

首先若 $n$ 个点联通则每个点必然会有一条连边，那么显然一定存在一棵树使得树上每条边的边权不大于 $n$。所以对每个点可以只考虑边权在 $n$ 范围内的边，而由于边权是乘积的形式所以可以除法分块，最终就只有 $O(\sqrt n)$ 条边，此时直接跑最小生成树是 $O(n\sqrt n logn)$ 过不去 QwQ。考虑优化，注意到边权只会在 $1-n$ 的范围内，桶排就可以了。

所以时间复杂度为 $O(n\sqrt n\alpha(n))$

T2 卡牌游戏 (cardgame)

签到题

注意到 $n\times m$ 次操作必定是整数次轮回，所以可以考虑计算一轮的贡献即可。考虑用 $a$ 数组计算贡献，而对于一轮而言发现 $a$ 能匹配到的 $b$ 是下标在模 $\gcd(n,m)$ 意义下同余的所有数且不重（证明考虑观察数组 $a$ 中的一个数所有匹配到 $b$ 中的下标，公式化即可），按剩余系分类后排序即可二分查找。

时间复杂度为 $O((n+m)logn)$。

T3 比特跳跃 (jump)

特殊性质，二进制拆位，最短路

显然三个性质是三道题。

$Task$ $1$ $(a\&b)$
由于与操作是一个不增的过程，所以可以考虑一些特殊情况，即结果为 $0$，发现除二进制下全为 $1$ 的数都能与一个比自己小的数计算得零，而如果这个全为 $1$ 的数不是最大数则刚好能用比它大 $1$ 的数计算得 $0$，所以特判最后一个数，其余输出 $0$ 即可
$Task$ $2$ $(a⊕b)$
手摸发现两个数异或本质上是一位一位叠加的，所以可以对每个数只改变一位进行连边这样只会有 $O(nlogn)$ 条边，可以直接跑最短路，时间复杂度为 $O((nlogn+m)logn)$。
$Task$ $3$ $(a|b)$
⾸先跳多次的代价肯定超过跳⼀次的代价（从 1 跳至多会多一个 k），并且如果不是从子集过来，那⼀定不如直接从 1 跳过来。依据以上两种情况做就好。具体的先将 1 与所有点建边跑最短路，然后 $DP$ 从小到大记录每个数的最小子集然后与当前距离取较小值更新距离。然后再跑一遍最短路即可。
时间复杂度为 $O((n+m)logn)$。