自动搬运

查看原文

来自洛谷，原作者为

	Daniel13265 **

搬运于2025-08-24 22:19:29，当前版本为作者最后更新于2020-03-22 22:03:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这是「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$ 小于该值时程序运行效率更高。