今天下午 1:30 - 4:30，PAT 甲級考試腺占，也是今年秋季之前的最后一次考試機(jī)會了域帐。

我在離考試結(jié)束還有 22 分鐘時拿到了 100 分，出考場的時候老師問我多少分悴侵，要不要等證書瞧剖。我說 100 分，感受到了各位考生的眼神投過來可免。抓于。。

現(xiàn)在趁還沒忘完浇借，回顧一下這幾道題是怎么寫的捉撮。

03 月 19 日更新：發(fā)現(xiàn)考試平臺可以查看自己考試時提交的代碼，于是也摘下來咯妇垢〗碓猓考試時間緊，拿分是最重要的事闯估，代碼難免有很丑的地方灼舍，請各位看官包涵哈。

A 20分 20分鐘

只用了 20 分鐘涨薪，一次通過骑素。

很奇葩的題，有些地方我覺得有坑尤辱，但是沒管砂豌，竟然過了。給一個數(shù)字 D光督，然后讓你輸出這個數(shù)字第多少次的表示方法阳距，比如 D 是 8，第一次說成 "81"结借，就是 8 有 1 個筐摘，第二次 “8111”，8 有 1 個船老，1 有 1 個咖熟；第三次 “8113” 這樣子。

我上來就是用字符串處理的柳畔，字符串開到最大馍管，然后一點一點比，后一個數(shù)跟前一個不一樣就輸出前面的數(shù)字及個數(shù)薪韩。寫的時候突然想到如果 1 連續(xù)出現(xiàn)了 >= 10 次怎么辦确沸，輸出 “1xx” 嗎？沒管這個俘陷，交上去罗捎，沒試幾次，過了拉盾。桨菜。。

# include <cstdio>
# include <cstring>

char s[1000000];
char s0[1000000];
char d;
int N;


int main(){
    int dt;
    scanf("%d %d", &dt, &N);
    d = '0' + dt;
    s[0] = d; s[1] = '\0';

    char lastc; 
    int lastn, idxs0;
    for(int i = 2; i <= N; i ++){
        lastc = s[0];
        lastn = 1;
        idxs0 = 0;
        for(int j = 1; ; j ++){
            if(s[j] != lastc){
                if(s[j] == '\0'){
                    s0[idxs0 ++] = lastc;
                    s0[idxs0 ++] = lastn + '0';
                    s0[idxs0 ++] = '\0';
                    break;
                }else{
                    s0[idxs0 ++] = lastc;
                    s0[idxs0 ++] = lastn + '0';
                    lastc = s[j];
                    lastn = 1;
                }
            }else{
                lastn ++;
            }
        }
        strcpy(s, s0); 
    }

    printf("%s", s);

    return 0;
}

B 25分 40分鐘

給許多個“考生 分?jǐn)?shù) 學(xué)凶狡”倒得，要通過它的要求計算出各個學(xué)校的 XXX（該學(xué)校學(xué)生的 頂級成績和 * 1.5 + 甲級成績 + 乙級成績 / 1.5） 和 Ns （考試人數(shù)），然后對各個學(xué)校排名次夭禽，XXX 一樣的同名次屎暇，這些的輸出順序再按照 Ns 和 學(xué)校名字典順序決定。

學(xué)校的各項分?jǐn)?shù)信息當(dāng)然用結(jié)構(gòu)體就可以了驻粟。很煩的就是學(xué)校名字符串怎么處理根悼，我為了查找校名快，用了很暴力的辦法蜀撑，把學(xué)校名和學(xué)校信息的 struct 對應(yīng)起來：

• 一個 map<str, int>挤巡， Key 是校名字符串，Value 是學(xué)校信息結(jié)構(gòu)體的 idx （剛開始想用索引表示酷麦，后來發(fā)現(xiàn)一旦排序就亂了矿卑，又在結(jié)構(gòu)體中加了一個字段 idx）；

• 后來發(fā)現(xiàn)自己不會從 map 中按照 value 查找值沃饶，尷尬了母廷，只好又存了一個校名數(shù)組 schName[n][7]轻黑，存 idx 對應(yīng)的校名。很繁瑣很丑琴昆，但是為了一次就迅速通過氓鄙，我忍了。业舍。抖拦。

這道題我提交了約 4~5 次才通過，總是漏掉一些奇怪的細(xì)節(jié)條件舷暮。我看到提交列表里态罪，第一題的通過率是 0.2 左右，這道題則只有驚人的 0.07……還好我試了幾次就通過了下面，這時考試才過去 1 個小時复颈。

# include <cstdio>
# include <cstdlib>
# include <string>
# include <cstring>
# include <map>

using namespace std;

typedef map<string, int> str_int_map;
str_int_map indexmap;

struct schinfo{
    int idx;
    int scoreT, scoreA, scoreB;
    int ns;
    int TWS;
}schs[100000];

char schName[100000][7];

int N;
int indexm = 0;

int compar(const void* a, const void *b){
    schinfo *aa = (schinfo*)a, *bb = (schinfo*)b;
    if(aa->TWS != bb->TWS){
        return bb->TWS - aa->TWS;
    }else if(aa->ns != bb->ns){
        return aa->ns - bb->ns;
    }else{
        return strcmp(schName[aa->idx], schName[bb->idx]);
    }
}

int main(){
    scanf("%d", &N);
    char id[7], school[7];
    string sch;
    int score;

    str_int_map::iterator iterf;
    int idx;

    for(int i = 0; i < N; i ++){
        scanf("%s %d %s", id, &score, school);
        for(int j = 0; school[j] != '\0'; j ++){
            if(school[j] >= 'A' && school[j] <= 'Z'){
                school[j] = school[j] - 'A' + 'a';
            }
        }
        sch = school;

        iterf = indexmap.find(sch);
        if(iterf == indexmap.end()){ //not have
            idx = indexm;
            schs[idx].idx = idx;
            indexmap[sch] = indexm ++;
            strcpy(schName[idx], school);
        }else{ //already in 
            idx = iterf->second;
        }

        schs[idx].ns ++;
        if(id[0] == 'T'){
            schs[idx].scoreT += score;
        }else if(id[0] == 'A'){
            schs[idx].scoreA += score;
        }else{
            schs[idx].scoreB += score;
        }
    }

    for(int i = 0; i < indexm; i ++){
        schs[i].TWS = schs[i].scoreT * 1.5 + schs[i].scoreA + schs[i].scoreB / 1.5; //ScoreB/1.5 + ScoreA + ScoreT*1.5
    }

    qsort(schs, indexm, sizeof(schinfo), compar);

    printf("%d\n", indexm);
    int rank = 0;
    str_int_map::iterator iter;
    for(int i = 0; i < indexm; i ++){
        if(i == 0 || schs[i].TWS < schs[i - 1].TWS){ //new rank
            rank = i + 1;
        }
        
        printf("%d %s %d %d\n", rank, schName[schs[i].idx], schs[i].TWS, schs[i].ns);
    }

    return 0;
    
}

C 25分 30分鐘

出考場的時候忘掉了這道題。過了一天才想起來沥割。

其實還是要動動腦子的券膀。剛看到這道題說 subset 和 clique 懵了一下，隱約記得《算法導(dǎo)論》上說過這個問題驯遇，好像是 NP 什么的芹彬，也沒寫過算法。結(jié)果一看題叉庐，只是讓判斷舒帮，沒有讓求。給一張圖和幾次查詢陡叠，要求對于每次查詢玩郊，給出這幾個 vertice 組成的 subset 是否是個 clique，是否是個 maximal clique枉阵。

A clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. A maximal clique is a clique that cannot be extended by including one more adjacent vertex.

圖建好很簡單译红，然后就是對于每次查詢的子集，判斷是否兩兩連通兴溜，再判斷是否有某個子集外的節(jié)點與子集中的每一個頂點連通侦厚，就知道是否是最大的clique 了。

# include <cstdio>

bool graph[210][210];

int nv, ne;

int m;
int nset, set[210];
bool markver[210]; // if in set

int ans;

void printans(int answer){
    if(answer == 0){ //not max
        printf("Not Maximal\n");
    }else if(answer == 1){
        printf("Yes\n");
    }else{
        printf("Not a Clique\n");
    }
}

int main(){
    scanf("%d %d", &nv, &ne);
    int a, b;
    for(int i = 0; i < ne; i ++){
        scanf("%d %d", &a, &b);
        graph[a][b] = graph[b][a] = 1;
    }

    scanf("%d", &m);
    for(int i = 0; i < m; i ++){ // m query
        for(int j = 1; j <= nv; j ++){
            markver[j] = false;
        }
        scanf("%d", &nset);
        for(int j = 0; j < nset; j ++){
            scanf("%d", set + j);
            markver[set[j]] = true;
        }

        if(nset == 1){ //only one vertice in this subset
            bool alone = true;
            for(int j = 1; j <= nv; j ++){
                if(graph[set[0]][j]) {alone = false; break;}
            }
            if(alone) ans = 1; else ans = 0;
        }else{ // 2 or more vertices
            bool isclique = true;
            for(int j = 0; isclique && j < nset; j ++){ //every pair of vertices
                for(int k = j + 1; k < nset; k ++){
                    if(! graph[set[j]][set[k]]){
                        isclique = false;
                        break;
                    }
                }
            }
            if(! isclique){
                ans = -1;
            }else{ // is a clique, check if is max
                bool ismax = true, alladj = true;
                for(int k = 1; ismax && k <= nv; k ++){
                    if(!markver[k]){ // k is now not in this set
                        alladj = true;
                        for(int kk = 0; kk < nset; kk ++){
                            if(!graph[k][set[kk]]){
                                alladj = false;
                                break;
                            }
                        }
                        if(alladj){ //k is adj with every set[kk]
                            ismax = false;
                        }
                    }
                }
                if(! ismax) ans = 0; else ans = 1;
            }
        }
        printans(ans);
    }

    return 0;
}

D 二叉樹 綜合

開始寫這道題的時候還有 80 分鐘左右吧拙徽，時間充足刨沦，我仍然很緊張，畢竟前面才 70 分膘怕，萬一寫不出來就還是挺難看的想诅。

這道題先給定一個前序遍歷序列。我看過這樣的題（雖然沒寫過），通過前序遍歷序列来破，根據(jù)左孩子小右孩子大篮灼，能直接分出來根節(jié)點的左右子樹，然后就是遞歸下去了徘禁。這次遞歸函數(shù)寫得比較好看诅诱，一遍就能跑對了。函數(shù)簽名大概是void build(node* pos, char lr, int lo, int hi)晌坤，是把preorder[lo, hi)這一部分的子樹放到 pos 的左孩子或者右孩子逢艘，用一個字符指示旦袋。函數(shù)里安上根節(jié)點（preorder[lo]）骤菠，找到其左右字樹的分界線，有子樹的話就遞歸地掛那一部分疤孕。一棵樹完成商乎。

后面給了好多組查詢，給兩個 key a, b祭阀，查找 a 和 b 的最低公共祖先節(jié)點鹉戚。當(dāng)然，還要分 a 或者 b 不在這棵樹里的情況专控，另外輸出（這里寫了個 node *search(int key)）抹凳。如果兩個 key 一個是另一個的祖先，也要識別出來伦腐。我本來想著把兩個節(jié)點各自往上走赢底，祖先存起來，然后兩組祖先對比著查找柏蘑，后來覺得太蠢了幸冻，萬一樹不平衡，祖先很長咳焚，查死你不償命洽损。

靈光一閃，想到之前寫樹的那篇文章里有學(xué)過 [dtime, ftime] 如果有包含關(guān)系革半，就存在祖先關(guān)系碑定。于是給結(jié)構(gòu)體增加了 dtime 和 ftime 兩個字段，先做了一遍 dfs又官。之后就特別爽了不傅，先看兩個點的[dtime, ftime]數(shù)組是否包含就知道是否有祖先關(guān)系了。沒有的話赏胚，順著 a 往上找各個祖先访娶，直到該祖先的[dtime, ftime]也包含了 b 的[dtime, ftime]。線性的復(fù)雜度哦觉阅！

這時還有將近半個小時考試結(jié)束崖疤，我有一個 case 沒過秘车，99 分，排第 23 名（從名單的頁數(shù)來看是全國的名次）劫哼。自己試了幾個 case叮趴，發(fā)現(xiàn)如果這兩個節(jié)點一樣，我給錯判斷了权烧，應(yīng)該認(rèn)為 a 是 a 的祖先眯亦。加了幾處等號，過了般码。走人啊嗨 ~~~

這道題的代碼不丑妻率！遞歸我寫的很認(rèn)真的！

# include <cstdio>

struct node{
    int data;
    node *p, *lc, *rc;
    int dtime, ftime; //discovered and finished time
};

int pre[100100];
node *root;
int m, n; //n = nkey, m = mquery

void insertAsRoot(int key){
    root = new node;
    root->lc = root->rc = root->p = NULL;
    root->data = key;
}

node *insertAslc(int key, node *pos){
    pos->lc = new node;
    pos->lc->lc = pos->lc->rc = NULL;
    pos->lc->p = pos;
    pos->lc->data = key;
    return pos->lc;
}

node *insertAsrc(int key, node *pos){
    pos->rc = new node;
    pos->rc->lc = pos->rc->rc = NULL;
    pos->rc->p = pos;
    pos->rc->data = key;
    return pos->rc;
}

void build(node* pos, char lr, int lo, int hi){
    node *x;
    if(lr == 'l'){
        x = insertAslc(pre[lo], pos);
    }else{
        x = insertAsrc(pre[lo], pos);
    }
    if(hi - lo == 1){
        return;
    }
    int part = lo + 1;
    for(; part < hi; part ++){
        if(pre[part] > pre[lo]){
            break;
        }
    }
    if(part < hi){ //have right tree
        build(x, 'r', part, hi);
    }
    if(part > lo + 1){ //have left tree
        build(x, 'l', lo + 1, part);
    }
}

node *search(int key, node *pos){
    if(pos == NULL || pos->data == key){
        return pos;
    }
    if(key < pos->data){
        return search(key, pos->lc);
    }else{
        return search(key, pos->rc);
    }
}

void dfs(node *pos, int &clk){
    if(pos == NULL) return;
    pos->dtime = clk ++;
    dfs(pos->lc, clk);
    dfs(pos->rc, clk);
    pos->ftime = clk ++;
}

int main(){
    scanf("%d %d", &m, &n);
    for(int i = 0; i < n; i ++){
        scanf("%d", pre + i);
    }

    insertAsRoot(pre[0]);
    int part =1;
    for(; part < n; part ++){
        if(pre[part] > pre[0]){
            break;
        }
    }
    if(part < n){ //have right tree
        build(root, 'r', part, n);
    }
    if(part > 1){ //have left tree
        build(root, 'l', 1, part);
    }

    int clk = 0;
    dfs(root, clk);

    int a, b;
    node *afound, *bfound;
    for(int i = 0; i < m; i ++){ // m queries
        scanf("%d %d", &a, &b);
        afound = search(a, root);
        bfound = search(b, root);
        if(!afound && !bfound){
            printf("ERROR: %d and %d are not found.\n", a, b);
        }else if(!afound){
            printf("ERROR: %d is not found.\n", a);
        }else if(!bfound){
            printf("ERROR: %d is not found.\n", b);
        }else{ //look for their ancestors
            if(afound->dtime <= bfound->dtime && bfound->ftime <= afound->ftime){ // a is ance of b
                printf("%d is an ancestor of %d.\n", a, b);
            }else if(bfound->dtime <= afound->dtime && afound->ftime <= bfound->ftime){ // b is ance of a
                printf("%d is an ancestor of %d.\n", b, a);
            }else{
                node *ance = afound->p;
                while(ance){
                    if(ance->dtime < bfound->dtime && ance->ftime > bfound->ftime){ //[dtime, ftime] being included
                        printf("LCA of %d and %d is %d.\n", a, b, ance->data);
                        break;
                    }
                    ance = ance ->p;
                }
            }
        }
    }


    return 0;
}