[immortal title] [LCA] Luogu P1852 jump checkers

Link

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