首页 > 代码库 > HDU 3830 Checkers
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<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<map> #include<set> #include<vector> #include<queue> #include<cstdlib> #include<ctime> #include<cmath> 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; }
HDU 3830 Checkers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。