bzoj2144

二分+lca

我们把向中间缩看成向上爬，向两边走看成向下爬，那么就相当于找出两个状态的lca，如果相邻的差是(a,b),a<b，那么向中间走就是(a,b-a)或(b-a,a),这个东西很像更相减损术，那么我们直接用(b-1)/a算出来要走的步数，然后继续递归求lca，直到走不了为止。先爬inf步判断是否有共同的祖先，然后将比较深的爬到同一高度，然后二分爬的步数，每次求lca就行了。

思路很奇妙啊

#include<bits/stdc++.h>

using namespace std;

struct data {

    int a[];

    data() { memset(a, , sizeof(a)); }

    bool friend operator != (const data &a, const data &b) {

        for(int i = ; i < ; ++i) if(a.a[i] != b.a[i]) return true;

        return false;

    }

};

int dd, s1, s2;

int a[], b[];

data lca(int *a, int d)

{

    data ret;

    int t1 = a[] - a[], t2 = a[] - a[];

    for(int i = ; i < ; ++i) ret.a[i] = a[i];

    if(t1 == t2) return ret;

    if(t1 < t2)

    {

        int tmp = min(d, (t2 - ) / t1);

        d -= tmp;

        dd += tmp;

        ret.a[] += tmp * t1;

        ret.a[] += tmp * t1;

    }

    else

    {

        int tmp = min(d, (t1 - ) / t2);

        d -= tmp;

        dd += tmp;

        ret.a[] -= tmp * t2;

        ret.a[] -= tmp * t2;

    }

    return d ? lca(ret.a, d) : ret;

}

int main()

{

    for(int i = ; i < ; ++i) scanf("%d", &a[i]);

    for(int i = ; i < ; ++i) scanf("%d", &b[i]);

    sort(a, a + );

    sort(b, b + );

    data t1 = lca(a, 1e9);

    s1 = dd;

    dd = ;

    data t2 = lca(b, 1e9);

    s2 = dd;

    dd = ;

    if(t1 != t2)

    {

        puts("NO");

        return ;

    }

    if(s1 < s2)

    {

        swap(s1, s2);

        for(int i = ; i < ; ++i) swap(a[i], b[i]);

    }

    t1 = lca(a, s1 - s2);

    for(int i = ; i < ; ++i) a[i] = t1.a[i];

    int l = , r = 1e9, ans = ;

    while(r - l > )

    {

        int mid = (l + r) >> ;

        if(lca(a, mid) != lca(b, mid)) l = mid;

        else r = ans = mid;

    }

    if(ans && !(lca(a, ans - ) != lca(b, ans - ))) --ans;

    printf("YES\n%d\n", s1 - s2 +  * ans);

    return ;

}

巴特西

bzoj2144

最新文章

热门文章