【XJTU 2020暑期集训】Day13 - 2019 Multi-University Training Contest 10

A - Minimum Spanning Trees

咕

B - Line Graphs

咕

C - Valentine's Day

咕

D - Play Games with Rounddog

咕

E - Welcome Party

先将所有同学按照 x 升序排序，枚举 x_i 为当前选唱歌的同学的 x 的最大值，则同学 i+1\dots n 必须选脱口秀，此外前 i-1 个同学可以任意选择。设 y_{\max}=\max_{k=i+1}^n y_i，若 y_{\max}\ge x_i，则前 i-1 个同学都选唱歌一定最优；若 y_{\max}\lt x_i，则在 y_1\dots y_{i-1} 中找分别大于等于和小于 x_i 且最接近 x_i 的两个值 \mathrm{mx},\mathrm{mn}，答案即为 |\max(y_{\max},\mathrm{mx})-x_i| 和 |\max(y_{\max},\mathrm{mn})-x_i| 中的最小值。枚举时用set维护，总复杂度 O(n\log n)。

F - Dense Subgraph

咕

G - Closest Pair of Segments

咕

H - Coins

咕

I - Block Breaker

签到题，简单模拟即可。

J - Domino Covering

咕

K - Make Rounddog Happy

咕

Code

A - Minimum Spanning Trees

B - Line Graphs

C - Valentine's Day

D - Play Games with Rounddog

E - Welcome Party

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <set>
#define MAX_N 100005
#define INF 0x3f3f3f3f3f3f3f3fLL
#define fi first
#define se second
#define pii pair<int, int>
#define int long long

using namespace std;

int T, n;
pii p[MAX_N];

int getl(multiset<int> &st, int x) {
    if (!st.size()) {
        return -1;
    }
    auto it = st.upper_bound(x);
    if (it == st.begin()) {
        return -1;
    }
    return *(--it);
}

int getr(multiset<int> &st, int x) {
    if (!st.size()) {
        return -1;
    }
    auto it = st.lower_bound(x);
    if (it == st.end()) {
        return -1;
    }
    return *it;
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld%lld", &p[i].fi, &p[i].se);
        }
        sort(p + 1, p + 1 + n);
        multiset<int> st1, st2;
        for (int i = 1; i <= n; i++) {
            st2.insert(p[i].se);
        }
        int ans = INF;
        for (int i = 1; i <= n; i++) {
            st2.erase(st2.find(p[i].se));
            int mx = -INF;
            if (st2.size()) {
                mx = *(--st2.end());
            }
            ans = min(ans, abs(mx - p[i].fi));
            if (mx < p[i].fi) {
                int l = getl(st1, p[i].fi);
                int r = getr(st1, p[i].fi);
                if (l != -1) {
                    ans = min(ans, abs(max(mx, l) - p[i].fi));
                }
                if (r != -1) {
                    ans = min(ans, abs(max(mx, r) - p[i].fi));
                }
            }
            st1.insert(p[i].se);
        }
        printf("%lld\n", ans);
    }
}

F - Dense Subgraph

G - Closest Pair of Segments

H - Coins

I - Block Breaker

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 2005

using namespace std;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int T, n, m, q, ans;
bool vis[MAX_N][MAX_N];

bool ok(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

bool uns(int x, int y) {
    return (vis[x - 1][y] || vis[x + 1][y]) && (vis[x][y - 1] || vis[x][y + 1]);
}

void dfs(int x, int y) {
    ans++, vis[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (!vis[nx][ny] && ok(nx, ny) && uns(nx, ny)) {
            dfs(nx, ny);
        }
    }
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &q);
        for (int i = 0; i <= n + 1; i++) {
            for (int j = 0; j <= m + 1; j++) {
                vis[i][j] = false;
            }
        }
        int x, y;
        while (q--) {
            scanf("%d%d", &x, &y);
            ans = 0;
            if (!vis[x][y]) {
                ans++, vis[x][y] = true;
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i], ny = y + dy[i];
                    if (!vis[nx][ny] && ok(nx, ny) && uns(nx, ny)) {
                        dfs(nx, ny);
                    }
                }
            }
            printf("%d\n", ans);
        }
    }
}

J - Domino Covering

K - Make Rounddog Happy