「Daniel13265 的公开赛」题解【悔改】

· · 题解

这是「Daniel13265 的公开赛」的官方题解。

子任务 1

直接枚举配对的木棍即可。

子任务 2,4,5

设长度为 i 的木棍的个数为 b_i，那么 x 作为最终的木棍长度最多可能出现的次数

f_x=\left\lfloor\frac12\sum_{i+j=x}\min\left(b_i,b_j\right)\right\rfloor

暴力算这个式子即可，算法时间复杂度为 \mathcal O\left(m^2\right)。

子任务 3

注意到上式中 b_i\ne0 的 i 的个数最多只有 n 个，于是可以将 b_i\neq0 的 i 的值统计出来，再用这 \mathcal O(n) 个数计算答案。时间复杂度 \mathcal O\left(\min^2(n,m)\right)。

子任务 6

发现上面的式子很像卷积，只是要计算 \min 的卷积。

于是考虑将上式转化一下，枚举一下小于等于 \min\left(b_i,b_j\right) 的数：

\begin{aligned}f_x&=\left\lfloor\frac12\sum_{i+j=x}\sum_{k=1}^{n}\left[b_i\geq k\right]\left[b_j\geq k\right]\right\rfloor\\&=\left\lfloor\frac12\sum_{k=1}^{n}\sum_{i+j=x}\left[b_i\geq k\right]\left[b_j\geq k\right]\right\rfloor\end{aligned}

然后就可以愉快地乘法卷积了~~~

但是，问题在于这么算的时间复杂度是 \mathcal O(nm\log m) 的。

优化方式也不难：考虑到子任务 3 的思路，发现对于一个给定的 t，大于 t 的 b_i 的 i 的个数只有 \mathcal O\left(\min\left(\dfrac nt,m\right)\right) 个，于是小于等于 t 的部分使用卷积，而大于 t 的部分直接暴力计算即可。

这个算法的总时间复杂度为 \mathcal O\left(tm\log m+\left(\dfrac nt\right)^2\right) ，当 t=\sqrt[3]{\dfrac{n^2}{m\log m}} 时有最小值 \mathcal O\left((nm\log m)^\frac23\right)。实际上，由于卷积部分常数较大，当 t 小于该值时程序运行效率更高。