2018-03-18 PAT 春季考試

今天下午 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;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末板祝,一起剝皮案震驚了整個濱河市宫静,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌券时,老刑警劉巖孤里,帶你破解...
    沈念sama閱讀 223,126評論 6 520
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異橘洞,居然都是意外死亡捌袜,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,421評論 3 400
  • 文/潘曉璐 我一進(jìn)店門炸枣,熙熙樓的掌柜王于貴愁眉苦臉地迎上來虏等,“玉大人,你說我怎么就攤上這事抛虏〔┢洌” “怎么了?”我有些...
    開封第一講書人閱讀 169,941評論 0 366
  • 文/不壞的土叔 我叫張陵迂猴,是天一觀的道長慕淡。 經(jīng)常有香客問我,道長沸毁,這世上最難降的妖魔是什么峰髓? 我笑而不...
    開封第一講書人閱讀 60,294評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮息尺,結(jié)果婚禮上携兵,老公的妹妹穿的比我還像新娘。我一直安慰自己搂誉,他們只是感情好徐紧,可當(dāng)我...
    茶點故事閱讀 69,295評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著,像睡著了一般并级。 火紅的嫁衣襯著肌膚如雪拂檩。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,874評論 1 314
  • 那天嘲碧,我揣著相機(jī)與錄音稻励,去河邊找鬼。 笑死愈涩,一個胖子當(dāng)著我的面吹牛望抽,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播履婉,決...
    沈念sama閱讀 41,285評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼煤篙,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了谐鼎?” 一聲冷哼從身側(cè)響起舰蟆,我...
    開封第一講書人閱讀 40,249評論 0 277
  • 序言:老撾萬榮一對情侶失蹤趣惠,失蹤者是張志新(化名)和其女友劉穎狸棍,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體味悄,經(jīng)...
    沈念sama閱讀 46,760評論 1 321
  • 正文 獨居荒郊野嶺守林人離奇死亡草戈,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,840評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了侍瑟。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片唐片。...
    茶點故事閱讀 40,973評論 1 354
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖涨颜,靈堂內(nèi)的尸體忽然破棺而出费韭,到底是詐尸還是另有隱情,我是刑警寧澤庭瑰,帶...
    沈念sama閱讀 36,631評論 5 351
  • 正文 年R本政府宣布星持,位于F島的核電站,受9級特大地震影響弹灭,放射性物質(zhì)發(fā)生泄漏督暂。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,315評論 3 336
  • 文/蒙蒙 一穷吮、第九天 我趴在偏房一處隱蔽的房頂上張望逻翁。 院中可真熱鬧,春花似錦捡鱼、人聲如沸八回。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,797評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽缠诅。三九已至伟墙,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間滴铅,已是汗流浹背戳葵。 一陣腳步聲響...
    開封第一講書人閱讀 33,926評論 1 275
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留汉匙,地道東北人拱烁。 一個月前我還...
    沈念sama閱讀 49,431評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像噩翠,于是被迫代替她去往敵國和親戏自。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,982評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 樹的概述 樹是一種非常常用的數(shù)據(jù)結(jié)構(gòu)伤锚,樹與前面介紹的線性表擅笔,棧,隊列等線性結(jié)構(gòu)不同屯援,樹是一種非線性結(jié)構(gòu) 1.樹的定...
    Jack921閱讀 4,462評論 1 31
  • 1.HashMap是一個數(shù)組+鏈表/紅黑樹的結(jié)構(gòu)猛们,數(shù)組的下標(biāo)在HashMap中稱為Bucket值,每個數(shù)組項對應(yīng)的...
    誰在烽煙彼岸閱讀 1,028評論 2 2
  • 1狞洋,從本篇文章/音頻/視頻中我學(xué)到的最重要的概念 How the writer keeps the traditi...
    沐汐蓓閱讀 296評論 3 0
  • PhantomJS is a headless WebKit scriptable with a JavaScri...
    專職跑龍?zhí)?/span>閱讀 567評論 1 2
  • ——舍棄弯淘,包容才是愛的真諦 愛情不止是甜蜜的相戀時光,更是當(dāng)時光老去吉懊,翻開每一封信件都能...
    我的飄飄天下閱讀 1,035評論 3 1