2024 停课做题总结

[ABC372D] Buildings

思路

正着做不方便，倒着用单调栈做一遍就行了。

代码

#include<iostream>

using namespace std;

inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}

const int N = 2e5 + 10;
int n, ans[N];
int h[N], stk[N], top;

int main(){
    n = read();
    for (int i = 1; i <= n; i++) h[i] = read();
    h[0] = 0x7fffffff;
    for (int i = n; i >= 1; i--){
        ans[i] = top;
        while (h[stk[top]] < h[i]) top--;
        stk[++top] = i;
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
    return 0;
}

[ABC372E] K-th Largest Connected Components

思路

注意到，\(k\le 10\)，所以暴力维护前 \(10\) 个点，然后使用并查集实现连边，利用归并排序实现前 \(10\) 个点，注意：自己也算能走到自己。

代码

#include<iostream>

using namespace std;

inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}

const int N = 2e5 + 10, M = 15;
int n, q;
int fa[N], e[N][M], a[N], len[N];
int find(int x){
    return (x == fa[x] ? fa[x] : fa[x] = find(fa[x]));
}
void merge(int x, int y){
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    fa[fx] = fy;
    for (int i = 1, j = 1, k = 1; k <= min(10, len[fx] + len[fy]); k++){
        if (e[fx][i] > e[fy][j]) a[k] = e[fx][i++];
        else a[k] = e[fy][j++];
    }
    len[fy] = min(10, len[fx] + len[fy]);
    for (int i = 1; i <= len[fy]; i++) e[fy][i] = a[i];
}

int main(){
    n = read(), q = read();
    for (int i = 1; i <= n; i++) fa[i] = i, e[i][1] = i, len[i] = 1;
    for (int i = 1; i <= q; i++){
        int opt = read(), u = read(), v = read();
        if (opt == 1) merge(u, v);
        else{
            int x = find(u);
            cout << (e[x][v] == 0 ? -1 : e[x][v]) << '\n';
        }
    }
    return 0;
}