寒假刷题第五天

PTA甲级

1022 Digital Library

大模拟

#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<set>using namespace std;unordered_map<string , set<int>>ti , au , key , pub , year;
unordered_set<string>se;void print(set<int>&v)
{for(auto i : v)printf("%07d\n" , i); // 注意是7位数字
}vector<string> split(string s)
{vector<string>v;int last = 0;for(int i = 0;i < s.size();i ++)if(s[i] == ' ') v.push_back(s.substr(last , i - last)) , last = i + 1;v.push_back(s.substr(last));return v;
}int main()
{int t;cin >> t;while(t --){int id;cin >> id;getchar();for(int i = 0;i < 5;i ++){string s;getline(cin , s);se.insert(s);if(i == 0) ti[s].insert(id);else if(i == 1) au[s].insert(id);else if(i == 2) {vector<string>v = split(s);for(auto j : v)key[j].insert(id) , se.insert(j);}else if(i == 3) pub[s].insert(id);else year[s].insert(id);}}int k;cin >> k;getchar();while(k --){string s;getline(cin , s);cout << s << endl;int k = s.find(':');string t = s.substr(k + 2);if(!se.count(t)) puts("Not Found");else{if(ti.count(t)) print(ti[t]);else if(au.count(t)) print(au[t]);else if(key.count(t)) print(key[t]);else if(pub.count(t)) print(pub[t]);else if(year.count(t)) print(year[t]);}}return 0;
}

1025 PAT Ranking

排序

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>using namespace std;typedef long long ll;
typedef pair<string , int> PII;
const int N = 1e5 + 10;
struct node
{string id; // 注意用stringint score;int loc;int finalrank;int locrank;
};
vector<node>v(N);
int n;
unordered_map<string , int>mp;bool cmp1(PII a , PII b)
{if(a.second != b.second) return a.second > b.second;return a.first < b.first;
}bool cmp2(node a , node b)
{if(a.score != b.score) return a.score > b.score;return a.id < b.id;
}int main()
{cin >> n;int cnt = 0;for(int i = 1;i <= n;i ++){int m;cin >> m;vector<PII>t;for(int j = 0;j < m;j ++){cin >> v[cnt].id >> v[cnt].score;v[cnt].loc = i;mp[v[cnt].id] = cnt;t.push_back({v[cnt].id , v[cnt].score});cnt ++;}sort(t.begin() , t.end() , cmp1);for(int j = 0;j < t.size();j ++)if(j == 0) v[mp[t[j].first]].locrank = j + 1;else{if(t[j].second == t[j - 1].second) v[mp[t[j].first]].locrank = v[mp[t[j - 1].first]].locrank;else v[mp[t[j].first]].locrank = j + 1;}}cout << cnt << endl;sort(v.begin() , v.begin() + cnt , cmp2);for(int i = 0;i < cnt;i ++){if(i == 0) cout << v[i].id << " " << i + 1 << " " << v[i].loc << " " << v[i].locrank << endl , v[i].finalrank = 1;else{if(v[i - 1].score == v[i].score) cout << v[i].id << " " << v[i - 1].finalrank << " " << v[i].loc << " " << v[i].locrank << endl , v[i].finalrank = v[i - 1].finalrank;else cout << v[i].id << " " << i + 1 << " " << v[i].loc << " " << v[i].locrank << endl , v[i].finalrank = i + 1;}}return 0;
}

1029 Median

找中位数，直接用python写更快

A = list(map(int , input().split()))
B = list(map(int , input().split()))
A.pop(0);B.pop(0);
A = A + B
A.sort()
print(A[len(A) // 2 if len(A) % 2 else (len(A) - 1) // 2])