「KDOI-03」序列变换题解

Error_Yuan · 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 转移：

暴力转移，时间复杂度 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)} 的。 实现需要注意细节，很容易挂。

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

C_{i,j}=\min(A_{i,k}+B_{k+1,j})

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

C_{i,j}=\min(A_{i,k}+B_{k,j})

这样的话，设 {\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) 内预处理。

附一些细节：

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

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

「KDOI-03」序列变换 题解