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

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

丑陋的代碼見下

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

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