跳跳棋

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2008 字
数轴上三颗棋子a,b,c，每次任选一颗跳过“
一本通
练习
正文

/*
原题：T1559 「一本通 4.4 练习 4」跳跳棋 (BZOJ 2144)
题意：数轴上三颗棋子 a,b,c，每次任选一颗跳过“中轴”棋子且只跳过一颗，求能否变成目标 x,y,z 及最少步数。
思路：将三数排序，状态视作一棵隐式二叉树（父状态为把较大间隔一侧的端点向中轴对称跳一步）。用欧几里得式向上走找到共同根；能到达当且仅当根相同，最少步数为两状态到 LCA 的距离和。
复杂度：状态深度 O(log 值域)，每次询问 O(log 值域)。
易错点：父状态唯一（d1<d2 时左端点跳、d1>d2 时右端点跳，d1==d2 即根无父）；比较时用排序后的三元组。
*/
#include <bits/stdc++.h>
using namespace std;
struct State{
    int a,b,c;
    State(int x,int y,int z):a(x),b(y),c(z){
        if(a>b) swap(a,b);
        if(a>c) swap(a,c);
        if(b>c) swap(b,c);
    }
    bool operator==(const State&o)const{ return a==o.a&&b==o.b&&c==o.c; }
    bool operator<(const State&o)const{
        if(a!=o.a) return a<o.a;
        if(b!=o.b) return b<o.b;
        return c<o.c;
    }
};
State one_up(State s){
    int d1=s.b-s.a,d2=s.c-s.b;
    if(d1<d2) return State(s.b,2*s.b-s.a,s.c);
    else if(d1>d2) return State(s.a,2*s.b-s.c,s.b);
    return s;
}
bool is_root(State s){
    return (s.b-s.a)==(s.c-s.b);
}
State get_root(State s){
    while(!is_root(s)) s=one_up(s);
    return s;
}
int depth(State s){
    int d=0;
    while(!is_root(s)){ s=one_up(s); d++; }
    return d;
}
State jump(State s,int k){
    while(k>0&&!is_root(s)){ s=one_up(s); k--; }
    return s;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,b,c;
    cin>>a>>b>>c;
    State S(a,b,c);
    int x,y,z;
    cin>>x>>y>>z;
    State T(x,y,z);
    if(!(get_root(S)==get_root(T))){
        cout<<"NO\n";
        return 0;
    }
    int dS=depth(S),dT=depth(T);
    if(dS>dT) S=jump(S,dS-dT);
    else if(dT>dS) T=jump(T,dT-dS);
    if(S==T){
        cout<<"YES\n"<<abs(dS-dT)<<'\n';
        return 0;
    }
    int base=min(dS,dT);
    map<State,int> anc;
    State cur=S;
    int dd=base;
    while(true){
        anc[cur]=dd;
        if(is_root(cur)) break;
        cur=one_up(cur);
        dd--;
    }
    cur=T;
    dd=base;
    while(anc.find(cur)==anc.end()){
        cur=one_up(cur);
        dd--;
    }
    int dLCA=dd;
    cout<<"YES\n"<<dS+dT-2*dLCA<<'\n';
    return 0;
}
跳跳棋

正文

一本通·提高篇的其它内容
