10137. 「一本通 4.4 练习 4」跳跳棋

题意

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏:棋盘上有三颗棋子,分别在 $a,b,c$ 这三个位置。我们要通过最少的跳动把他们的位置移动成 $x,y,z$(注意:棋子是没有区别的)。
跳动的规则很简单,任意选一颗棋子,对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过一颗棋子。
写一个程序,首先判断是否可以完成任务。如果可以,输出最少需要的跳动次数。

思路

可以将状态视为一个三元组$(x,y,z)$。
  1. 中间往左跳:$(x,y,z) –> (2x-y,x,z)$
  2. 中间往右跳:$(x,y,z) –> (x,z,2z-y)$
  3. 左边往右跳:$if (y-x)<(z-y) then (x,y,z) –> (y,2y-x,z) Because ‘Only one chess piece is allowed to be skipped at a time.’$
  4. 右边往左跳:$if (y-x)>(z-y) then (x,y,z) –> (x,2y-z,y) Because ‘Only one chess piece is allowed to be skipped at a time.’$
可以注意到,操作1与操作2可以使该三元组区间扩大。而操作3与操作4可以使三元组区间缩小。 那我们将区间扩大的视为父亲,区间缩小的状态视为儿子。 那么我们可以由此构建一棵树。 先把深度大的节点移到深度小的节点,然后二分到LCA的距离,往上走n步和求根。 当然,这样是会TLE的,比如说这组数据:9998 9999 10000000 如果以1步每次的速度的话就需要跳 (10000000-9999)/(9999-9998)次嘛!所以就有一个优化:MOD。 这样就可以像gcd一样,跑得飞快。省去了很多时间。
#include<bits/stdc++.h>
#define int long long
#define MAXN 500010
using namespace std;
inline int read(){
    int res=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}
struct node{
    int x,y,z;
}endsss,tmps;
node make(int x,int y,int z){
    node pp;pp.x=x;pp.y=y;pp.z=z;return pp;
}
int GetFa(node p){
    int x=p.x,y=p.y,z=p.z,res=0;
    if(y-x<z-y){
        int pt=y-x;
        int zr=z-y;
        int kkk=zr%pt;res=zr/pt;
        if(kkk==0) --res,kkk+=pt;
        res+=GetFa(make(z-kkk-(y-x),z-kkk,z));
        return res;
        //-----X--Y-Z----------
    }else if(y-x>z-y){
        int pt=z-y;
        int zr=y-x;
        int kkk=zr%pt;res=zr/pt;
        if(kkk==0) --res,kkk+=pt;
        res+=GetFa(make(x,x+kkk,x+kkk+(z-y)));
        return res;
        //------X-Y---Z----------
    }else{
        endsss=p;
        return 0;
    }
}
void move(node p,int stp){
    int x=p.x,y=p.y,z=p.z;
    int pt=y-x,zr=z-y,cz,res=0;
    if(stp==0||pt==zr){endsss=p;return ;}
    if(pt<zr){
        res=zr/pt;
        cz=zr%pt;
        if(cz==0) cz=pt,--res;
        if(stp<res) move(make(z-cz-(res-stp+1)*pt,z-cz-(res-stp)*pt,z),0);
        else move(make(z-cz-pt,z-cz,z),stp-res);
        //X,Y,Z
    }else{
        res=pt/zr;
        cz=pt%zr;
        if(cz==0) cz=zr,--res;
        if(stp<res) move(make(x,x+cz+zr*(res-stp),x+cz+zr*(res-stp+1)),0);
        else move(make(x,x+cz,x+cz+zr),stp-res);
        //X,Y,Z 
    }
}
int tmp[5];
void Sort(int &x,int &y,int &z){
    tmp[1]=x;tmp[2]=y;tmp[3]=z;
    sort(tmp+1,tmp+3+1);
    x=tmp[1];y=tmp[2];z=tmp[3];
}
int a,b,c;
int x,y,z;
bool judge(node q,node p){
    if(q.x==p.x&&q.y==p.y&&q.z==p.z) return 0;
    return 1;
}
bool check(int mid){
    move(make(x,y,z),mid);tmps=endsss;
    move(make(a,b,c),mid);
    if(judge(tmps,endsss)==1) return 0;
    return 1;
}
signed main(){
    a=read();b=read();c=read();
    x=read();y=read();z=read();
    Sort(x,y,z);
    Sort(a,b,c);
    int stp1=GetFa(make(a,b,c));tmps=endsss;
    int stp2=GetFa(make(x,y,z));
    if(judge(tmps,endsss)==1){
        puts("NO");
        return 0;
    }
    if(stp1<stp2) move(make(x,y,z),stp2-stp1),x=endsss.x,y=endsss.y,z=endsss.z;
    else if(stp1>stp2) move(make(a,b,c),stp1-stp2),a=endsss.x,b=endsss.y,c=endsss.z;
    int l=0,r=min(stp1,stp2),mid,ans;
    while(l<=r){
        mid=l+r>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    puts("YES");
    write(ans*2+abs(stp1-stp2));putchar('\n');
    return 0;
}
//(x,y,z) --> (2x-y,x,z)
//(x,y,z) --> (x,z,2z-y)
//if (y-x)<(z-y) then (x,y,z) --> (y,2y-x,z) Because 'Only one chess piece is allowed to be skipped at a time.'
//if (y-x)>(z-y) then (x,y,z) --> (x,2y-z,y) Because 'Only one chess piece is allowed to be skipped at a time.'
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇