101-2 資訊社小考一參考解答

***************  d492. 10226 - Hardwood species  ***************

//10226 - Hardwood Species (by Snail)

#include <iostream>

#include <iomanip> //setprecision()

#include <string>

#include <map>

using namespace std;

int main () {

    int tc, n;

    string s;

    map<string, int>::iterator it;

    cout << fixed << setprecision(4);           //小數點以下四位

    cin >> tc >> ws;                            //ws 跳過換行

    while (tc--) {

        map<string, int> h;                     //建構新的 h 陣列

        n = 0;

        while (getline (cin, s), s != "")       //輸入到空行為止

            h[s]++, n++;                        //記錄各種樹的量

        for (it=h.begin(); it!=h.end(); it++)

            cout << it->first << ' ' << it->second*100./n << endl;

        if (tc) cout << endl;                   //資料間空一行

    }

}

***************  b207. F. 世界盃  ***************

//F. 世界盃 -- 2008 NPSC 國中組初賽 by Snail

#include <iostream>

#include <string>

#include <algorithm>

#include <map>

using namespace std;

struct team {                                   //c(ountry)--國家

    string c;                                   //p(oints)--積分

    int p, w, l;                                //w(in), l(ost)--得分, 失分

} t[8];                                         //t(eam)[]--隊伍

bool operator< (team a, team b) {

    if (a.p != b.p) return a.p > b.p;

    if (a.w != b.w) return a.w > b.w;

    if (a.l != b.l) return a.l < b.l;

    return a.c < b.c;

}

int main () {

    int n, i, sa, sb;

    string ca, cb;

    cin >> n;

    while (n--) {

        map <string, int> id;                   //國名->編號

        for (i=0; i<8; i++) {

            cin >> t[i].c;

            id[t[i].c] = i;

            t[i].p = t[i].w = t[i].l = 0;

        }

        for (i=0; i<12; i++) {

            cin >> ca >> sa >> sb >> cb;        //c(ountry)a, b--國家

            if (sa == sb)                       //s(core)a,b--得分

                t[id[ca]].p++, t[id[cb]].p++;

            else if (sa > sb)

                t[id[ca]].p += 3;

            else

                t[id[cb]].p += 3;

            t[id[ca]].w += sa;

            t[id[ca]].l += sb;

            t[id[cb]].w += sb;

            t[id[cb]].l += sa;

        }

        sort (t, t+4);

        cout << "A1 " << t[0].c << endl;

        cout << "A2 " << t[1].c << endl;

        sort (t+4, t+8);

        cout << "B1 " << t[4].c << endl;

        cout << "B2 " << t[5].c << endl;

        cout << "BEST3 " << (t[2]<t[6] ? t[2].c : t[6].c) << endl;

    }

}

***************  b198. C. 計票程式  ***************

//C. 計票程式 (2008 NPSC 高中組初賽) by Snail

#include <iostream>

#include <string>

#include <algorithm>

#include <map>

#include <vector>

using namespace std;

bool gt (pair<string, int> a, pair<string, int> b) {    //gt (greater than)--a > b

    if (a.second == b.second) return a.first < b.first; //若票數相同則比選項名稱

    return a.second > b.second;

}

                                                //nvote[s]--s 的得票數

int main () {                                   //valid[c]--c 為有效投票碼

    map <string, int> nvote, valid;

    string s, code;                             //code--投票碼

    while (getline (cin, code), code != "*")

        valid[code] = 1;                        //讀入有效投票碼

    getline (cin, s);

    while (s != "*") {

        cin >> ws;                              //跳過投票碼的前 4 個空白

        getline (cin, code);

        map <string, int> voted;                //voted[s]--s 已經投過了

        while (getline (cin, s), s[0] == ' ')

            if (valid[code] && s.substr(4,2)=="<<"

                            && s.substr(s.size()-2)==">>")

                if (!voted[s]++)                //若該選項未投過

                    nvote[s.substr(4)]++;       //則票數加 1 (跳過選項名稱前的空白)

        valid[code] = 0;                        //投票碼用過作廢

    }

    vector <pair <string, int> > v (nvote.begin(), nvote.end());

    sort (v.begin(), v.end(), gt);              //從 map 複製到 vector 並排序

    for (unsigned i=0; i<v.size(); i++)

        cout << v[i].second << ' ' << v[i].first << endl;

}

***************  a584. 2. 親等關係  ***************

//a584. 2. 親等關係 (by Snail)

#include <iostream>

#include <string>

#include <map>

using namespace std;

int main () {

    map <string, string> f;                     //f(ather)--父節點

    int n, i, ns, nt;

    string s, t, s1[50], t1[50];

    cin >> n >> ws;                             //ws--跳過換行

    while (n--) {

        getline (cin, s);

        t = s.substr(0,3);                      //取得父親名字

        for (i=4; i<(int)s.size(); i+=4)

            f[s.substr(i,3)] = t;               //記錄每個人的父親

    }

    cin >> s >> t;

    for (ns=0; s!=""; s=f[s])                   //向上回溯至根

        s1[ns++] = s;

    for (nt=0; t!=""; t=f[t])

        t1[nt++] = t;

    while (s1[ns-1]==t1[nt-1])                  //扣掉相同的祖先

        ns--, nt--;

    cout << ns + nt << endl;

}