HDU 3830 Checkers - c++编程基础

TOP

HDU 3830 Checkers

2015-07-20 17:33:21 来源: 作者: 【大中小】浏览:2次

Tags：HDU 3830 Checkers

题意：

有三个棋子可以隔一个棋子跳不能隔两个跳问状态u到状态v最少跳几步

思路：

对于一个状态三个棋子的位置可以设为 x y z （小到大）

只有当y-x=z-y的时候跳的方法为两种即 y跳过x 或 y跳过z

在上式等式不成立时短的一边可以跳许多次直到大小关系改变

那么这样就形成了二叉树的结构我们将y向左右跳的状态分别作为原状态的儿子将两边其中一个向中间跳的状态作为原状态的父亲

那么这时u和v的可达性就变成了他们是不是同一个根于是我们可以从u和v跳到头判断一下

如果能跳要跳几次呢？？这时利用LCA 方法与倍增法相同即 u和v先爬到同一高度再同时爬

爬的方法和刚才的状态向根移动相同由于没有倍增打表因此同一深度后我们要用二分法确定爬的高度

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               using namespace std; typedef unsigned long long LL; #define M 1100 #define N 16 struct state { int x[3]; void Sort() { sort(x, x + 3); } int Root() { int floor = 0; int a1 = x[1] - x[0], a2 = x[2] - x[1]; while (a1 != a2) { if (a1 > a2) { int d = (a1 - 1) / a2; floor += d; x[2] -= d * a2; x[1] -= d * a2; } else { int d = (a2 - 1) / a1; floor += d; x[0] += d * a1; x[1] += d * a1; } Sort(); a1 = x[1] - x[0], a2 = x[2] - x[1]; } return floor; } bool operator==(const state ff) const { return (x[0] == ff.x[0]) && (x[1] == ff.x[1]) && (x[2] == ff.x[2]); } void GoUp(int floor) { while (floor) { int a1 = x[1] - x[0], a2 = x[2] - x[1]; if (a1 > a2) { int d = (a1 - 1) / a2; if (d > floor) d = floor; floor -= d; x[2] -= d * a2; x[1] -= d * a2; } else { int d = (a2 - 1) / a1; if (d > floor) d = floor; floor -= d; x[0] += d * a1; x[1] += d * a1; } Sort(); } } } u, v, fau, fav; int main() { int fu, fv, ans; while (~scanf("%d%d%d%d%d%d", &u.x[0], &u.x[1], &u.x[2], &v.x[0], &v.x[1], &v.x[2])) { u.Sort(); v.Sort(); fau = u; fav = v; fu = fau.Root(); fv = fav.Root(); if (fau == fav) { puts("YES"); if (fu > fv) { ans = fu - fv; u.GoUp(ans); } else if (fv > fu) { ans = fv - fu; v.GoUp(ans); } else ans = 0; int l = 0, r = min(fu, fv), mid, tmp; while (l <= r) { mid = (l + r) >> 1; fau = u; fav = v; fau.GoUp(mid); fav.GoUp(mid); if (fau == fav) { r = mid - 1; tmp = mid; } else l = mid + 1; } printf("%d\n", ans + (tmp << 1)); } else puts("NO"); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 1198 hdu 1401 搜索+剪枝 Sol..	下一篇：NYOJ 623 A*B Problem II

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: