题目链接:https://vijos.org/d/ybttg/p/5c28fb7df413624d6550c3b7

博主学习了另一位博主的题解后AC了这题,我只在这里简介地介绍一些关键点,具体请阅读我学习的博客(下称B):https://www.cnblogs.com/zhber/p/4055359.html

建议阅读顺序是先B后本文(B中有不理解的或许能从本文理解)

1.解题总流程是:判断是否能跳到->求最小步数

2.跳跳棋合法的跳只有三种,而非六种,容易被人忽略的是题中的这句话:"一次只允许跳过一颗棋子。"

.3.定义"溯源"操作:对应于B中介绍的两边的棋子往中间跳,B中讲的

"那么显然a往中间跳的次数就是(s1-1)/s2

而且a、b、c是不计顺序的，所以直接a+=s1*(s1-1)/s2 b+=s1*(s1-1)/2 就好了"　　相较于一步一步往中间跳,被称为"快速溯源"(B的这部分有笔误,正确的应该是:s1<s2时,让a跳(s2-1)/s1次而非(s1-1)/s2次)

这一点我举例说明:

对于-3 6 11 ab间距为9,bc间距为5,那么我们跳一次c变成-3 1 6

对于-3 1 6 ab间距为4,bc间距为5,那么我们跳一次a变成1 5 6

对于-3 1 6 ab间距为4,bc间距为1,那么我们跳三次c变成1 2 3

注意跳a(c)时ab(bc)间距不变,而bc(ab)间距减少的量为 跳跃次数*ab(bc)间距

4.这题被打上了倍增求LCA的标签,B中用的2分,本人用的方法是倍增,复杂度相同

5.测试数据提示:要注意输入后对三颗棋子排序,输入数据有坑人的例如4 5 1的输入数据,令人TL

如果只通过了1 3 5 6 10 12 14 16这8个样例并得到40分,那问题99%出在未对棋子排序(泪目,虚空Debug了好久)

 

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define per(i,a,b) for(ll i=a;i>=b;--i)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const ll maxn=1e5+10;

struct Piece{
    ll a,b,c,step;
    ll anse[3];
    Piece (ll a=0,ll b=0,ll c=0):a(a),b(b),c(c){
    //构造函数,用来求棋子的源头
        step=0;

        ll d1=b-a,d2=c-b;
        ll ta=a,tb=b,tc=c;
        while(d1!=d2){
            if(d1<d2){
                ll tStep=(d2-1)/d1,change=tStep*d1;
                step+=tStep;
                tb+=change,ta+=change;
                d2=tc-tb;
            }
            else{
                ll tStep=(d1-1)/d2,change=tStep*d2;
                step+=tStep;
                tc-=change,tb-=change;
                d1=tb-ta;
            }
        }
        anse[0]=ta,anse[1]=tb,anse[2]=tc;
    }

    void FindAnse(ll k){
    //将棋子变成 溯源k次后的状态(代码与构造函数很类似)
        ll d1=b-a,d2=c-b;
        step-=k;
        while(k){
            if(d1<d2){
                ll tStep=min(k,(d2-1)/d1),change=tStep*d1;
                k-=tStep;
                b+=change,a+=change;
                d2=c-b;
            }
            else{
                ll tStep=min(k,(d1-1)/d2),change=tStep*d2;
                k-=tStep;
                c-=change,b-=change;
                d1=b-a;
            }
        }    
    }

    bool CmpAnse(const Piece& t){return anse[0]==t.anse[0]&&anse[1]==t.anse[1]&&anse[2]==t.anse[2];}//比较源头是否相等
    bool operator ==(const Piece& t)const {return a==t.a&&b==t.b&&c==t.c;}
    bool operator !=(const Piece& t)const {return !((*this)==t);}
};

int main()
{
    
    /*ll a,b,c,x,y,z;
    cin>>a>>b>>c>>x>>y>>z;

    Piece s(a,b,c),tar(x,y,z);*/
    //对棋子排序 5555555555555555555
    ll arg[6];
    rep(i,0,5) cin>>arg[i];
    sort(arg,arg+3);
    sort(arg+3,arg+6);
    Piece s(arg[0],arg[1],arg[2]),tar(arg[3],arg[4],arg[5]);

    if(!s.CmpAnse(tar)) cout<<"NO"<<endl;
    else{
        if(s.step<tar.step) swap(s,tar);
        ll sub=s.step-tar.step;
        s.FindAnse(sub);    //倍增法第一步:同等高度
        
        ll ans=sub;
        if(s!=tar) {
            Piece bS(s),bTar(tar);

            ll maxstep=1;
            while((maxstep<<1)<s.step) maxstep<<=1;    //找到k使1+2+……+m(m=2^k)>=2^s.step - 1

            Piece tS(s),tTar(tar);
            while(1){
                if(maxstep<=s.step){
                    s.FindAnse(maxstep),tar.FindAnse(maxstep);    
                    if(s==tar){
                        s=bS,tar=bTar;
                    }
                    else{
                        tS=s,tTar=tar;                    
                        tS.FindAnse(1),tTar.FindAnse(1);
                        if(tS==tTar) {ans+=2;break;}//倍增法第二步:找到公共祖先的最高分叉点
                        else {
                            ans+=maxstep*2;
                            bS=s,bTar=tar;
                        }
                    }
                }
                maxstep>>=1;
            }
            ans+=maxstep*2;
        }

        cout<<"YES"<<endl;
        cout<<ans<<endl;
    }

    
    return 0;
}
/*
1 4 5
-3 6 11
ans:3
*/
/*
-1 0 3
1 4 5
ans:2

1 4 5
1 1000000000 1000000001
ans:999999996
*/

View Code