MENU

HDU 3830 Checkers

2019-06-30 • 阅读: 21 • 图论—LCA二分阅读设置

LCA+二分

题目链接: HDU 3830 Checkers

题意:给定3个点a,b,ca,b,c,每次操作可以跳到相邻点的对称位置。询问最终能否跳到x,y,zx,y,z(不考虑顺序) 如果能,输出最小步数.

我们不妨设 a<b<ca<b<c , bb可以跳到2ab2a-b,2cb2c-b,也即是往两边跳。
aacc可以往中间跳,我们可以发现如果ba==cbb-a==c-b的时候我们就不能往中间跳了。
我们可以这样想,把a,b,ca,b,c这三个的位置当成一个状态,而这个状态是二叉树中的一个节点,a和c往里跳相当于往父节点走,当ba==cbb-a==c-b时说明走到了根节点。bb往外跳相当去往子节点走,并且无穷无尽。

我们开始让aacc不断往里走,即不断往上寻找父节点,直至找到根节点。a,b,ca,b,cx,y,zx,y,z具有相同根节点时,答案有解,此时答案树上两点的最短距离。也即是可以转化寻找LCA。往上走的时候不能一步一步走,比如三个数1,2,1011,2,101,我们不能一步步翻(2,3,101)(2,3,101), (3,4,101)(3,4,101),这样太慢了,能不能直接翻到(99,100,101)(99,100,101)

首先要找到a,b,ca,b,cx,y,zx,y,z走到根节点所需步数,也即是深度,然后将其中深度大的减小至共同深度。设深度差disdis.二分答案,假设二分值为midmid,如果它们俩往上走midmid步就能处于共同坐标,那么可以r=midr=mid,缩小答案,继续二分。二分结束的 ll 即是它们俩其中一个走向LCA所需步数。最终 2l+dis2 * l+dis 即为答案。

另外题目有多组输入,也没看到题目有说。

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<bitset>
#include<cmath>
using namespace std;
const int N = 1e6 + 100;
typedef long long ll;
struct state{
    ll a, b, c, cnt;//cnt表示当前状态走到根节点需要的步数
    bool operator == (const state &o)const{
        return a == o.a&&b == o.b&&c == o.c;
    }
};
state st, ed;
void Sort(state &cur)
{
    if (cur.a > cur.b)swap(cur.a, cur.b);
    if (cur.a > cur.c) swap(cur.a, cur.c);
    if (cur.b > cur.c) swap(cur.b, cur.c);
}
state getRoot(state cur)
{
    cur.cnt = 0;
    ll d1 = cur.b - cur.a, d2 = cur.c - cur.b;
    while (d1 != d2)
    {
        ll t = 0;
        if (d1 > d2)
        {
            t = (d1 - 1) / d2;
            cur.b -= t*d2;
            cur.c -= t*d2;
        }
        else
        {
            t = (d2 - 1) / d1;
            cur.b += t*d1;
            cur.a += t*d1;
        }
        cur.cnt += t;
        Sort(cur);
        d1 = cur.b - cur.a, d2 = cur.c - cur.b;
    }
    return cur;
}
state solve(state cur, ll dis)
{
    ll d1 = cur.b - cur.a, d2 = cur.c - cur.b;
    while (dis&&d1!=d2)
    {
        ll t = 0;
        if (d1 > d2)
        {
            t = min((d1 - 1) / d2, dis);
            cur.b -= t*d2;
            cur.c -= t*d2;
        }
        else
        {
            t = min((d2 - 1) / d1, dis);
            cur.b += t*d1;
            cur.a += t*d1;
        }
        dis -= t;
        Sort(cur);
        d1 = cur.b - cur.a, d2 = cur.c - cur.b;
    }
    return cur;
}
int main()
{
    while (scanf("%lld%lld%lld", &st.a, &st.b, &st.c) != EOF)
    {
        scanf("%lld%lld%lld", &ed.a, &ed.b, &ed.c);
        st.cnt = 0, ed.cnt = 0;
        Sort(st);
        Sort(ed);
        state st1 = getRoot(st), ed1 = getRoot(ed);//首先找到根节点
        st.cnt = st1.cnt, ed.cnt = ed1.cnt;//所需步数
        if (st1 == ed1){
            puts("YES");
            ll dis = abs(st.cnt - ed.cnt);
            if (st.cnt > ed.cnt){//提至同一深度
                st = solve(st, dis);
            }
            else{
                ed = solve(ed, dis);
            }
            ll l = 0, r = min(st.cnt, ed.cnt);
            while (l < r)
            {
                ll mid = (l + r) >> (1LL);
                state ss = solve(st, mid);
                state ee = solve(ed, mid);
                if (ss == ee) r = mid;
                else l = mid + 1;
            }
            printf("%lld\n", 2 * l + dis);
        }
        else{
            puts("NO");
        }
    }

    return 0;
}

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码