Uriel's Corner

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

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

丑陋的代碼見下

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

 -------Classify: BST & 模擬
 ----Description: 輸出一棵BST樹(按輸入建樹), 結(jié)點數(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樹, 再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;
}