题解：P12407 「CZOI-R3」数字变换

· · 题解

第一次场蓝，写篇题解纪念下。

关于符号的说明：\operatorname{and} 代表按位与。

给定一个长度为 n 的序列 x 和一个初始位置 a=p，每次操作可将 a 移至任意位置，而第 j 次操作花费为 w_{i,j}+2 \times (L-(x_a \operatorname{and} x_i))。L 为序列 x 的最大值，目标是求出第 k 次操作结束时，将 a 转移到每个位置 i 的最小总花费。

考虑 dp 做法。定义 dp_{i,j} 为 j 次操作后 a 位于位置 i 的最小总花费。因为在 j 次操作时可以从任意位置 v 移到 u，所以令 w_{i,j} 为第 j 次操作转移到 u 的花费，推出动态转移方程：

dp_{j,u}=\displaystyle\min_{1 \le i \le n} (dp_{j-1,v}+w_{u,j}+2 \times (L-x_v \operatorname{and} x_u)) $。 但是时间复杂度为 $O(n^2 \times k)$，显然超时。 观察到 $0 \le x_i < 2^{16}$，考虑位运算优化。将 $x_i$ 拆成高低 $8$ 位。令 $high_i=(\lfloor\frac{x_i}{2^8} \rfloor) \operatorname{and} (2^8-1)$ 而 $low_i=x_i \operatorname{and} (2^8-1)$。根据按位与的性质，可将 dp 式子拆成高低 $8$ 位的贡献，即

dp{j,u}=\displaystyle\min{1 \le i \le n} (dp{j-1,v}+w{u,j}+2 \times L-2 \times (high_v \operatorname{and} high_u) \times 256-2 \times (low_v \operatorname{and} low_u))

最后再通过预处理最小值进一步优化即可。 记 $P$ 为 $2^{24}$，则时间复杂度：$O(k \times P)$。空间复杂度：$O(n \times k)$。可以通过。 [AC 记录](https://www.luogu.com.cn/record/215809794)，[代码](https://www.luogu.com.cn/paste/4xgjt2v3)。