10137. 「一本通 4.4 练习 4」跳跳棋

题意

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏:棋盘上有三颗棋子,分别在 $a,b,c$ 这三个位置。我们要通过最少的跳动把他们的位置移动成 $x,y,z$(注意:棋子是没有区别的)。
跳动的规则很简单,任意选一颗棋子,对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过一颗棋子。
写一个程序,首先判断是否可以完成任务。如果可以,输出最少需要的跳动次数。

思路

可以将状态视为一个三元组$(x,y,z)$。
  1. 中间往左跳:$(x,y,z) –> (2x-y,x,z)$
  2. 中间往右跳:$(x,y,z) –> (x,z,2z-y)$
  3. 左边往右跳:$if (y-x)<(z-y) then (x,y,z) –> (y,2y-x,z) Because ‘Only one chess piece is allowed to be skipped at a time.’$
  4. 右边往左跳:$if (y-x)>(z-y) then (x,y,z) –> (x,2y-z,y) Because ‘Only one chess piece is allowed to be skipped at a time.’$
可以注意到,操作1与操作2可以使该三元组区间扩大。而操作3与操作4可以使三元组区间缩小。 那我们将区间扩大的视为父亲,区间缩小的状态视为儿子。 那么我们可以由此构建一棵树。 先把深度大的节点移到深度小的节点,然后二分到LCA的距离,往上走n步和求根。 当然,这样是会TLE的,比如说这组数据:9998 9999 10000000 如果以1步每次的速度的话就需要跳 (10000000-9999)/(9999-9998)次嘛!所以就有一个优化:MOD。 这样就可以像gcd一样,跑得飞快。省去了很多时间。
暂无评论

发送评论


				
上一篇
下一篇