寒假刷题第五天

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; // 注意用string
    int 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])