天梯赛L2题解（001-004）

L2-001 紧急救援

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

void solve() {
    int n, m, st, ed;
    cin >> n >> m >> st >> ed;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<vector<PII>> g(n);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({ v, w });
        g[v].push_back({ u, w });
    }

    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({ 0, st });

    const int INF = 1e18;
    vector<int> dist(n, INF), cnt(n, 0), sum(n, 0), pa(n, -1);
    dist[st] = 0;
    cnt[st] = 1;
    sum[st] = a[st];
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u])
            continue;
        for (auto [v, w] : g[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                cnt[v] = cnt[u];
                sum[v] = sum[u] + a[v];
                pa[v] = u;
                pq.push({ dist[v], v });
            } else if (dist[v] == dist[u] + w) {
                cnt[v] += cnt[u];
                if (sum[v] < sum[u] + a[v]) {
                    sum[v] = sum[u] + a[v];
                    pa[v] = u;
                }
            }
        }
    }
    cout << cnt[ed] << ' ' << sum[ed] << '\n';
    vector<int> ans;
    int cur = ed;
    while (cur != -1) {
        ans.push_back(cur);
        cur = pa[cur];
    }
    for (int i = ans.size() - 1; i >= 0; --i) {
        cout << ans[i] << (i > 0 ? " " : "");
    }
}

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

L2-002 链表去重

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

void ylh_() {
    const int N = 1e5;
    vector<int> pos(N + 1), next(N + 1, -1);
    auto trans = [&](string s) { //变换
        int res = 0;
        for (auto v : s) {
            res *= 10;
            res += (int)(v - '0');
        }
        return res;
    };
    auto ftrans = [&](int x) { //逆变换
        string r = "";
        while (x) {
            r += (char)((x % 10) + '0');
            x /= 10;
        }
        while (r.size() < 5) {
            r += '0';
        }
        reverse(r.begin(), r.end());
        return r;
    };
    string fst;
    int f, n;
    cin >> fst >> n;
    f = trans(fst);
    for (int i = 1, val; i <= n; ++i) {
        string s1, s2;
        cin >> s1 >> val >> s2;
        int j = trans(s1);
        if (s2 == "-1") { 
            next[j] = -1;
            pos[j] = val;
            continue;
        }
        int k = trans(s2);
        pos[j] = val;
        next[j] = k;
    }
    vector<int> vis(N + 1, 0);
    vector<int> ans1;
    vector<int> ans2;
    auto dfs = [&](auto&& dfs, int u) {
        if (vis[abs(pos[u])]) {
            ans2.push_back(u);
        }
        if (!vis[abs(pos[u])]) {
            ans1.push_back(u);
            vis[abs(pos[u])] = 1;
        }
        if (next[u] == -1) {
            return;
        }
        dfs(dfs, next[u]);
    };
    dfs(dfs, f);
    for (int i = 0; i < ans1.size(); ++i) {
        int u = ans1[i];
        if (i != ans1.size() - 1) {
            int v = ans1[i + 1];
            cout << ftrans(u) << ' ' << pos[u] << ' ' << ftrans(v) << '\n';
        } else {
            if (ans2.size()) {
                cout << ftrans(u) << ' ' << pos[u] << ' ' << -1 << '\n';
            } else {
                cout << ftrans(u) << ' ' << pos[u] << ' ' << -1;
            }
        }
    }
    for (int i = 0; i < ans2.size(); ++i) {
        int u = ans2[i];
        if (i != ans2.size() - 1) {
            int v = ans2[i + 1];
            cout << ftrans(u) << ' ' << pos[u] << ' ' << ftrans(v) << '\n';
        } else {
            cout << ftrans(u) << ' ' << pos[u] << ' ' << -1;
        }
    }
}

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

L2-003 月饼

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

//坑点：月饼的两个参数是正数，并非正整数

void ylh_() {
    int n, D;
    cin >> n >> D;
    vector<PII> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].second;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].first;
    }
    sort(a.begin() + 1, a.end(), [&](PII x, PII y) {
        return x.first * y.second > y.first * x.second;
    });
    double ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (D >= a[i].second) { //其实这里的比较是不合法的，最好使用eps，不过这样可以通过
            D -= a[i].second;
            ans += 1.00 * a[i].first;
        } else {
            ans += a[i].first * D / a[i].second;
            cout << fixed << setprecision(2) << ans << '\n';
            return;
        }
    }
    cout << fixed << setprecision(2) << ans << '\n';
}

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

L2-004 这是二叉搜索树吗？

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

void ylh_() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    vector<int> l(n + 1), r(n + 1);
    int mxdep = 1;
    auto add = [&](auto&& add, int u, int p, int dep) -> void {
        mxdep = max(dep + 1, mxdep);
        if (a[p] < a[u]) {
            if (!l[u]) {
                l[u] = p;
            } else {
                add(add, l[u], p, dep + 1);
            }
        } else if (a[p] >= a[u]) {
            if (!r[u]) {
                r[u] = p;
            } else {
                add(add, r[u], p, dep + 1);
            }
        }
    };
    for (int i = 2; i <= n; ++i) {
        add(add, 1, i, 1);
    }
    vector<int> ans, pre;
    pre.push_back(0);
    auto dfs = [&](auto&& dfs, int u, int mode) -> void {
        pre.push_back(a[u]);
        if (mode == 1) {
            if (l[u])
                dfs(dfs, l[u], mode);
            if (r[u])
                dfs(dfs, r[u], mode);
        } else {
            if (r[u])
                dfs(dfs, r[u], mode);
            if (l[u])
                dfs(dfs, l[u], mode);
        }
        ans.push_back(a[u]);
    };
    dfs(dfs, 1, a[2] < a[1]);
    if (pre != a) {
        cout << "NO";
        return;
    }
    cout << "YES\n";
    for (int i = 0; i < ans.size(); ++i) {
        cout << ans[i];
        if (i != ans.size() - 1) {
            cout << ' ';
        }
    }
}

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