Uriel's Corner

    5.15 2011復旦ACM省賽, 悲劇, 第5個銅... 繼續全銅悲劇... 膜拜jjllqq學長, 全銅后最后銀獎結束ACM生涯... ...

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

丑陋的代碼見下

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

 -------Classify: BST & 模擬
 ----Description: 輸出一棵BST樹(按輸入建樹), 結點數<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樹, 再BFS一層一層輸出該樹
 ---------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)  //沒有這句導致比賽時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;
}