天梯赛L2题解（013-016）

L2-013 红色警报

呃，怎么说呢，题目讲的可能不太清楚，大概就是说只要连通块数量增加，那么就要发出红色警报，所以我们每去掉一个点的时候重新再搜索一下不包含这个点的图的连通块数量就行，我这里用的是bfs

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

void ylh_() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> exist(n + 1, 1);
    auto bfs = [&]() -> int {
        vector<int> vis(n + 1);
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (vis[i] || !exist[i])
                continue;
            queue<int> q;
            q.push(i);
            ++cnt;
            while (!q.empty()) {
                auto u = q.front();
                q.pop();
                if (vis[u])
                    continue;
                vis[u] = 1;
                for (auto v : g[u]) {
                    if (!vis[v] && exist[v]) {
                        q.push(v);
                    }
                }
            }
        }
        return cnt;
    };
    int k;
    cin >> k;
    vector<int> res(k + 1);
    res[0] = bfs();
    for (int i = 1; i <= k; ++i) {
        int x;
        cin >> x;
        exist[x] = 0;
        res[i] = bfs();
        if (res[i] > res[i - 1]) {
            cout << "Red Alert: City " << x << " is lost!\n";
        } else {
            cout << "City " << x << " is lost.\n";
        }
        if (res[i] == 0) {
            cout << "Game Over.";
        }
    }
}

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

L2-014 列车调度

用Set维护每一个轨道的尾巴，显然某个值比这个尾巴小的时候才能放进这个轨道，而且最好插入目前最相近的尾巴，如果不能插入，那么就新开一条轨道

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

void ylh_() {
    int n;
    cin >> n;
    set<int> st;
    st.insert(0);
    for(int i = 0; i < n; i++) {
        int t;
        cin >> t;
        auto it = st.upper_bound(t);
        if(it != st.end()) st.erase(it);
        st.insert(t);
    }
    cout << st.size() - 1 << endl;
}

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

L2-015 互评成绩

时间复杂度可以用优先队列压一下，但是不压也能过，无所谓了

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

void ylh_() {
    int n, k, m;
    cin >> n >> k >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        int min_ = x, max_ = x, sum_ = x;
        for (int j = 1; j < k; ++j) {
            cin >> x;
            min_ = min(min_, x);
            max_ = max(max_, x);
            sum_ += x;
        }
        a[i] = sum_ - min_ - max_;
    }
    sort(a.begin() + 1, a.end(), greater<int>());
    for (int i = m; i >= 1; --i) {
        double res = 1.00 * a[i] / (k - 2);
        cout << fixed << setprecision(3) << res;
        if (i != 1) {
            cout << ' ';
        }
    }
}

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

L2-016 愿天下有情人都是失散多年的兄妹

太保守了导致一开始少过几个点，注意即使为人父母也是可以被询问的
这个题具体来说就是我们可以直接往上搜四代，因为只有五代状态数不算多，复杂度可以接受

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

void ylh_() {
    int n;
    cin >> n;
    const int N = 1e5;
    vector<int> dad(N + 1, -1), mom(N + 1, -1), x(N + 1);
    for (int i = 1; i <= n; ++i) {
        int idx, f, m;
        char c;
        cin >> idx >> c >> f >> m;
        x[idx] = ((c == 'M') ? 1 : 2);
        dad[idx] = f;
        mom[idx] = m;
        if (f != -1) x[f] = 1;
        if (m != -1) x[m] = 2;//注意即使身为人父人母也是可以被询问的
    }
    int ok = 1;
    auto f = [&](auto&& f, int x, int y, int cnt) -> void {
        // cout << x << ' ' << y << '\n';
        if (x == -1 || y == -1) return ;
        if (x == y) {
            ok = 0;
            return;
        }
        if (cnt > 4)
            return;
        if (dad[x] != -1 && dad[y] != -1)
            f(f, dad[x], dad[y], cnt + 1);
        if (dad[x] != -1 && mom[y] != -1)
            f(f, dad[x], mom[y], cnt + 1);
        if (mom[x] != -1 && dad[y] != -1)
            f(f, mom[x], dad[y], cnt + 1);
        if (mom[x] != -1 && mom[y] != -1)
            f(f, mom[x], mom[y], cnt + 1);
    };
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        if (x[u] == x[v]) {
            cout << "Never Mind\n";
            continue;
        }
        ok = 1;
        f(f, u, v, 1);
        cout << ((ok) ? "Yes" : "No") << '\n';
    }
}

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