Codeforces Round 857 (Div. 2)【A - E】

D 题有一个细节没处理好 FST 了，E 题没想好树状数组怎么清空，不过思路基本上对了。

最后居然也上了一分……继续努力吧。

比赛链接：https://codeforces.com/contest/1802

A. Likes

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        map<int, int> mp;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            mp[abs(x)] += 1;
        }

        int one = 0, two = 0;
        for (auto [x, y] : mp) {
            (y == 1 ? one : two) += 1;
        }

        for (int i = 1; i <= one + two; i++) {
            cout << i << ' ';
        }
        for (int i = 1; i <= two; i++) {
            cout << one + two - i << ' ';
        }
        cout << "\n";

        for (int i = 1; i <= two; i++) {
            cout << 1 << ' ' << 0 << ' ';
        }
        for (int i = 1; i <= one; i++) {
            cout << i << ' ';
        }
        cout << "\n";
    }

    return 0;
}

B. Settlement of Guinea Pigs

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        int ans = 0, cur = 0, one = 0;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if (x == 1) {
                cur += 1;
                one += 1;
                ans = max(ans, cur);
            } else {
                if (one == 0) {
                    continue;
                }
                if (one & 1) {
                    cur -= (one - ((one - 1) / 2 + 1));
                    one = 1;
                } else {
                    cur -= (one - ((one - 2) / 2 + 2));
                    one = 2;
                }
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

C. The Very Beautiful Blanket

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n, m;
        cin >> n >> m;

        cout << n * m << "\n";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << (1 << (__lg(m) + 1)) * i + j << " \n"[j == m - 1];
            }
        }
    }

    return 0;
}

D. Buying gifts

题解

排序后枚举第一个人所选的最大值。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<pair<int, int>> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i].first >> a[i].second;
        }
        sort(a.begin(), a.end());

        vector<int> dp(n);
        for (int i = n - 1; i >= 0; i--) {
            if (i == n - 1) {
                dp[i] = a[i].second;
            } else {
                dp[i] = max(dp[i + 1], a[i].second);
            }
        }

        int ans = INT_MAX;
        set<int> st;
        for (int i = 0; i < n; i++) {
            int mx = -1;
            if (i + 1 < n) {
                mx = dp[i + 1];
                ans = min(ans, abs(mx - a[i].first));
            }
            auto it = st.lower_bound(a[i].first);
            if (it != st.end() and *it >= mx) {
                ans = min(ans, *it - a[i].first);
            }
            if (it != st.begin() and not st.empty() and *prev(it) >= mx) {
                ans = min(ans, a[i].first - *prev(it));
            }
            st.insert(a[i].second);
        }
        cout << ans << "\n";
    }

    return 0;
}

E. Music Festival

题解

将每个序列处理为严格递增后按右端点从小到大排序，之后对每个序列的右端点进行 dp，用树状数组查询和更新以该右端点结尾的最大长度。

代码

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

struct Fenwick_tree {
    vector<int> bit;

    Fenwick_tree(int n) : bit(n) {}

    void update(int pos, int val) {
        for (int i = pos; i <= (int)bit.size(); i += i & (-i)) {
            bit[i] = max(bit[i], val);
        }
    }

    void clear(int pos) {
        for (int i = pos; i <= (int)bit.size(); i += i & (-i)) {
            bit[i] = 0;
        }
    }

    int query(int l, int r) {
        return query(r) - query(l - 1);
    }

    int query(int pos) {
        int res = 0;
        for (int i = pos; i >= 1; i -= i & (-i)) {
            res = max(res, bit[i]);
        }
        return res;
    }
} F(2e5 + 10); // 也可以每次开 O(n) 的然后把所有值离散化

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<vector<int>> a(n);
        for (int i = 0; i < n; i++) {
            int k;
            cin >> k;
            int pre = -1;
            for (int j = 0; j < k; j++) {
                int x;
                cin >> x;
                if (x > pre) {
                    a[i].push_back(x);
                    pre = x;
                }
            }
        }
        sort(a.begin(), a.end(), [](auto& x, auto& y) {
            return x.back() < y.back();
        });

        for (auto vec : a) {
            int mx = 0;
            for (int i = 0; i < (int)vec.size(); i++) {
                mx = max(mx, (int)vec.size() - i + F.query(vec[i] - 1));
            }
            F.update(vec.back(), mx);
        }

        cout << F.query(2e5 + 1) << "\n";
        for (auto vec : a) {
            F.clear(vec.back());
        }
    }

    return 0;
}