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;
}