某岛

… : "…アッカリ～ン . .. . " .. .
June 3, 2014

ACM-ICPC Regional Asia Changchun 2013 Onsite

http://acmicpc.info/archives/1710
http://blog.renren.com/blog/271960376/918770698?bfrom=01020110200
https://gist.github.com/lychees/803f6e6a61c0f393660a

Problem D. Bathysphere

Brief description:

。。。x 轴上方给定一段折线。（一个分段线性可积函数）。
。。求 d 宽度的窗口内的最大面积。。。

Analysis:

Two Point 解方程

为了处理方便我们先准备一些辅助函数。。。

inline DB yy(int i, DB xx){ // 求横坐标为 xx 时的函数值。。
    return y[i] + (xx-x[i])*slope[i];
}

inline DB s(int i, DB st, DB ed){ //求 st 到 ed 这段区间的面积。。
    return (ed-st)*(yy(i,st)+yy(i,ed));
}

考虑 Two Point 的部分。。我们用 ll, rr 记录当前窗口的位置。。（rr-ll 总等于 d。。。再用 l， r 记录其左侧第一个结点的位置。。。

...
        for (;r<n-1;l+=ll==x[l+1],r+=rr==x[r+1]){
            int d = min(x[r+1]-rr, x[l+1]-ll); DB a = slope[r]-slope[l], b = (yy(r,rr)-yy(l,ll))*2; if (sgn(a)){
                DB dd = -b/(2*a); if (sgn(.0, dd) < 0 && sgn(dd, DB(d)) < 0){
                    checkMax(res, pre-(b*b/a/4));
                }
            }
            checkMax(res, pre += s(r,rr,rr+d)-s(l,ll,ll+d));
            ll+=d,rr+=d;
        }
...

。。就是每次我们取移动的步长 d…。。
。。然后解这个窗口内二次方程。。看极值点是否落在步长范围之内。。
。。更新完之后。。再移动两个端点。。。

我们直接在移动端点的同时再尝试更新一次答案。。（因为有可能出现方程退化情况。。

const int N = int(2e5) + 9;
int x[N], y[N], n; DB slope[N];
int D;

inline DB yy(int i, DB xx){
    return y[i] + (xx-x[i])*slope[i];
}

inline DB s(int i, DB st, DB ed){
    return (ed-st)*(yy(i,st)+yy(i,ed));
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Rush{
        RD(n); RD(); REP(i, n) RD(x[i], y[i]); RD(D)*=2;
        REP(i, n-1) slope[i] = (DB)(y[i+1]-y[i])/(x[i+1]-x[i]);

        DB res = 0, pre = 0; int r; REP_N(r, n-1){
            if (x[r+1] >= D) break;
            pre += s(r,x[r],x[r+1]);
        }

        checkMax(res, pre += s(r, x[r], D));
        int l=0,ll=0,rr=D;r+=rr==x[r+1];

        for (;r<n-1;l+=ll==x[l+1],r+=rr==x[r+1]){
            int d = min(x[r+1]-rr, x[l+1]-ll); DB a = slope[r]-slope[l], b = (yy(r,rr)-yy(l,ll))*2; if (sgn(a)){
                DB dd = -b/(2*a); if (sgn(.0, dd) < 0 && sgn(dd, DB(d)) < 0){
                    checkMax(res, pre-(b*b/a/4));
                }
            }
            checkMax(res, pre += s(r,rr,rr+d)-s(l,ll,ll+d));
            ll+=d,rr+=d;
        }

        OT(res/D/2);
    }
}

Problem J. Tri-war

Brief description:

。。给定 $$n$$ 个结点的一棵树。。每次询问三个点 $$u_0, u_1, u_2$$。。。
。。。点 $$v$$ 被 $$u_x$$ 支配 。。如果 $$\forall y \not = x, d(u_x, v) < d(u_y, v) $$。。 。。。问这三个点所在的支配集的大小。。。

Analysis:

倍增祖先 LCA 分类讨论

两个点的情况：

。先铺好模板。。显然就是。。。。。（。Codeforces Round #140 和 SPOJ 1486. The Ants in a Tree

。。考虑 2 个点的。。设函数 up(u, k) 表示 $$u$$ 结点向上 $$k$$ 个位置的结点。。。
。。那么通过 倍增祖先 我们就可以将中点找到。。。之后根据路径的奇偶性讨论一下即可。。。

最后要么是。。。

u0  --- m --- u1

（这种情况存在着一些 灰色结点。。（既不属于 $$u_0$$ 也不属于 $$u_1$$。。
要么是。。。

u0 --- m0 --- m1 --- u1

。。。复杂度 $$O(log(n))$$。。。（对于有边权的情况。。复杂度好像仍然是 $$O(log(n))$$ ？。。可以一边二分一边向上跳？）

。。。合理的使用 swap 以提高对讨论的抗性。。、、。。
（本题中 swap 的情况目测会茫茫多。。我们直接使用 ans[] 来记录答案。。）

void gao(int x, int y){
    int z = lca(x,y), dx = dep[x]-dep[z], dy = dep[y]-dep[z], dd = dx+dy;
    int d = dd/2; if (d>=dx) swap(x, y), swap(dx, dy); int m = up(x,d);
    if (dd&1) ans[x] = sz[m], ans[y] = n-ans[x];
    else ans[x] = sz[up(x,d-1)], ans[y] = d==dx?sz[up(y,d-1)]:n-sz[m];
}

三个点的情况：

。。。。现在讨论三个点的情况。。。
。。先按照 dep 对询问点排序。。

Case 1：链状

这种情况，$$u_0$$ 和 $$u_2$$ 都是它们各自对 $$u_1$$ 两个点时的答案。。。
。。。再把 $$u_1$$ 容斥出来。。。

void gao(int u0, int u1, int u2){
    gao(u1, u2); int g = n-ans[u1]-ans[u2]; gao(u0, u1);
    ans[u1] -= ans[u2]+g;
}
Case 2：叉状

我们求出三者的汇点 $$m$$。。并重新将询问的结点按照到 $$m$$ 的距离排序。。

                m = entry(u0, u1, u2); SRT(I, cmp);
Case 2-1：$$m$$ 被其中一个结点支配

这种情况，$$u_1$$ 和 $$u_2$$ 都是它们各自对 $$u_0$$ 两个点时的答案。。。
。。。类似的。。再把 $$u_0$$ 容斥出来。。。

                    gao(u1, u0); int g1 = n-ans[u0]-ans[u1];
                    gao(u0, u2); int g2 = n-ans[u0]-ans[u2];
                    ans[u0] = n-ans[u1]-ans[u2]-g1-g2;
Case 2-2：$$m$$ 是灰色结点

这种情况还得分两种情况讨论。（恰好两个结点到 $$m$$ 距离相等，和三个结点到 $$m$$ 距离都相等。。）
。。但是处理起来恰好可以做到完全一样。。。。

最后注意 HDU 直接交会 dfs() 爆栈。。。
这里我使用了汇编调栈。。。。

const int N = int(1e5)+9, M = 2*N, LV = 18;
int hd[N], suc[M], to[M];
int ST[LV+1][M], sz[N], fa[N][LV], st[N], dep[N];
int n, tt;

inline bool elder(int a, int b){
    return dep[a] < dep[b];
}

inline int lca(int a, int b){
    int l = st[a], r = st[b]; if (l > r) swap(l, r); ++r; int lv = lg2(r-l);
    return min(ST[lv][l], ST[lv][r-(1<<lv)], elder);
}

bool isa(int u1, int u2){
    return lca(u1, u2) == u1;
}

int entry(int x, int y, int w){
    int xy = lca(x, y); if (!isa(xy, w)) return xy; int xw = lca(x, w);
    return xw != xy ? xw : lca(y, w);
}

inline int d(int x, int y){
    return dep[x]+dep[y]-2*dep[lca(x,y)];
}

inline int up(int x, int t){
    for (int i=0;i<LV&&t;++i,t>>=1)
        if (t&1) x = fa[x][i];
    return x;
}

#define aa to[i^1]
#define bb to[i]
#define v bb

void dfs(int u = 1){
    ST[0][st[u] = ++tt] = u, sz[u] = 1;
    REP_G(i, u) if (!st[v]){
        dep[v] = dep[u] + 1, fa[v][0] = u; FOR(lv, 1, LV) fa[v][lv] = fa[fa[v][lv-1]][lv-1];
        dfs(v), ST[0][++tt] = u, sz[u] += sz[v];
    }
}

#undef v

int ans[N], m;

bool cmp(int a, int b){
    return d(a, m) < d(b, m);
}

void gao(int x, int y){
    int z = lca(x,y), dx = dep[x]-dep[z], dy = dep[y]-dep[z], dd = dx+dy;
    int d = dd/2; if (d>=dx) swap(x, y), swap(dx, dy); int m = up(x,d);
    if (dd&1) ans[x] = sz[m], ans[y] = n-ans[x];
    else ans[x] = sz[up(x,d-1)], ans[y] = d==dx?sz[up(y,d-1)]:n-sz[m];
}

void gao(int u0, int u1, int u2){
    gao(u1, u2); int g = n-ans[u1]-ans[u2]; gao(u0, u1);
    ans[u1] -= ans[u2]+g;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

int __size__ = 256 << 20; // 256MB
char *__p__ = (char*)malloc(__size__) + __size__;
__asm__("movl %0, %%esp\n" :: "r"(__p__));


    Rush{

        FOR_C(i, 2, RD(n)<<1){
            RD(aa, bb);
            suc[i] = hd[aa], hd[aa] = i, ++i;
            suc[i] = hd[aa], hd[aa] = i;
        }

        dfs();

        for ( int lv = 1 ; (1 << lv) <= tt ; lv ++ ){
            for ( int i = 1 ; i + (1 << lv)  <= tt + 1 ; i ++ )
                ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + (1<<(lv-1))], elder);
        }


        Rush{

            int u0, u1, u2; RD(u0, u1, u2);
            VI I; I.PB(u0), I.PB(u1), I.PB(u2); SRT(I, elder);

#define u0 I[0]
#define u1 I[1]
#define u2 I[2]

            if (isa(u0, u1) && isa(u1, u2)){
                gao(u0, u1, u2); // Case 1
            }
            else{
                m = entry(u0, u1, u2); SRT(I, cmp);

                if (d(u0,m) < d(u1,m)){ // Case 2.1
                    gao(u1, u0); int g1 = n-ans[u0]-ans[u1];
                    gao(u0, u2); int g2 = n-ans[u0]-ans[u2];
                    ans[u0] = n-ans[u1]-ans[u2]-g1-g2;
                }
                else{ // Case 2.2
                    gao(u0, u2), gao(u0, u1);
                }
            }
#undef u0
#undef u1
#undef u2

            printf("%d %d %d\n", ans[u0], ans[u1], ans[u2]);
        }

        fill(hd+1, hd+n+1, 0);
        fill(st+1, st+n+1, 0);
        tt = 0;
    }
}

Posted by xiaodao
Category: 线下比赛

« | »

  • Archives

    open all | close all