# [immortal title] [LCA] Luogu P1852 jump checkers

That's a good question,

## subject ## solution

From "only one chess piece can be skipped at a time", an important property of this question is obtained:
There are at most three jumping methods for these three chess pieces at a certain time: the middle piece jumps left and right, or the piece closer to the middle piece jumps to the middle. like this When AB=BC, there are only two jumping methods (A cannot jump to the position of A ')
When the outside point jumps in, the range of these three pieces will be smaller and smaller until there is a situation that they can't jump in.
We find that the state at this time is unique: the three pieces cannot reproduce the relative state at this time elsewhere.
We take this state as the root;
Judge the roots of two groups of pieces. If they are different, it means that they can never look like another group; Direct output No.
If they can be placed in the same root, then we need LCA.
The first group of pieces will eventually move to the state of LCA and then to the state of the second group of pieces.

###### be careful
• For LCA, we can't use multiplication, but we can use dichotomy to accelerate
• In case AB is close and BC is far away, it can be optimized here, like this: When AB moves, just add (k-1)*AB directly. (translation method) since there is no special difference between chess pieces, you don't need to care about whether the AB position is exchanged.

## Code

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int astep,bstep;
struct asdf{
int a,b,c;
} A,B,Fka,Fkb;
void px(asdf &LL){   //Sort
if(LL.a>LL.b) swap(LL.a,LL.b);
if(LL.a>LL.c) swap(LL.a,LL.c);
if(LL.b>LL.c) swap(LL.b,LL.c);
}
int getroot(int &aa,int &bb,int &cc){  //Find root
int step = 0,l,jl1,jl2;
while(aa+cc!=bb*2){  //If AB= AC
jl1 = bb-aa;//AB
jl2 = cc-bb;//BC
if(jl1<jl2){  //Left inward
l = jl2/jl1;  //How many times can you jump
if(jl2%jl1 == 0) --l;
aa += jl1*l;  //translation
bb += jl1*l;
step += l;  //Statistical steps
}
else {  //Right inward / / ditto
l = jl1/jl2;
if(jl1%jl2 == 0) --l;
bb -= jl2*l;
cc -= jl2*l;
step += l;
}
}
return step;
}
asdf jummp(asdf ll,int step){  //Skip step on ll status
int l,jl1,jl2;
while(step){
jl1 = ll.b-ll.a;  //It's the same as finding the root. I don't want to comment
jl2 = ll.c-ll.b;
if(jl1<jl2){
l = jl2/jl1;
if(jl2%jl1 == 0) --l;
l = min(l,step);
ll.a += jl1*l;
ll.b += jl1*l;
step -= l;
}
else {
l = jl1/jl2;
if(jl1%jl2 == 0) --l;
l = min(l,step);
ll.b -= jl2*l;
ll.c -= jl2*l;
step -= l;
}
}
return ll;
}
bool db(asdf aa,asdf bb){  //Compare whether the two states are the same
if(aa.a!=bb.a||aa.b!=bb.b||aa.c!=bb.c) return 0;
return 1;
}
int main(){
scanf("%d%d%d%d%d%d",&A.a,&A.b,&A.c,&B.a,&B.b,&B.c);
px(A); px(B);  //sort
Fka = A;   //Temporary storage
Fkb = B;
astep = getroot(Fka.a,Fka.b,Fka.c);   //Find root
bstep = getroot(Fkb.a,Fkb.b,Fkb.c);
if(db(Fka,Fkb)==0){  //Different roots
printf("NO");
return 0;
}
if(astep > bstep) A = jummp(A,astep-bstep);  //Jump to the same height first
else B = jummp(B,bstep-astep);
int l = 0,r = min(astep,bstep), mid;  //Dichotomy
while(l<r){
mid = (l+r)/2;
Fka = jummp(A,mid);
Fkb = jummp(B,mid);
if(db(Fka,Fkb) == 1) r = mid;  //Jump mid*2 steps to reach
else l = mid+1;   //no way
}
printf("YES\n%d",max(astep-bstep,bstep-astep)+r*2);
}```

Tags: Graph Theory

Posted by phpScott on Tue, 24 May 2022 02:25:07 +0300