题解 | 2023 年牛客多校第三场 F 题
题意：给定两个十进制数 ，每次可以选择
十进制表达中的其中一位
，然后执行
或
。问
最少经过多少次操作变成
。多次询问，
，
，强制在线。
解法：显然，每个点可以向外连出若干条边模拟一次操作。如果数字范围足够小那么是一个简单的全源最短路问题，但是本题数据范围较大，但是我们仍然需要这一建图的思想。
考虑固定枚举出中间某个特定的变化步骤，即取出一段长度为 的一段——因为一步操作至多使得
变化
。然后采用分治的思想：
定义起始数字 和结束数字
以及中间变化过程都在区间
，考虑中间的
个数字
。这时可以考虑以
依次每个点跑单源最短路（bfs），求得每个点到
中每个点到其他点的正向（即
）和反向（即
）的距离。这时这个图的大小和源都相对较少，可以承受。
如果起始数字和结束数字分列在 和
区间，则必然需要在变化过程中经过
。那么答案可以是
的正向距离，加上
的反向距离之和。
如果都分在同一侧，则递归在两个子区间进行分治处理，预处理记录每个点在 层中到枢纽点
的两个距离。
考虑一次查询操作，则需要对每一个包含 的区间都做一次答案更新操作：
的正向距离，加上
的反向距离之和。这样单次查询操作仅需要查询
个区间，复杂度就是
。整体复杂度
。
投递微软等公司10个岗位 >
