JZOJ.4701【NOIP2016提高A组模拟8.15】Throw

Problem

Description

Input

Output

Sample Input

1 2 3 0 3 5

Sample Output

YES 2

Data Constraint

Solution

我们设状态为一棵树，将起点、终点两个状态的边上2点向中间靠，到l=r的时候，就不能够继续向中间靠了，设此时状态为根节点。 就这样，如果l>r，那么l=l mod r，然后r=原来的l。这样很像辗转相除法。 我们先判断YES还是NO.NO的情况当且仅当起点与终点的根三个人的坐标有任意一个不相同。 此时我们求一下起点和终点的LCA。我们先求出起点和终点的深度f1,f2，然后当f1>f2时，f1向上走 2i 步，如果深度没有f2深，退回来再向上走 2i−1 步，如此类推，直到f1=f2为止（其他情况自己想）。 这个时候我们再将起点和终点(此时f1=f2)向上走 2i 步，如果发现到了或过了LCA，就退回来，再向上走 2i−1 步，如此类推。直到不能够再走为止（图中的蓝色的两个点都是LCA的儿子，走到这就不能够再走了），此时将起点和终点总共走的步数加起来再+2就是答案。因为此时两个点只需再向上走一步就可以到达LCA。

Code

#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; int a1,a2,a3,b1,b2,b3,l1,r1,l2,r2,c1,c2,d1,d2,f1,f2,f3,f4,ans; int _2[32],i,j,l,r,x,y,p1,p2,p3,p4; void px() { if (a1>a2) swap(a1,a2); if (a2>a3) swap(a2,a3); if (a1>a2) swap(a1,a2); if (b1>b2) swap(b1,b2); if (b2>b3) swap(b2,b3); if (b1>b2) swap(b1,b2); } int deep(int l,int r) { int u=0,t; if (l<r) swap(l,r); while (l!=r) { if (l%r!=0) u+=l/r; else { u+=l/r-1; //最后一步不能够跳，因为已经有2人在一点上。 l=r; break; } t=l%r; l=r; r=t; } c2=l; return u; } void reach(int &l,int &r,int u) { while (u>0) { if (l==r) break; if (l>r) { if (l-u*r>0) { l-=u*r; break; } u-=l/r; if (l%r==0) { l=r; break; } else l=l%r; } else { if (r-u*l>0) { r-=u*l; break; } u-=r/l; if (r%l==0) { r=l; break; } else r=r%l; } } } int main() { _2[0]=1; fo(i,1,30) _2[i]=_2[i-1]*2; scanf("%d%d%d",&a1,&a2,&a3); scanf("%d%d%d",&b1,&b2,&b3); px(); if (a1==b1 && a2==b2 && a3==b3) { printf("YES\n0"); return 0; } l1=a2-a1;r1=a3-a2; l2=b2-b1;r2=b3-b2; f1=deep(l1,r1);c1=c2; f2=deep(l2,r2); if (c1!=c2) { printf("NO"); return 0; } if (f1<f2) { swap(f1,f2); swap(l1,l2); swap(r1,r2); } j=log2(f1-f2); fd(i,j,0) { p1=l1;p2=r1; reach(p1,p2,_2[i]); f3=deep(p1,p2); if (f3>=f2) { f1=f3; l1=p1;r1=p2; ans+=_2[i]; if (f3==f2) break; } } if (l1==l2 && r1==r2) { printf("YES\n"); printf("%d",ans); return 0; } j=log2(f1); fd(i,j,0) { p1=l1;p2=r1;p3=l2;p4=r2; reach(p1,p2,_2[i]); reach(p3,p4,_2[i]); if (p1!=p3 || p2!=p4) { l1=p1;r1=p2; l2=p3;r2=p4; ans+=_2[i]+_2[i]; } } ans+=2; printf("YES\n"); printf("%d",ans); }

——2016.8.16