前置芝士
-
建模思想
-
倍增求 LCA 思想
这个题的建模太女少了啊！
Description
跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有三颗棋子，分别在 \(a, b, c\) 这三个位置。我们要通过最少的跳动把他们的位置移动成 \(x, y, z\)（注意：棋子是没有区别的）。
跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过一颗棋子。
判断是否可以完成任务。如果可以，输出最少需要的跳动次数。
Solution
观察棋子的移动规律，无非一下几种情况，以移动棋子 \((a, b, c)\) 为例：
- 中间棋子向两边跳，跳完分别会变成 \((2a - b, a, c)\) 和 \((a, c, 2c - b)\)
- 设 \(d_1 = b - a, d_2 = c - b\)。如果 \(d_1 > d_2\) ，那么 \(c\) 可以跳到 \(a, b\) 之间（注意此时 \(a\) 是不能跳的，因为会跨过两个棋子）；如果 \(d_1 < d_2\)， 那么 \(a\) 可以跳到 \(b, c\) 之间；如果 \(d_1 == d_2\)，显然都不能跳，可以作为终止条件
发现在两种跳法中，第一种跳法反过来就是第二种跳法；并且第一种跳法没有终止条件，第二种跳法有终止条件
我们不妨将其作为切入点
将两组棋子都向中间跳，记录下跳到终止条件的步数，如果能跳到同一个终止条件，就证明有解，反之无解
优化：
一步一步跳太慢了，发现 \(d_1, d_2\) 差距过大时，比如 \((1, 2, 8)\)，很多步都是在跳相同位置的两个量，不妨让我们直接算出要跳几步
假设 \(d_1 < d_2\)，那么每次调完后中间点离右边点的距离都会缩小 \(d_1\)，做一下除法求出跳几步能使 新距离 \(\le d_2\) 以此来减少复杂度，（注意特判一下模数为 \(0\) 的情况）
如何求跳的步数？
将每组棋子移动的每一个状态当做一个结点建树，那么如果有共同的终止状态，跳的步数就是两个状态间的距离。
(当然不是真的去建一棵树，而是要用相应的思想)
是不是非常像在求 LCA ？
模拟求LCA的过程：
想让他们跳到同一深度（离终止状态的步数相等）
二分跳的步数，找到有共同状态时跳了几步，然后输出答案就好了
Code
/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
int rig[4], gol[4];
int lca[4], to[4];
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
int Get_Step(int a, int b, int c) {
int d1 = b - a, d2 = c - b;
// cout<<a<<" "<<b<<" "<<c<<" "<<d1<<" "<<d2<<endl;
to[1] = a, to[2] = b, to[3] = c;
if(d1 == d2) return 0;
if(d1 < d2) {
int cnt = d2 / d1;
if(d2 % d1 == 0) cnt--;
return cnt + Get_Step(a + d1 * cnt, b + d1 * cnt, c);
} else {
int cnt = d1 / d2;
if(d1 % d2 == 0) cnt--;
return cnt + Get_Step(a, b - d2 * cnt, c - d2 * cnt);
}
}
void Update(int a, int b, int c, int step) {
if(!step) {
to[1] = a, to[2] = b, to[3] = c; return ;
}
// cout<<a<<" "<<b<<" "<<c<<" " << step<<endl;;
int d1 = b - a, d2 = c - b;
if(d1 < d2) {
int cnt = d2 / d1;
if(d2 % d1 == 0) cnt--;
if(step < cnt) cnt = step;
Update(a + d1 * cnt, b + d1 * cnt, c, step - cnt);
} else {
int cnt = d1 / d2;
if(d1 % d2 == 0) cnt--;
if(step < cnt) cnt = step;
Update(a, b - d2 * cnt, c - d2 * cnt, step - cnt);
}
}
bool check(int step) {
Update(rig[1], rig[2], rig[3], step);
memcpy(lca, to, sizeof to);
Update(gol[1], gol[2], gol[3], step);
if(lca[1] == to[1] && lca[2] == to[2] && lca[3] == to[3]) return true;
else return false;
}
signed main()
{
for(int i = 1; i <= 3; ++i) rig[i] = read();
for(int i = 1; i <= 3; ++i) gol[i] = read();
sort(rig + 1, rig + 4), sort(gol + 1, gol + 4);
int step1 = Get_Step(rig[1], rig[2], rig[3]);
memcpy(lca, to, sizeof to);
// cout<<lca[1]<<" "<<lca[2]<<" "<<lca[3]<<endl;
int step2 = Get_Step(gol[1], gol[2], gol[3]);
// cout<<to[1]<<" "<<to[2]<<" "<<to[3]<<endl;
if(lca[1] != to[1] || lca[2] != to[2] || lca[3] != to[3]) { printf("NO"); return 0; }
if(step1 > step2) Update(rig[1], rig[2], rig[3], step1 - step2), memcpy(rig, to, sizeof to);;
if(step2 > step1) Update(gol[1], gol[2], gol[3], step2 - step1), memcpy(gol, to, sizeof to);;
int L = 0, R = min(step1, step2), ans;
while(L <= R) {
int mid = L + R >> 1;
if(check(mid)) ans = mid, R = mid - 1;
else L = mid + 1;
}
printf("YES\n%lld", ans * 2 + abs(step1 - step2));
return 0;
}