BZOJ2144 跳跳棋

2015.02.02 10:07 Mon| 8 visits oi_2015| 2015_刷题日常| Text

Solution

传说中,有一种神奇的跳跳棋。

它从一个状态开始只有至多三种转移方式:

  • 中间的棋子跳到左面
  • 中间的棋子跳到右面
  • 左右两边距离中间较近的棋子跳到中间(仅当两棋子与中间的棋子的距离不同)

将状态看作一棵树,分别将这三种转移方式看作左儿子右儿子和父亲(什么脑洞)。

于是我们可以类似辗转相除的做法在 $\mathcal O(\log s)$ 的时间内询问一个节点的 k 层父亲。

最后二分 LCA 就可得到答案。

Code

#include <bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f

struct node
{
    int a, b, c;
    void sort()
    {
        if (a > b) swap(a, b); if (a > c) swap(a, c); if (b > c) swap(b, c);
    }
    inline bool operator !=(const node &n) const
    {
        return a != n.a || b != n.b || c != n.c;
    }
}p, q;

node getfa(node x, int s, int *d = NULL)
{
    while (s)
    {
        int t1 = x.b - x.a, t2 = x.c - x.b;
        if (t1 == t2) break;
        if (t1 < t2)
        {
            int t = min(s, (t2 - 1) / t1);
            x.a += t * t1, x.b += t * t1;
            s -= t;
        }
        else
        {
            int t = min(s, (t1 - 1) / t2);
            x.c -= t * t2, x.b -= t * t2;
            s -= t;
        }
    }
    if (d) *d = inf - s;
    return x;
}

int main()
{
    cin >> p.a >> p.b >> p.c; p.sort();
    cin >> q.a >> q.b >> q.c; q.sort();
    int d1, d2;
    if (getfa(p, inf, &d1) != getfa(q, inf, &d2))
        return puts("NO"), 0;
    puts("YES");
    if (d1 < d2)
        swap(d1, d2), swap(p, q);
    int ans = d1 - d2;
    p = getfa(p, ans);
    int l = 0, r = d2, re = 0;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (getfa(p, mid) != getfa(q, mid))
            l = mid + 1;
        else r = mid - 1, re = mid;
    }
    cout << ans + re * 2 << endl;
    return 0;
}