题解 | CF986 / Codeforces Round 485 (Div. 1)
题解 | 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) 差分成
然后就是树上差分,把询问离线到树上,然后一遍 \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;否则无解。
总结
独立完成。