2021 ICPC 网络赛第一场 2021 ICPC Asia Regionals Online Contest (I)

今天还是打得比较开心的

A

图片说明

我们采用了二分+线段树，先在[i%k,k-1]里找最左的符合题意的点（完成时间小于当前时间），如果没找到，再在[0,i%k-1]里找，还没找到就忽略此任务

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
ll tree[N << 2];
int n;
#define ls (p << 1)
#define rs (p << 1 | 1)
#define lson ls, l, mid
#define rson rs, mid + 1, r
void update(int x, ll num, int p = 1, int l = 1, int r = n) {  // a[x] = num
    if (l == r) {
        if (l == x) tree[p] = num;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
        update(x, num, lson);
    else
        update(x, num, rson);
    tree[p] = min(tree[ls], tree[rs]);
}
ll query(int x, int y, int p = 1, int l = 1, int r = n) {  // [x,y]'s min val
    if (x <= l && r <= y) return tree[p];
    int mid = (l + r) / 2;
    if (y <= mid) return query(x, y, lson);
    if (x > mid) return query(x, y, rson);
    return min(query(x, mid, lson), query(mid + 1, y, rson));
}
int cnt[N];
void chk(int id, ll now, ll len) {
    int L = id + 1, R = id;
    int l = L, r = n;  // fit segment tree
    int mid;
    int ans = -1;
    while (l <= r) {
        mid = l + r >> 1;
        if (query(L, mid) <= now) {
            ans = mid, r = mid - 1;
        } else
            l = mid + 1;
    }
    if (ans == -1) {
        l = 1, r = R;
        while (l <= r) {  // 找最左的右边界
            mid = l + r >> 1;
            if (query(1, mid) <= now) {
                ans = mid, r = mid - 1;
            } else
                l = mid + 1;
        }
    }
    if (ans != -1) {
        cnt[ans - 1] += 1;
        update(ans, now + len);
    }
}
signed main() {
    int m;
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    ll arriveTime, processTime;
    for (int i = 0; i < m; ++i) {
        cin >> arriveTime >> processTime;
        chk(i % n, arriveTime, processTime);
    }
    int maxVal = 0, lastid;
    for (int i = 0; i < n; ++i) maxVal = max(maxVal, cnt[i]);
    vector<int> res;
    for (int i = 0; i < n; ++i)
        if (cnt[i] == maxVal) res.emplace_back(i);
    for (int i = 0; i < res.size(); ++i) {
        cout << res[i];
        if (i != res.size() - 1) cout << ' ';
    }
    return 0;
}

B

图片说明

最后改好了没有交上，就用凸包搞一下然后逆着输出即可

// debug ing

D

图片说明

题意：有一个乱七八糟的图，要你删到最小生成树，问删掉的总边权和。 $l,r,w$ 表示从 $l$ 到 $r$ 节点生成一个 $w$ 的完全图。

思路：用set维护区间左端点，即可模拟线段覆盖。如果最后覆盖成了一个连通块即可联通。

#include <bits/stdc++.h>
typedef long long ll;
#define int ll
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
const int N = 1e5 + 7;
struct nod {
    int l, r, w;
    bool operator<(const nod o) const { return w < o.w; }
} t;
inline ll sum(ll l, ll r) {
    ll n = r - l + 1;
    return (n - 1) * n / 2;
}
void solve() {
    int n, m;
    cin >> n >> m;
    vector<nod> edg;
    rep(i, 1, m) {
        cin >> t.l >> t.r >> t.w;
        edg.emplace_back(t);
    }
    int ans = 0;
    sort(edg.begin(), edg.end());
    set<int> s;
    rep(i, 1, n) s.insert(i);
    rep(i, 0, m - 1) {
        vector<set<ll>::iterator> vi;
        int cnt = 0, st = edg[i].l, ed = edg[i].r;
        auto l = s.upper_bound(st);
        auto r = s.upper_bound(ed);

        for (auto it = l; it != r; ++it) {
            auto now = it;
            vi.push_back(it);
            cnt++;
        }
        for (auto ii : vi) s.erase(ii);

        ans += (sum(st, ed) - cnt) * edg[i].w;
    }
    if (s.size() == 1)
        cout << ans;
    else
        cout << "Gotta prepare a lesson";
}
signed main() {
    int T;
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> T;
    rep(i, 1, T) {
        cout << "Case #" << i << ": ";
        solve();
        if (i != T) cout << '\n';
    }
    return 0;
}