题解 | 2023 年牛客多校第三场 F 题

题意：给定两个十进制数 ，每次可以选择 十进制表达中的其中一位 ，然后执行 或 。问 最少经过多少次操作变成 。多次询问，，，强制在线。

解法：显然，每个点可以向外连出若干条边模拟一次操作。如果数字范围足够小那么是一个简单的全源最短路问题，但是本题数据范围较大，但是我们仍然需要这一建图的思想。

考虑固定枚举出中间某个特定的变化步骤，即取出一段长度为 的一段——因为一步操作至多使得 变化 。然后采用分治的思想：

定义起始数字 和结束数字 以及中间变化过程都在区间 ，考虑中间的 个数字 。这时可以考虑以 依次每个点跑单源最短路（bfs），求得每个点到 中每个点到其他点的正向（即 ）和反向（即 ）的距离。这时这个图的大小和源都相对较少，可以承受。

如果起始数字和结束数字分列在 和 区间，则必然需要在变化过程中经过 。那么答案可以是 的正向距离，加上 的反向距离之和。

如果都分在同一侧，则递归在两个子区间进行分治处理，预处理记录每个点在 层中到枢纽点 的两个距离。

考虑一次查询操作，则需要对每一个包含 的区间都做一次答案更新操作： 的正向距离，加上 的反向距离之和。这样单次查询操作仅需要查询 个区间，复杂度就是 。整体复杂度 。