1 条题解
-
0
一个比较巧妙的题。
考虑每次跳跃只能跳过一个棋子,所以只有两种情况。
一种是中间的向两边跳,一种是两边向中间跳。
前者会让棋子的距离加大,后者会变小,考虑后者。
容易发现两边向中间跳的方案是唯一的,离中间距离小的跳到另一边。
如果两边距离相等,就不能向中间跳了。
所以两个状态都一只向中间跳,看是否相等。
考虑怎么找最小步数。
假设 。
如果 ,那么向中间跳两边的距离变成 ,实际上就是辗转相减。
可以辗转相除优化一下。
然后考虑两种状态一起跳,比如到了某个时候相等,找到那个状态即可。
类似于找 LCA,先跳到深度相同,然后二分一下向上跳就好了。
#include<bits/stdc++.h> using namespace std; struct Node{int a,b,c;}; struct hzy{int l,r;}; bool operator !=(Node a,Node b){return a.a!=b.a||a.b!=b.b||a.c!=b.c;} bool operator ==(hzy a,hzy b){return a.l==b.l&&a.r==b.r;} int Sum; Node get_rt(int a,int b,int c){ int x=b-a,y=c-b; if(x==y)return (Node){a,b,c}; if(x>y){ int s=(x-1)/y; Sum+=s; return get_rt(a,b-s*y,c-s*y); } else{ int s=(y-1)/x; Sum+=s; return get_rt(a+s*x,b+s*x,c); } } hzy jump(hzy a,int b){ // cerr<<a.l<<' '<<a.r<<' '<<b<<endl; if(!b)return a; if(a.l>a.r){ int s=(a.l-1)/a.r; if(s>b)return (hzy){a.l-b*a.r,a.r}; return jump((hzy){a.l-s*a.r,a.r},b-s); } else{ int s=(a.r-1)/a.l; // cerr<<s<<endl; if(s>b)return (hzy){a.l,a.r-b*a.l}; return jump((hzy){a.l,a.r-s*a.l},b-s); } } int a[5],b[5],ans,sum1,sum2; int main(){ for(int i=1;i<=3;i++)scanf("%d",&a[i]); for(int i=1;i<=3;i++)scanf("%d",&b[i]); sort(a+1,a+4),sort(b+1,b+4); Node rt1=get_rt(a[1],a[2],a[3]);sum1=Sum,Sum=0; Node rt2=get_rt(b[1],b[2],b[3]);sum2=Sum; if(rt1!=rt2)return puts("NO"),0; hzy p,q; p.l=a[2]-a[1],p.r=a[3]-a[2],q.l=b[2]-b[1],q.r=b[3]-b[2]; if(sum2>sum1)swap(sum1,sum2),swap(p,q); // cerr<<q.l<<' '<<q.r<<' '<<p.l<<' '<<p.r<<endl; if(sum1>sum2){ ans+=sum1-sum2; p=jump(p,sum1-sum2); } int l=0,r=sum2; // cerr<<q.l<<' '<<q.r<<' '<<p.l<<' '<<p.r<<endl; while(l+1<r){ int mid=l+r>>1; if(jump(p,mid)==jump(q,mid))r=mid; else l=mid; } if(jump(p,l)==jump(q,l))ans+=l*2; else ans+=r*2; puts("YES"); printf("%d",ans); return 0; }
- 1
信息
- ID
- 88
- 时间
- 500ms
- 内存
- 259MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者