查看源代码：
MX-S10.md

---
title: MX-S10 / FeOI-4 两题
createTime: 2025/11/8
categories:
    - IT
tags:
    - OI
---

写挂了 QwQ，但是思路是对的。

## A

显然 $T \ge dk + d\min \{t_1,t_2\}$，$t_1 \le t_2$ 时可以取等，在原地等 $d$ 个铁然后直接出发即可。

$t_1 > t_2$ 不能取等。此时路径必然是多个折返，设距离 $d$ 的子问题答案为  $f(d)$，则
$$
\begin{aligned}
f(d) &= \min_{i=0}^{d-1} \max\{dk, f(i)+it_2\} + it_2 + (d-i)t_1 \\
&= dt_1 + \min_{i=0}^{d-1} \max\{dk+i(t_2-t_1), f(i)+i(2t_2-t_1)\} \\
&\mathop{=}\limits^{\text{换元}} dt_1 + \min_{i=0}^{d-1} \max\{A(d,i), B(i)\}
\end{aligned}
$$
众所周知，分段函数的最小值是每一段的最小值的最小值。$A(d,i)$ 关于 $i$ 单调递减，而 $B(i)$ 与 $d$ 无关，可以数据结构维护。因此只需知道如何分段。

$A$ 主导时
$$
dk \ge f(i)+it_2 \mathop{=}\limits^{\text{def}} g(i)
$$
因为 $g(i)$ 单调递增，$d$ 增加时分界点必不左移，可以直接挪分界点，不必二分。此时 $B(i)$ 相当于滑动窗口，单调队列维护即可。

单组测试数据时间复杂度 $O(m)$。

## B

我们可以使用算子大大简化问题。记 $D f(x) = f'(x)$，因为 $D$ 是线性算子，记 $f(x)+f'(x) = (1+D) f(x)$。
$$
F_{2k}(x) = \cdots(1+D)(1-D) F_0 (x) = (1-D^2)^k F_0(x
) \\
G_{2k}(x) = \cdots(1-D)(1+D) G_0 (x) = (1-D^2)^k G_0(x
)
$$

由二项式定理，
$$
\begin{aligned}
(1-D^2)^k f(x) = \sum_{i=0}^{k} (-1)^i \binom{k}{i} D^{2i}f(x)
\end{aligned}
$$
记 $[x^t]f(x)$ 为 $f(x)$ 的 $t$ 次项系数，则有
$$
\begin{aligned}
[x^t] (1-D^2)^k f(x) &= \sum_{i=0}^{k} (-1)^i \binom{k}{i} [x^t] D^{2i}f(x) \\
&= \sum_{i=0}^{k} (-1)^i \binom{k}{i} (t+2i)^{2i-}[x^{t+2i}]f(x) \\
&= \sum_{i=0}^{k} (-1)^i \binom{k}{i} \frac{(t+2i)!}{t!} [x^{t+2i}]f(x) \\
\end{aligned}
$$
在 $t+2i > m$ 的时候直接 `break`，时间复杂度 $O(m^2)$。

以上是 $n$ 为偶数的情况，如果 $n$ 为奇数，可以先求 $F_{n-1}(x), G_{n-1}(x)$，最后一次运算 $O(m)$，可以直接暴力。