寒假刷题记录，第三天

PTA甲级

1009 Product of Polynomials

多项式乘法

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>

using namespace std;

const int N = 1010;
int n;
unordered_map<int , double>a , res;

int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++)
    {
        int idx;
        double x;
        cin >> idx >> x;
        a[idx] = x;
    }

    cin >> n;
    for(int i = 0;i < n;i ++)
    {
        int idx;
        double x;
        cin >> idx >> x;
        for(auto j : a)
            res[j.first + idx] += x * j.second;
    }
    vector<pair<int , double>>v;
    for(auto i : res)
        if(i.second) v.push_back({i.first , i.second});
    sort(v.begin() , v.end());
    reverse(v.begin() , v.end());
    cout << v.size();
    for(auto i : v)
        printf(" %d %.1lf" , i.first , i.second);
    return 0;
}

1012 The Best Rank

排序

#include <cstdio>
#include <algorithm>
using namespace std;
struct node {
    int id, best;
    int score[4], rank[4];
}stu[2005];
int exist[1000000], flag = -1;
bool cmp1(node a, node b) {return a.score[flag] > b.score[flag];}

int main() 
{
    int n, m, id;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) 
    {
        scanf("%d %d %d %d", &stu[i].id, &stu[i].score[1], &stu[i].score[2], &stu[i].score[3]);
        stu[i].score[0] = (stu[i].score[1] + stu[i].score[2] + stu[i].score[3]) / 3.0 + 0.5;
    }
    
    for(flag = 0; flag <= 3; flag ++) 
    {
        sort(stu, stu + n, cmp1);
        stu[0].rank[flag] = 1;
        for(int i = 1; i < n; i ++) 
        {
            stu[i].rank[flag] = i + 1;
            if(stu[i].score[flag] == stu[i-1].score[flag])
                stu[i].rank[flag] = stu[i-1].rank[flag];
        }
    }
    
    for(int i = 0; i < n; i++) 
    {
        exist[stu[i].id] = i + 1;
        stu[i].best = 0;
        int minn = stu[i].rank[0];
        for(int j = 1; j <= 3; j ++) 
        {
            if(stu[i].rank[j] < minn) 
            {
                minn = stu[i].rank[j];
                stu[i].best = j;
            }
        }
    }
    char c[5] = {'A', 'C', 'M', 'E'};
    for(int i = 0; i < m; i++) 
    {
        scanf("%d", &id);
        int temp = exist[id];
        if(temp) 
        {
            int best = stu[temp - 1].best;
            printf("%d %c\n", stu[temp - 1].rank[best], c[best]);
        } 
        else printf("N/A\n");
    }
    return 0;
}

1013 Battle Over Cities

经典并查集

#include<iostream>

using namespace std;

const int N = 10100 , M = 1e6 + 10;
int n , m , k;
int p[N];
struct node
{
    int a , b;
}nodes[M];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d %d %d" , &n , &m , &k);
    for(int i = 0;i < m;i ++) scanf("%d %d" ,&nodes[i].a ,&nodes[i].b);

    while(k --)
    {
        int x;
        scanf("%d" ,&x);
        int res = n - 1;
        for(int i = 1;i <= n;i ++) p[i] = i;
        
        for(int i = 0;i < m;i ++)
        {
            int a = nodes[i].a , b = nodes[i].b;
            if(a != x && b != x)
            {
                int pa = find(a) , pb = find(b);
                if(pa != pb) p[pa] = pb , res --;
            }
        }
        printf("%d\n" , res - 1);
    }
    return 0;
}