ABC355E 题解

__ryp__ · 2024-05-26 00:03:44 · 题解

本篇题解是赛后补的，参考学习了官方题解以及 jiangly dalao 的代码。

首先发现本题和最近的 ABC349D 很像。但是注意到那个题里没法将两个区间相减，但是本题可以，于是那个题的策略没法照搬。

那么怎么样才能得到最优解呢？（题目要求我们必须用最优策略）

换句话说，我们需要求出从 r 走到 l 的最少步数。注意到值域相比上一个题小了很多，那么可以尝试最短路。

不难发现，对于一个数 u，我们能够转移到的数是 v = u \pm 2^j, 0\le j \le \mathrm {lowbit}(u)，其中 \mathrm{lowbit}(x) 是 x 的最低非零位。因为对于 j \gt\mathrm{lowbit}(u)，2^j \nmid u，无法转移。

由于边权都是 1，我们就可以直接 BFS 跑出最短路，然后一边跳一边计算即可。

赛后的 submission