欧几里得算法

洛谷题库 P1852 跳跳棋

我仍然坚持认为这道题不应该放在LCA的专题里面

一拿到题我毫无头绪……这看起来跟最近公共祖先没有半毛钱关系啊?我的第一反应是“递推出从某个状态开始能达到的所有状态”,时间复杂度大约是O(2N)\mathbf{O}(2^{|N|})(至于为什么底数为22,请看完下一节后思考)。但很明显,坐标在±109\pm 10^9范围内的数据可容不下这般折腾。

但鉴于它被放在这个专题中,我们就尝试从的角度来考虑。

(更多…)

More
  • 2021年7月25日