天梯赛L2题解（009-012）

L2-009 抢红包

模拟即可，注意排序还要根据抢红包的个数

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

void ylh_() {
    int n;
    cin >> n;
    vector<int> ans(n + 1), cnt(n + 1), id(n + 1);
    for (int i = 1; i <= n; ++i) {
        int m;
        cin >> m;
        id[i] = i;
        for (int j = 1; j <= m; ++j) {
            int idx, g;
            cin >> idx >> g;
            ans[idx] += g;
            ++cnt[idx];
            ans[i] -= g;
        }
    }
    sort(id.begin() + 1, id.end(), [&](int x, int y) {
        if (ans[x] == ans[y]) {
            if (cnt[x] == cnt[y]) {
                return x < y;
            } else {
                return cnt[x] > cnt[y];
            }
        }
        return ans[x] > ans[y];
    });
    for (int i = 1; i <= n; ++i) {
        double res = ans[id[i]] / 100.00;
        cout << id[i] << ' ' << fixed << setprecision(2) << res << '\n';
    }
}

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

L2-010 排座位

并查集

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

void ylh_() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; ++ i) {
        p[i] = i;
    }
    auto find = [&](auto &&find, int u) -> int{
        return u == p[u] ? u : p[u] = find(find, p[u]);
    };
    auto d = [&](int u, int v) -> void{
        u = find(find, u);
        v = find(find, v);
        if (u == v) return ;
        p[u] = v;
        return ;
    };
    vector<vector<int>> e(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; ++ i) {
        int u, v, w;
        cin >> u >> v >> w;
        if (w == 1) {
            d(u, v);
        } else {
            e[u][v] = e[v][u] = 1;
        }
    }
    for (int i = 1; i <= k; ++ i) {
        int u, v;
        cin >> u >> v;
        if (e[u][v]) {
            if (find(find, u) == find(find, v)) {
                cout << "OK but...\n";
            } else {
                cout << "No way\n";
            }
        } else {
            if (find(find, u) == find(find, v)) {
                cout << "No problem\n";
            } else {
                cout << "OK\n";
            }
        }
    }
}

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

L2-011 玩转二叉树

你可以递归的真正去翻转一下，但是实际上只需要层序遍历的时候先右后左就行了

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

void ylh_() {
    int n;
    cin >> n;
    vector<int> in(n), pre(n);
    for (auto& i : in)
        cin >> i;
    for (auto& i : pre)
        cin >> i;
    vector<int> ls(n, -1), rs(n, -1), val(n);
    int cnt = 0;
    auto dfs = [&](auto&& dfs, int l1, int r1, int l2, int r2) -> int {
        if (l1 > r1)
            return -1;
        int u = cnt++;
        val[u] = pre[l2];

        int t = l1;
        while (t <= r1 && in[t] != val[u])
            t++;
        int left_len = t - l1;

        ls[u] = dfs(dfs, l1, t - 1, l2 + 1, l2 + left_len);
        rs[u] = dfs(dfs, t + 1, r1, l2 + left_len + 1, r2);

        return u;
    };
    int rt = dfs(dfs, 0, n - 1, 0, n - 1);
    queue<int> q;
    q.push(rt);
    vector<int> ans;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans.push_back(val[u]);
        if (rs[u] != -1)
            q.push(rs[u]);
        if (ls[u] != -1)
            q.push(ls[u]);
    }
    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_();
    }
}

L2-012 关于堆的判断

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

void ylh_() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<int> pq(n + 1);
    map<int, int> pos;
    int cnt = 1;
    auto insert = [&](int x) {
        int u = cnt++;
        pq[u] = x;
        pos[x] = u;
        while (u > 1 && pq[u / 2] > pq[u]) {
            swap(pq[u / 2], pq[u]);
            pos[pq[u / 2]] = u / 2;
            pos[pq[u]] = u;
            u /= 2;
        }
    };
    for (int i = 1; i <= n; ++i) insert(a[i]);
    while (q--) {//根据第二个单词排除操作二，根据第四个单词就可以判断是哪个操作了
        int x;
        string op;
        cin >> x >> op;
        if (op == "and") {
            int y;
            cin >> y;
            int px = pos[x], py = pos[y];
            bool sibling = (px / 2 == py / 2) && abs(px - py) == 1;
            cout << (sibling ? 'T' : 'F') << '\n';
            string dummy;
            cin >> dummy >> dummy;
        } else {
            string word;
            cin >> word;
            cin >> word;
            if (word == "root") {
                cout << (pos[x] == 1 ? 'T' : 'F') << '\n';
            } else if (word == "parent") {
                cin >> word;
                int y;
                cin >> y;
                bool parent = (pos[y] / 2 == pos[x]);
                cout << (parent ? 'T' : 'F') << '\n';
            } else {
                cin >> word;
                int y;
                cin >> y;
                bool child = (pos[x] / 2 == pos[y]);
                cout << (child ? 'T' : 'F') << '\n';
            }
        }
    }
}


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