自动搬运

查看原文

来自洛谷，原作者为

	Error_Yuan **

搬运于2025-08-24 22:43:14，当前版本为作者最后更新于2022-11-11 21:33:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

T4 题解：

观察题意得，我们对序列 $a$ 做前缀异或和得到 $s$ 后，每次操作相当于交换 $s_i$ 和 $s_{i-1}$。

（不失一般性，以下全部假设 $s_{L-1}=0$，$s_{L-1}=1$ 时是相反的）

至多 $k$ 个 $1$ 在 $k$ 为偶数时相当于把 $s_{[L,R]}$ 中的 $1$ 分成 $\dfrac{k}{2}$ 段，每段的 $1$ 都是连续的（$s_{L-1}=1$ 时是把 $0$ 分成 $\dfrac{k}{2}$ 段）。则我们可以写出如下 dp 转移：

• 设 $dp_{l,r,i}$ 表示 $s_{[l,r]}$ 中的 $1$ 分成 $i$ 段的最小操作次数；
• $dp_{l,r,i}=\min_{l\le j<r}(dp_{l,j,i-1}+cost_{j+1,r})$，其中 $cost_{i,j}$ 表示将 $s_{i,j}$ 中的 $1$ 移动到同一段的最小操作次数。
• $cost_{i,j}$ 可以通过平凡的贪心计算。

算法一

暴力转移，时间复杂度 $O(n^3k)$，预期通过测试点 $1\sim10$，然而由于常数极小，实际上可以通过测试点 $1\sim14$。

• 鲜花：这个 $O(n^3k)$ 到底是怎么做到 $400$ 只需要 $3s$ 的？？$400^3\times300=1.92\times10^{11}$，就算乘上 $\frac{1}{16}$ 的常数也有 $10^{10}$，怎么在 $4s$ 内跑过去的？？？

算法二

进行优化：感性理解一下，$cost$ 满足四边形不等式，因此可以用四边形不等式优化，复杂度降至 $O(n^2k)$。

注意：此处的四边形不等式优化和 [IOI 2000] 邮局 所用并不相同。

可以通过前 $17$ 个测试点。

算法三

• 继续优化：我们记矩阵 ${\bf{A}}_{ij}=\begin{cases} cost_{i,j} & \text{ if } i\le j\\ 0 & \text{ otherwise } \end{cases}$，则每次 $i$ 上的转移相当于对 $\bf{A}$ 做一次 $(\min,+)$ 的矩阵乘法，$\dfrac{k}{2}$ 次后 dp 矩阵即为 ${\bf{A}}^{\frac{k}{2}}$，所以用矩阵快速幂即可 $O(n^2\log k)$。请注意，经过算法二中的优化后这里的矩阵乘法是 $\bm{O(n^2)}$ 的。 实现需要注意细节，很容易挂。

一个细节：这里矩阵乘法的形式是：

这里中间的 $k$ 断开了，不一定能够满足乘法结合律，直接做快速幂会挂。我们可以这样重新定义矩阵乘法：

这样的话，设 ${\bf A'}_{ij}=\begin{cases} {\bf A}_{i-1,j} & \text{ if } i\le n\\ 0 & \text{ otherwise } \end{cases}$

这样 $\bf A'$ 也满足四边形不等式，而原来的 ${\bf A}^{\frac{k}{2}}$ 等于现在的 ${\bf A}\times{\bf (A')}^{\frac{k}{2}-1}$，这样就可以直接快速幂了。

对于询问，分类讨论一下即可做到单次 $O(1)$，具体如下：

• 若 $k$ 是偶数，答案显然为 $dp_{l,r,\frac{k}{2}}$。
• 若 $k$ 是奇数，则答案为 $\min_{l\le j\le r} (dp_{l,j,\frac{k-1}{2}}+cost2_{j+1,r}))$，其中 $cost2_{i,j}$ 表示 $s_{[i,j]}$ 中的 $1$ 在均移动到末尾（即 $j$）处的最小操作数，这个也可以通过四边形不等式优化在 $O(n^2)$ 内预处理。

附一些细节：

• 不要将 matrix 类型传入函数，很慢。
• 如果用了矩阵赋值，记得重载 =。

鲜花：本题赛时最高得分为 $36$，似乎大家都没有想到题解的第一句话。。。

得分为 $28/32/36$ 应该是写了错误的贪心。