BZOJ2144

Description

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋>来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。我们要通过最少的跳动把他们的位置移动成x，y，z。（棋子是没有区别的）跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。 写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。 ### Input 第一行包含三个整数，表示当前棋子的位置a b c。（互不相同） 第二行包含三个整数，表示目标位置x y z。（互不相同）

(输入数据均在内)

Output

如果无解，输出一行NO。如果可以到达，第一行输出YES，第二行输出最少步数。

Sample Input

1 2 3
0 3 5

Sample Output

YES
2

Solution

对于一个三元组作为状态考虑能够转移到的所有状态再来判和是否相同的暴搜肯定是过不了这题的。然后尝试找找规律，如果一个状态中 则只能转移到 两种状态，而如果不等的话只能选一边跳(因为只允许跳过一个棋子)，共有三个转移 冷静分析，什么东西是特殊点两个”转移“普通点三个”转移“？ 二叉树！ （这题来说树就够了） 这一步想通了之后的就简单了 相当于每个状态都是树上的节点，可能转移到与之相邻的节点，特殊点就是两个转移的的点即为根，1问相当于问是否同属一个树，2问相当于求两点之间距离，用求LCA的方法即可。 还有一个问题就是可能两个点之间距离太小如数据可能要很久才会到达一个根，考虑每次转移的两个距离到直到发现相当于每次减了若干小的那个数，可以算出能够减多少次和当前往上跳的次数取min来直接减去以加速这个过程，代码如下：

Code

#include<bits/stdc++.h>
#define FIO "2144"
#define DBUG(...) fprintf(stderr,__VA_ARGS__)
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;
const int N=4;
using namespace std;
template <class T>inline void read (T &x) {
  T f=1;
  x=0;
  char ch=getchar();
  for (; !isdigit (ch)&&ch!='-'; ch=getchar());
  if (ch=='-')f=-1,ch=getchar();
  for (; isdigit (ch); ch=getchar())x=x*10+ch-'0';
  x*=f;
}
struct node {
  int v[N];
  inline int& operator [] (int x) {
    return v[x];
  }
  inline void rd() {
    read (v[1]); read (v[2]); read (v[3]);
    if (v[1]>v[2])	swap (v[1],v[2]);
    if (v[2]>v[3])	swap (v[2],v[3]);
    if (v[1]>v[2])	swap (v[1],v[2]);

  }
  bool operator == (const node &t)const {
    return v[1]==t.v[1] && v[2]==t.v[2] && v[3]==t.v[3];
  }
  void operator = (node t) {
    v[1]=t[1]; v[2]=t[2]; v[3]=t[3];
  }
} a,b;
int L,R,mid,cur,d1,d2,ans;
node up (node x,int step) {
  int k1,k2;
  if ((k1=x[2]-x[1])== (k2=x[3]-x[2]))	return x;
  node ret=x;
  if (k1>k2) {
    int delta=min (step, (k1-1)/k2);
    step-=delta; cur+=delta;
    ret[2]=ret[2]-delta*k2; ret[3]-=delta*k2;
  } else {
    int delta=min (step, (k2-1)/k1);
    step-=delta; cur+=delta;
    ret[2]+=delta*k1; ret[1]+=delta*k1;
  }
  return step?up (ret,step):ret;
}
int main() {
  freopen (FIO".in","r",stdin);
	freopen(FIO".out","w",stdout);
  a.rd(); b.rd();
  cur=0; node x=up (a,INF); d1=cur;
  cur=0; node y=up (b,INF); d2=cur;
  if (x==y) {
    puts ("YES");
    if (d1<d2)	swap (d1,d2),swap (a.v[1],b.v[1]),swap (a.v[2],b.v[2]),swap (a.v[3],b.v[3]);
    a=up (a,d1-d2);
    L=0; R=d2; ans+=d1-d2;
    while (L<=R) {
      mid= (L+R)>>1;
      if (up (a,mid)==up (b,mid))	R=mid-1;
      else L=mid+1;
    }
    printf ("%d",ans+ (L<<1));
  } else	puts ("NO");
  return 0;
}