意甲冠军：
有三件 所有其他棋子可以跳 不能分开的两个跳跃 当被问及状态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;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。