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