Uriel's Corner

    5.15 2011復(fù)旦ACM省賽, 悲劇, 第5個(gè)銅... 繼續(xù)全銅悲劇... 膜拜jjllqq學(xué)長(zhǎng), 全銅后最后銀獎(jiǎng)結(jié)束ACM生涯... ...

    正式賽, 照舊我從前看, MEC從中間看, 光光先建工程然后從中間開(kāi)始。發(fā)現(xiàn)A理解不能, 就先看了B, 發(fā)現(xiàn)G快被板刷了, 于是去看, 17min 1A。然后繼續(xù)看完C。光光開(kāi)始敲J, 說(shuō)是DP, 敲完后說(shuō)沒(méi)有想清楚, 坐一邊接著想去了。發(fā)現(xiàn)A有幾個(gè)隊(duì)出了, 硬著頭皮努力理解。還是有點(diǎn)不確定, 就和MEC討論了一下, 終于理解了, 由于一貫對(duì)數(shù)學(xué)題很恐懼, 就交給MEC推公式了。E有人出了, 就看E去了。光光說(shuō)J(DP)那題不太靠譜, 先想D(字符串)去。跟我說(shuō)了下大概思路, 后綴數(shù)組, 想了一下, 比較靠譜。當(dāng)了下碼工, 幫光光敲了后綴數(shù)組模板, 然后聽(tīng)MEC說(shuō)A的思路。光光的D題WA了, 查了幾遍沒(méi)有發(fā)現(xiàn)問(wèn)題, 寫(xiě)了個(gè)暴力程序?qū)ε? 發(fā)現(xiàn)是我模板有個(gè)變量敲錯(cuò)了..- -||..改了后TLE了...于是我先JAVA敲A, 敲完想著會(huì)不會(huì)TLE, 于是想打表, 糾結(jié)了一會(huì)寫(xiě)了打表要用的一段代碼后發(fā)現(xiàn)500個(gè)答案秒出, 于是擦掉了打表部分, 直接交了, 171min 1A。光光繼續(xù)改D, 終于199min 5A。然后決定去敲B, 跟MEC討論了下之后決定先讀入, 建BST樹(shù), 然后按從小到大排序后可得到每個(gè)結(jié)點(diǎn)距離最左邊的位置(即為該結(jié)點(diǎn)排序后在結(jié)點(diǎn)中的位置)。然后BFS這棵樹(shù), 一層一層輸出, 大概4h20min的時(shí)候出了sample, 結(jié)果WA。各種測(cè)數(shù)據(jù)沒(méi)有發(fā)現(xiàn)問(wèn)題, 最后10min的時(shí)候跟光光說(shuō)了B, 光光出的case沒(méi)有過(guò)。但是單case的話可以過(guò), 于是懷疑是初始化問(wèn)題。各種初始化之后依然沒(méi)有過(guò)那個(gè)sample, 一直糾結(jié)到比賽結(jié)束... ...
    組隊(duì)賽依然很不給力, 我的問(wèn)題是雖然敲模板速度還過(guò)得去, 但是比較密的代碼很有可能敲錯(cuò), 數(shù)學(xué)題, DP都過(guò)分依賴隊(duì)友, JAVA還不是特別熟練...etc
    不甘心, 只好用光光的U盤(pán)拷了代碼回來(lái)繼續(xù)看。發(fā)現(xiàn)BFS那里l==r的時(shí)候會(huì)有下標(biāo)越界的問(wèn)題, 只要加一句話判一下就行, 晚上終于在UVA上A掉了。

丑陋的代碼見(jiàn)下

/**//*
 2011 ACM-ICPC Shanghai Invitational B Boring Homework

 -------Classify: BST & 模擬
 ----Description: 輸出一棵BST樹(shù)(按輸入建樹(shù)), 結(jié)點(diǎn)數(shù)<80
 ---Sample Input:

 3----------------//3 cases
 3 3 1 2----------//n nodes, value of each node
 6 4 5 6 1 3 2
 5 3 4 5 2 1

 --Sample Output:

 Case #1:
 +-o
 |
 o+
 |
 o
 Case #2:
 +--o+
 |   |
 o-+ o+
 |  |
 +o  o
 |
 o
 Case #3:
 +o+
 | |
 +o o+
 |   |
 o   o

 -----Time Limit: 1000Ms
 ---------Source: 2011 ACM-ICPC Shanghai Invitational B
 -------Solution: 建一棵BST樹(shù), 再BFS一層一層輸出該樹(shù)
 ---------Status: AC C++ 
 -----------Date: 2011.05.15
 ------Reference: NULL
 -----------Code: 
 */

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1000

struct node {
    int f, l, r, idx, pos;
} t[N];

struct M {
    int id, a, pos;
} p[N];

int n, nt, q[N * 2][2];
bool flg[N];

bool cmp(M a, M b) {
    return a.a < b.a;
}

void insert(int idx, int rt) {
    if (idx < t[rt].idx) {
        if (~t[rt].l)
            insert(idx, t[rt].l);
        else {
            t[rt].l = nt;
            t[nt].f = rt;
            t[nt].idx = idx;
            t[nt].l = t[nt].r = -1;
            ++nt;
            return;
        }
    } else {
        if (~t[rt].r)
            insert(idx, t[rt].r);
        else {
            t[rt].r = nt;
            t[nt].f = rt;
            t[nt].idx = idx;
            t[nt].l = t[nt].r = -1;
            ++nt;
            return;
        }
    }
}

void BFS() {
    int i, l = 0, r = 1, cen;
    char mp[2000], sk[2000];
    q[0][0] = 0;
    q[0][1] = 0;
    i = 0;
    memset(mp, 0x00, sizeof(mp));
    memset(sk, 0x00, sizeof(sk));
    if (~t[0].l) {
        q[r][1] = 1;
        q[r++][0] = t[0].l;
        for (; i < t[t[0].l].pos; ++i)
            mp[i] = ' ';
        mp[i++] = '+';
        for (; i < t[0].pos; ++i)
            mp[i] = '-';
    }
    mp[i++] = 'o';
    if (~t[0].r) {
        q[r][1] = 1;
        q[r++][0] = t[0].r;
        for (; i < t[t[0].r].pos; ++i)
            mp[i] = '-';
        mp[i++] = '+';
    }
    ++l;
    //printf("l=%d r=%d\n",l,r);
    puts(mp);
    cen = 1;
    while (l < r) {
        memset(mp, 0x00, sizeof(mp));
        memset(sk, 0x00, sizeof(sk));
        i = 0;
        while (q[l][1] == cen) {
            //printf("l=%d r=%d\n", l, r);
            if (l == r)  //沒(méi)有這句導(dǎo)致比賽時(shí)WA到死... ...
                break;
            if (t[q[l][0]].l >= 0) {
                //printf("q=%d qq=%d\n",q[l][0],t[q[l][0]].l);
                q[r][1] = cen + 1;
                //printf("q=%d qq=%d\n",q[l][0],t[q[l][0]].l);
                q[r++][0] = t[q[l][0]].l;
                //printf("l=%d r=%d\n",l,r);
                //printf("q=%d qq=%d\n",q[l][0],t[q[l][0]].l);
                for (; i < t[t[q[l][0]].l].pos; ++i)
                    mp[i] = ' ';
                //printf("q=%d qq=%d\n",q[l][0],t[q[l][0]].l);
                mp[i++] = '+';
                //printf("q=%d qq=%d\n",q[l][0], t[q[l][0]].l);
                for (; i < t[q[l][0]].pos; ++i)
                    mp[i] = '-';
            }
            i = t[q[l][0]].pos;
            sk[i] = '|';
            mp[i++] = 'o';
            if (~t[q[l][0]].r) {
                //if(q[l][0]==6) puts("*****");
                q[r][1] = cen + 1;
                q[r++][0] = t[q[l][0]].r;
                for (; i < t[t[q[l][0]].r].pos; ++i)
                    mp[i] = '-';
                mp[i++] = '+';
            }
            ++l;
        }
        ++cen;
        for (i = n;; --i) {
            if (mp[i] > 0)
                break;
        }
        for (; i >= 0; --i) {
            if (!mp[i])
                mp[i] = ' ';
        }
        for (i = n;; --i) {
            if (sk[i] > 0)
                break;
        }
        for (; i >= 0; --i) {
            if (!sk[i])
                sk[i] = ' ';
        }
        puts(sk);
        puts(mp);
    }
}

int main() {
    //freopen("d:\\in.txt","r",stdin);
    int cse, i, g = 1;
    scanf("%d", &cse);
    while (cse--) {
        scanf("%d", &n);
        nt = 0;
        for (i = 0; i < n; ++i) {
            p[i].a = 0;
            p[i].id = 0;
            p[i].pos = 0;
            t[i].f = t[i].l = t[i].r = -1;
            t[i].pos = t[i].idx = 0;
        }
        for (i = 0; i < n; ++i) {
            scanf("%d", &p[i].a);
            if (!i) {
                t[0].f = -1;
                t[0].idx = p[0].a;
                t[0].l = t[0].r = -1;
                nt++;
            } else {
                insert(p[i].a, 0);
            }
            p[i].id = i;
        }
        //        for(i=0;i<n;++i) {
        //            printf("idx=%d l=%d r=%d f=%d\n",t[i].idx,t[i].l,t[i].r,t[i].f);
        //        }
        sort(p, p + n, cmp);
        for (i = 0; i < n; ++i) {
            p[p[i].id].pos = i;
            t[p[i].id].pos = i;
        }
        printf("Case #%d:\n", g++);
        BFS();
    }
    return 0;
}