左跳右跳题解(紫题)(洛谷P1852 跳跳棋)(超级详细注释版)

考场上直接挂了,爆搜都爆炸,赛后仔细看了题解,终于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请在贴下说出来

1 个赞

一道水紫题

2 个赞

大佬太酷啦

2 个赞

有一点问题
这里不应该是同一高度
应该是步数相同
其实是无法建树的(题主也没建树 会爆炸的)
步数不同的话会出现明明能撞到一起,却错过的情况
(应该是这样)
所以要把缺失的步数补全

相当于是把一棵 树压扁
压在数轴上完成

最后是把
a 一开始为了和 b 保持同一步数状态的步数 (← ans )
a、b 跳到同一 x、y、z 所花步数( ← l
加在一起
因为 a、b 都跳了 l
所以是 ans+l+l = ans+2*l

2 个赞