考场上直接挂了,爆搜都爆炸,赛后仔细看了题解,终于AC了
先讲本题一开始拿到的思路,xyd是你谷上的略微简化版,将几个跳的公式列出来了(其实没什么大用,建议看洛谷的题目)。考虑转移的性质,首先由几种情况可以推出,由于每次只能跳一个棋子,其实相当于什么,中间的棋子可以往两边跳,而两边的棋子能往中间跳,一个状态可以由两个状态转移而来,这是什么,二叉树啊!(考试的时候最多也只能想到这里了)。
那就简单了,我们可以将起点以及终点的两个状态都看作树上的两个节点,然而有一个逆天性质:两边的棋子不能一直往中间跳!当两边中某一个棋子与中间棋子的距离为0时无法跳了!那么这两个状态都有一个根节点,也就是无线次跳以后无法再跳跃的状态!遍历时不断递归寻找根节点,顺便记录一下他们的在树上的深度,将深度较深的节点跳到同一高度,再二分答案要跳的距离即可。
Code:
#include <bits/stdc++.h>
#define ll long long
#define F(i,a,b) for(int i = (a);i<=(b);i++)
#define R register
using namespace std;
inline int read() {R int x=0,t=1;R char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=1e5+10;
const int INF=0x3f3f3f3f;//极大值
struct Node
{
int a[5];
bool operator !=(const Node& x) const
{
F(i,1,3) if(a[i]!=x.a[i]) return 1;
return 0;
}//判断两个Node是否相等的函数
}na,nb;//存放根状态
int A[N],B[N],dep1,dep2,tmp,ans;
Node getfa(int a[],int k){//a为当前状态,k为可以跳的次数
Node ans;//暂时存放下一步转移到的状态
int d1=a[2]-a[1],d2=a[3]-a[2];//记录三点之间的距离,主要是方便判断还能不能再跳了
F(i,1,3) ans.a[i]=a[i];//初始化ans
if(d1==d2) return ans;//距离刚好相等,直接跳掉
if(d1<d2){//跳右边的
int t=min(k,(d2-1)/d1);
k-=t;
tmp+=t;
ans.a[2]+=t*d1,ans.a[1]+=t*d1;
}
else{//跳左边的
int t=min(k,((d1-1)/d2));
k-=t;
tmp+=t;
ans.a[2]-=t*d2,ans.a[3]-=t*d2;
}
if(k) return getfa(ans.a,k);//k还没跳完
return ans;//k跳完了,直接返回
}
inline void solve()
{
//读入
F(i,1,3) A[i]=read();
F(i,1,3) B[i]=read();
//排序起始和结束状态,防止因为相对位置而寄掉
sort(A+1,A+1+3);
sort(B+1,B+1+3);
na=getfa(A,INF),dep1=tmp,tmp=0;//找到根状态
nb=getfa(B,INF),dep2=tmp,tmp=0;
//这里使用INF是为了节省码量以及方便些(好像是同一个事情)
if(na!=nb){//根状态根本不是同一个,绝对不行
puts("NO");
return;
}
if(dep1>dep2){//交换dep1和dep2,使其有序
swap(dep1,dep2);
F(i,1,3) swap(A[i],B[i]);
}
ans=dep2-dep1;//先只算跳到同一高度
na=getfa(B,ans);//B跳到与A同一高度时能到达的状态
F(i,1,3) B[i]=na.a[i];//赋值,方便二分时处理
int l=0,r=dep1;
//!注意,此时两个已经在同一高度了
for(;l<r;){//二分次数
int mid=(l+r)/2;
if(getfa(A,mid)!=getfa(B,mid)) l=mid+1;//当前的次数还不足以使两个状态跳成一个
else r=mid;
}
puts("YES");
cout << ans+2*l << '\n';//由于是两边都跳,所以要加两次
}
signed main()
{
solve();
return 0;
}
如果有爆炸的markdown请在贴下说出来