关键观察
把一个数除以 2^k 并向下取整,等价于对它做一次右移 k 位:
* floor(x / 2^k) = x >> k
因为操作可以做很多次,所以对同一个数连续做几次就是累计右移:
* 选了 k1, k2, ... 作用在 x 上,最终变成 x >> (k1+k2+...)
代价是这些 2^k 的和。
额外限制:每个 k 全局最多用一次,也就是说同一个 k 不能同时用于 x 和 y,也不能重复用于同一个数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
目标转成“选 K 分配给 X / Y / 不用”
你最终会让:
* x' = x >> sx
* y' = y >> sy
其中 sx 是分配给 x 的所有 k 的和,sy 是分配给 y 的所有 k 的和,并且用到的 k 互不重复。
要求 x' == y',并让总代价最小。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
预处理 DP:先算出每个 (SX, SY) 的最小代价
因为 x, y <= 1e17,最多也就 60 位左右,右移超过 60 基本都变 0,所以只需要考虑:
* sx, sy 都在 0..60 之间
做一个“背包式”的 DP,枚举 k=1..60,每个 k 有三种选择:
1. 不用 k
2. 把 k 分配给 x(sx += k,代价 += 2^k)
3. 把 k 分配给 y(sy += k,代价 += 2^k)
这样就能得到 best[sx][sy]:实现这对总右移量的最小代价(自动保证 k 不重复,因为每个 k 只处理一次)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
每个测试用例怎么用
对每个测试用例 (x,y):
* 枚举 sx=0..60,sy=0..60
* 如果 (x >> sx) == (y >> sy),就用 best[sx][sy] 更新答案最小值
复杂度:
* 预处理一次:大约 60 * 61 * 61,很小
* 每组数据:枚举 61*61=3721 次,t=1e5 也能接受
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C++ 代码