ARC158 题解

简单场，但是我更降智。

A. +3 +5 +7 (700)

毛估估一下我们只会对最小值 (+3)，次小值 (+5)，最大值 (+7)。然后做完了，时间复杂度 (mathcal O(T))。

大概证明就是等价于一个数 (-2)，一个数 (+2)，设最终三个相同的数为 (x)，那每次操作必定也最多可以让 (displaystylesum_{i=1}^{3}{|x_i-x|}) 减 (4)。

Code

B. Sum-Product Ratio (1400)

首先令 (x_i+x_j=a,x_ix_j=b)，那么 (frac{x_i+x_j+x_k}{x_ix_jx_k}=frac{a+x_k}{bx_k}=frac{a}{b}cdotfrac{1}{x_k}+frac{1}{b})，确定了 (x_i,x_j) 后只需最小/最大化 (frac{1}{x_k}) 即可。

而 (frac{x_i+x_j}{x_ix_j}) 同样可以通过正负性讨论来求最小/最大值。为了避免臭长的分类讨论，可以分正负后把前三小，前三大拎出来做 (n^3) 暴力。

时间复杂度 (mathcal O(n))。

Code

C. All Pair Digit Sums (1900)

考场上写了 3 个 log 过了，后来发现自己降智了

首先有 (f(a_i+a_j)=f(a_i)+f(a_j)-9 imes p)，(p) 为 (a_i+a_j) 的进位次数。那么只需要对每个 (a_i+a_j) 数进位次数。

枚举 (a_i)，考虑有多少个 (a_j) 能让 (a_i+a_j) 在第 (k) 位进位，第 (k) 位进位相当于后面连续一段加起来是 (9)，然后接着一个 (geq 10)。对所有 (a_j) 的后 (k) 位排序，满足条件的 (a_j) 一定是一段后缀。于是提前对每一位后面排序，枚举 (a_i) 和 (k) 即可用 lower_bound 算出 (a_j) 的个数。

时间复杂度 (mathcal O(nlog nlog V))。

Code

D. Equation (2900)

赛时看 D 比 E 过的人少就跳了，没想到如此简单

如果看到左边一堆括号就想拆，那你就输了。

假设现在有 ((x,y,z))，把它变成 ((kx,ky,kz))，那么左式会乘上 (k^{3n+1})，右式会乘上 (k^{3n})，刚好差一个 (k)！

所以可以直接随一组 ((x,y,z))，只要左式不为 (0) 就行。官方题解好像还证了为 (0) 概率不超过 (frac{1}{4})？不会证。

时间复杂度 (mathcal O(Tlog p))。

Code

E. All Pair Shortest Paths (2600)

赛时想了个大粪做法，到结束了还没写出来

容易发现最优路径不可能会走过去再走回来，所以路径一定是从左到右然后中间有一些拐点的形状。

然后就是 CDQ 板题。(dp) 求出两边到中间的距离，然后合并。

具体怎么合并？左边到右边一定会穿过中间两条边之一（两条边即 ((mid,0) ightarrow (mid+1,0)) 和 ((mid,1) ightarrow (mid+1,1))），那么最短路径长度大概是 (min(a_0+b_0,a_1+b_1)) 的形式。假设 (a_0+b_0 leq a_1+b_1)，那么相当于 (a_0-a_1 leq b_1-b_0)，排序后求后缀和就行了。(a_0+b_0 > a_1+b_1) 同理。

时间复杂度 (mathcal O(nlog^2n))，足已通过，但题解好像有单 log 甚至线性做法。

Code

F. Random Radix Sort (3500)

一眼题？感觉赛时要是看 F 的话都做出来了。

考虑一个操作序列 ({k_1,cdots,k_m}) 会对原序列产生什么影响。从后往前看，那么首先会把 (A) 按照第 (k_m) 位排序，(k_m) 位相同的再按照 (k_{m-1}) 位排序，以此类推。所以我们只关心每个 (k_i) 最后一次出现的位置，这组成一个子序列。

容易证明，假设操作序列有 (p) 个不同的数，那么每个子序列的出现概率为 (frac{1}{p!})。所以只需要对这个子序列计数。以下的操作序列均指这个子序列，且前后翻转。

先假设 (A_i) 互不相同，考虑 (A_i) 和 (A_j(i<j)) 在 (m) 次操作后会发生什么变化。对于一次 (k) 操作，如果 (A_i) 第 (k) 位比 (A_j) 小，我们将这次操作标记为 (<)，如果比 (A_j) 大就标记为 (>)，如果一样就标记为 (=)。

对于 (=) 类操作，显然不会对 (A_i) 和 (A_j) 产生任何变化；如果是 (<)，那 (A_i) 就会永远在 (A_j) 前面；(>) 号同理。

所以，如果 (A_i) 在 (B) 中还是在 (A_j) 前面，那么 (>) 号操作前必须要有一个 (<)（否则你 (A_i) 跑到后面去了）；如果在后面，那么 (<) 号操作前必须要有一个 (>)，并且最终序列不能全是 (=)。这相当于对每个位置有一个限制，表示前面必须要有某个集合 (S) 的一个数。这个限制是好刻画的，相当于前面的操作不能是 (Usetminus S) 的子集。

因为现在这个操作序列里的数互不相同，所以可以直接暴力状压 dp，每次往末尾新加一个数，并且要保证满足限制。时间复杂度 (mathcal O(nlog n+nk+k2^k))。

Code