题解 | CF986 / Codeforces Round 485 (Div. 1)

• 链接 ᴮᵃᶜᵏᵘᵖ
• 参考代码 ᴮᵃᶜᵏᵘᵖ

未独立完成的题目

• D（实现困难）
• E

A

题意

一张 $n$ 个点的连通图，$k$ 种货物，每个点有一种货物，运送货物的代价是两点间最短路的长度。对每个点分别求聚集 s 种货物的最小代价。$n\le 10^5,k\le 100$。

题解

注意到 $k$ 的范围很小，可以对每种货物跑一个最短路，dis[i][j] 表示离 $i$ 最近的货物 $j$ 到 $i$ 的距离。然后对每个点求离它最近的 $s$ 个货物即可。

总结

考场 AC，重做时独立完成。

B

题意

有一个长度为 $n$ 的序列 $1, 2, ... , n$，打乱序列的方式是随机选两个数，然后交换。$\mathrm{Petr}$ 进行 $3n$ 次操作，$\mathrm{Alex}$ 进行 $7n+1$ 次操作。给出一个 $1\sim n$ 的排列，问是谁打乱的。

题解

注意到 $3n$ 和 $n$ 的奇偶性相同，而 $7n+1$ 和 $n$ 奇偶性不同。同时，我们还原序列进行的操作数和打乱序列进行的操作数的奇偶性相同。所以可以 $\mathrm{O}(n)$ 还原这个序列（策略是不断交换 $a_{a_i}$ 和 $a_i$，直到 $a_i=i$），然后比较一下操作数和 $n$ 的奇偶性即可。

总结

考场 AC，重做时独立完成。

C

题意

一个由 $m$ 个整数构成的集合，每个整数均在 $0 \sim 2 ^ n - 1$ 之间。以每个整数为顶点建立一个无向图，当两个整数 x, y 符合 x & y = 0 时，则认为 $x, y$ 之间存在一条边。计算图中连通块的数量。

题解

设对 x 按位取反的结果为 z，则 x & y = 0 意味着 y & z = z，y 的 1 是 z 的 1 的子集。总共有 2 ^ 22 种状态，对于每个没被标记过的 x 直接爆搜 + 标记，复杂度完全吃得消。

总结

重做时独立完成。

D

题意

给出 $N$，选 $M$ 个正整数 $a_1,a_2,...a_M$（可以相同），使得 $\prod_{i=1}^{m} a_i \ge N$，并最小化它们的和。

题解

对一些小数据打表，可以观察到用 $2$ 和 $3$ 凑数是最经济的。 对 $x^{\log(\frac N x)}$ 进行研究发现，在 $x = e$ 的时候值最大，而 $2$ 和 $3$ 都很接近 $e$。所以考虑用 $3$ 凑数。设这 $M$ 个正整数的和为 $k$，则：

• $k \% 3 = 0$，全部用 $3$
• $k \% 3 = 1$，用两个 $2$，剩下全用 $3$
• $k \% 3 = 2$，用一个 $2$，剩下全用 $3$

k 的值可以通过二分确定，但是二分太慢了。解方程 $N = 3 ^ {\frac k 3}$，$k\approx log_{3}^N \cdot 3$。可以通过 $N$ 的长度（小于等于 $log_{10}^N$）去估计一个大概的 $k$ 值，再暴力乘上去。注意到这题卡常，显然要 $\mathrm{FFT}$，可能要压位高精。

总结

这题做法还记得，但是实现起来比较困难。

E

题意

给你一棵树，每个点有点权（$\le 10^7$），m 个询问，每次给定 x, y, w，问 x -> y 路径上的点的 点权与 w 的 gcd 的积，对 $10^9+7$ 取模。

题解

首先把询问 $(x, y, w)$ 差分成

$$ans(1,x) \times ans(1,y) \times \mathrm{gcd}(w,val_{lca(x,y)})\over ans(w,lca_{x,y})^2$$

然后就是树上差分，把询问离线到树上，然后一遍 $\mathrm{dfs}$ 去解决。$\gcd$ 本质是把每个质因数的幂次取 $\min$。注意到 $10^7$ 以内的质数个数只有 $6\cdot 10^5$ 级别。可以给每个质数开个桶，$vec[p][i]$ 表示正在处理的部分里质因数分解后 $p$ 的次幂为 $i$ 的点的个数。

总结

未独立完成。

F

题意

给定 $n, k$，问是否可以将 $n$ 分为若干个 $k$ 的因数之和。题目钦定了 $k = 1$ 的时候不能。

题解

题目限制最多 $50$ 个不同的 $k$，所以先将询问离线下来，对每个 $k$ 解决问题。先对 $k$ 质因数分解，如果质因数个数大于 $2$，用同余最短路解决；如果等于 $2$，设这两个质因数为 $a, b$，解 $ax + by = n$ 即可；如果等于 1，判一下 $n \% p$ 是否等于 $0$ 即可。

关于同余最短路，可以在最小的质因数的剩余系里做，并且对 $i$ 向 $(i + fac_x) \% fac_1$ 连一条边权为 $fac_x$ 的边。这样跑最短路，得到的结果 $dis_i$ 就是通过若干个 $p_2 \sim p_n$ 凑到 $\% p_1 = i$ 的最小值。如果 $dis_i \le n$，可以通过 $p_1$ 凑到恰好为 $n$；否则无解。

总结

独立完成。