PAT甲级打卡-1001-1004

1001 A+B Format

求a+b，但需要有逗号格式

#include <bits/stdc++.h>
using namespace std;

void print(int x) {
    
    if(x == 0) {
    
        cout << "0" ;
        return;
    }
    string s = "";
    bool flag = 0;
    if(x < 0) {
    
        flag = 1;
        x = -x;
    }
    int cnt =0;
    while(x) {
    
        s =s + (char)('0' + x % 10);
        x /= 10;
        cnt++;
        if(cnt && cnt % 3 ==0) s=  s +',';
    }

    reverse(s.begin(), s.end());
    if(s[0] == ',') s = s.substr(1);
    if(flag) {
    
        cout << "-";
    }
    cout << s;
}

signed main() {
    
    ios::sync_with_stdio(false) , cin.tie(nullptr), cout.tie(nullptr);

    int a, b;
    cin >> a >> b;
    int sum = a + b;
    print(sum);
}

1002 A+B for Polynomials

给两个多项式，求和，按格式输出

#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-7;

map<int, double> mp;

signed main() {
    
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int n;
    while(cin >> n) {
    
        for (int i = 1; i <= n; ++i) {
    
            int k;
            double a;
            cin >> k >> a;
            mp[k] += a;
        }
        cin >> n;
        for (int i = 1; i <= n; ++i) {
    
            int k;
            double a;
            cin >> k >> a;
            mp[k] += a;
        }
        vector<pair<int, double> > ans;
        for (auto[x, y]: mp) {
    
            if(fabs(y) < eps) continue;
            ans.push_back({
    x, y});
        }
        reverse(ans.begin(), ans.end());
        cout << ans.size();
        for (auto tt : ans) {
    
            cout << " " << tt.first << " " << fixed << setprecision(1) << tt.second;
        }
        cout << endl;
    }

    return 0;
}

1003 Emergency

我之前写过一道天梯赛的，一样的题不用输出方案 https://blog.csdn.net/qq_39602052/article/details/123804709
这个之前的博客链接有一组样例可以看看

n点m边无向图，点有点权，问从起点到终点的最短路同时获得最大权值，输出最短路条数和最大权值

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;

const int N = 510;

struct edges {
    
    int to, len;
};
vector<edges> g[N];
int a[N];
int cnt[N];

struct node {
    
    int u, dis, val;

    bool operator<(const node &right) const {
    
        if (this->dis == right.dis) return this->val > right.val;
        return this->dis < right.dis;
    }
};

pair<int, int> ans[N];

void dij(int s) {
    
    priority_queue<node, vector<node> > que;
    que.push({
    s, 0, a[s]});
    ans[s].first= 0, ans[s].second = a[s];

    while (!que.empty()) {
    
        auto tmp = que.top();
        que.pop();
        int u = tmp.u;

        if (tmp.dis > ans[u].first || (tmp.dis == ans[u].first && tmp.val < ans[u].second)) continue;

        for (auto tt : g[u]) {
    
            int to = tt.to;
            int len = tt.len;
            if (ans[u].first + len < ans[to].first) {
    
                ans[to].first = ans[u].first + len;
                ans[to].second = ans[u].second + a[to];
                que.push({
    to, ans[to].first, ans[to].second});
            } else if (ans[u].first + len == ans[to].first && ans[u].second + a[to] > ans[to].second) {
    
                ans[to].second = ans[u].second + a[to];
                que.push({
    to, ans[to].first, ans[to].second});
            }
        }
    }

}

signed main() {
    
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int n, m, s, t;
    cin >> n >> m >> s >> t;

    for (int i = 0; i <= n; ++i) ans[i].first = inf, ans[i].second = 0;

    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0, x, y, len; i < m; ++i) {
    
        cin >> x >> y >> len;
        g[x].push_back({
    y, len});
        g[y].push_back({
    x, len});
    }

    dij(s);

    cnt[s] = 1;
    vector<pair<int,int>> vec;
    for(int i =0;i < n; ++i) {
    
        vec.push_back({
    i, ans[i].first});
    }
    sort(vec.begin(), vec.end(),[&](auto x, auto y){
    return x.second < y.second;});

    for(auto [x, dis] : vec) {
    
        for(auto [to, len] : g[x]) {
    
            if(ans[to].first == ans[x].first+ len) {
    
                cnt[to] += cnt[x];
            }
        }
    }

    cout << cnt[t] << " " << ans[t].second;
}

1004 Counting Leaves

给一棵树，问每层的叶子数

#include<bits/stdc++.h>

using namespace std;

const int N = 110;
vector<int> g[N];

int cnt[N];
int mxdep = 0;

void dfs(int x, int p, int dep) {
    
    if (g[x].empty()) cnt[dep]++;
    mxdep = max(mxdep, dep);
    for (auto to : g[x]) {
    
        if (to == p) continue;
        dfs(to, x, dep + 1);
    }
}

signed main() {
    
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
    
        int x, k;
        cin >> x >> k;
        for (int j = 0; j < k; ++j) {
    
            int y;
            cin >> y;
            g[x].push_back(y);
        }
    }

    dfs(1, -1, 1);

    for (int i = 1; i <= mxdep; ++i) {
    
        cout << cnt[i];
        cout << (i == mxdep ? "" : " ");
    }

}