题解 | 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；否则无解。
总结
独立完成。
