天梯赛L2题解（017-020）

L2-017 人以群分

偶数对半分最好，奇数的话外向多一个差就更大

#include <bits/stdc++.h>
using namespace std;
#define int long long
using PII = pair<int, int>;

void ylh_() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    sort(a.begin() + 1, a.end());
    vector<int> pre(n + 1);
    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1] + a[i];
    }
    int diff = pre[n] - 2 * pre[n / 2];
    cout << "Outgoing #: " << n / 2 + (n % 2 == 1) << '\n';
    cout << "Introverted #: " << n / 2 << '\n';
    cout << "Diff = " << diff;
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        ylh_();
    }
}

L2-018 多项式A除以B

比赛的时候拿不到满分就放弃吧，我已调试到疾苦
想拿满分还是不要看我的这题的一坨解QWQ

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

const double eps = 1e-6;

void ylh_() {
    int n1;
    cin >> n1;
    vector<int> a1;
    vector<double> a2;
    for (int i = 1; i <= n1; ++i) {
        int x;
        double y;
        cin >> x >> y;
        a1.push_back(x);
        a2.push_back(y);
    }
    int n2;
    cin >> n2;
    vector<int> b1;
    vector<double> b2;
    for (int i = 1; i <= n2; ++i) {
        int x;
        double y;
        cin >> x >> y;
        b1.push_back(x);
        b2.push_back(y);
    }
    if (n1 == 0) {
        cout << "0 0 0.0\n 0 0 0.0";
        return;
    }
    
    // 被除式数组，下标为指数
    vector<double> a3(10010, 0.0);
    int max_a = 0;
    for (int i = 0; i < a1.size(); ++i) {
        a3[a1[i]] = a2[i];
        if (a1[i] > max_a) max_a = a1[i];
    }
    
    // 除式数组
    vector<double> b3(10010, 0.0);
    int max_b = 0;
    for (int i = 0; i < b1.size(); ++i) {
        b3[b1[i]] = b2[i];
        if (b1[i] > max_b) max_b = b1[i];
    }
    
    // 商数组
    vector<double> c3(10010, 0.0);
    int max_c = max_a - max_b;
    
    while (max_a >= max_b) {
        if (abs(a3[max_a]) < eps) {
            max_a--;
            continue;
        }
        double q = a3[max_a] / b3[max_b];
        c3[max_a - max_b] = q;
        
        // 更新被除式
        for (int i = max_a, j = max_b; i >= 0 && j >= 0; i--, j--) {
            a3[i] -= b3[j] * q;
        }
        
        while (max_a >= 0 && abs(a3[max_a]) < eps) {
            max_a--;
        }
    }
    
    auto print = [&](vector<double>& arr, int max_exp) {
        int cnt = 0;
        for (int i = 0; i <= max_exp; ++i) {
            if (abs(arr[i]) + 0.05 >= 0.1) cnt++;
        }
        cout << cnt;
        if (cnt == 0) {
            cout << " 0 0.0";
        } else {
            for (int i = max_exp; i >= 0; --i) {
                if (abs(arr[i]) + 0.05 >= 0.1) {
                    cout << ' ' << i << fixed << setprecision(1) << ' ' << arr[i];
                }
            }
        }
    };
    
    print(c3, max_c);
    cout << '\n';

    print(a3, max_a);
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        ylh_();
    }
    return 0;
}

L2-019 悄悄关注

#include <bits/stdc++.h>
using namespace std;
#define int long long
using PSI = pair<string, int>;

void ylh_() {
    int n;
    cin >> n;
    set<string> st;
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        st.insert(s);
    }
    int m;
    cin >> m;
    vector<PSI> a(m + 1);
    int sum = 0;
    for (int i = 1; i <= m; ++i) {
        cin >> a[i].first >> a[i].second;
        sum += a[i].second;
    }
    sort(a.begin() + 1, a.end(), [&](PSI x, PSI y) {
        return x.first < y.first;
    });
    vector<string> ans;
    for (int i = 1; i <= m; ++i) {
        if (a[i].second * m > sum) {
            if (!st.count(a[i].first)) {
                ans.push_back(a[i].first);
            }
        }
    }
    for (int i = 0; i < ans.size(); ++i) {
        cout << ans[i];
        if (i != ans.size() - 1) {
            cout << '\n';
        } else {
            return;
        }
    }
    cout << "Bing Mei You";
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        ylh_();
    }
}

L2-020 功夫传人

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

void ylh_() {
    int n;
    double z, r;
    cin >> n >> z >> r;
    r /= 100;
    vector<vector<int>> g(n);
    vector<int> ddz(n + 1); // 得道者的倍数
    for (int i = 0; i < n; ++i) {
        int m;
        cin >> m;
        if (m == 0) {
            int k;
            cin >> k;
            ddz[i] = k;
        }
        for (int j = 1; j <= m; ++j) {
            int k;
            cin >> k;
            g[i].push_back(k);
        }
    }
    double ans = 0;
    auto dfs = [&](auto&& dfs, double cur, int u) {
        // cout << u << ' ' << cur << endl;
        if (ddz[u] > 0) {
            ans += cur * ddz[u];
            return;
        }
        double ncur = cur * (1.0 - r);
        for (auto v : g[u]) {
            dfs(dfs, ncur, v);
        }
    };
    dfs(dfs, z, 0);
    int ans_int = ans;
    cout << ans_int;
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        ylh_();
    }
}