[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;
}

[ABC372F] Teleporting Takahashi 2

思路

好题！看完题目，可以很快想到一个 \(dp\)，但是空间和时间复杂度显然都不允许，于是集中注意力，发现 \(m\le 50\)，这意味着只有不到 \(100\) 个点转移时会变，那么，就把两两之间有多余连边的点中间没有多余连接的点看成一条边，边权为所有边的总和，接着 \(dp\)。

考虑怎么统计答案，很显然，有多余连接的点可以直接求，而没有多余连接的点就是它所在的有向边指向的点的 \(k - i\) 步的方案数（\(i\) 为自己到达有向边指向的点的距离）。

代码

#include<iostream>
#define int long long

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 = 55, K = 2e5 + 10, mod = 998244353;
int n, m, k, ans;
int x[M], y[M];
bool vis[N];
struct edge{
    int v, w, nxt;
}e[N];
int head[N], cnt, id[N], tot;
void add(int u, int v, int w){
    e[++cnt] = (edge){v, w, head[u]};
    head[u] = cnt;
}
int dp[M << 2][K << 2];

signed main(){
    n = read(), m = read(), k = read();
    for (int i = 1; i <= m; i++) x[i] = read(), y[i] = read(), add((id[x[i]] == 0 ? id[x[i]] = ++tot : id[x[i]]), (id[y[i]] == 0 ? id[y[i]] = ++tot : id[y[i]]), 1);
    for (int i = 1, last = 1; i <= n; i++){
        bool ok = 0;
        vis[i] = 1;
        for (int j = 1; j <= m; j++) if (x[j] == i || y[j] == i) ok = 1;
        if (ok && i != 1) add((id[last] == 0 ? id[last] = ++tot : id[last]), (id[i] == 0 ? id[i] = ++tot : id[i]), i - last), vis[i] = 0, last = i;
        if (i == n){
            if (last != 1) add((id[last] == 0 ? id[last] = ++tot : id[last]), (id[1] == 0 ? id[1] = ++tot : id[1]), n - last + 1);
            else add((id[last] == 0 ? id[last] = ++tot : id[last]), 1, n);
        }
    }
    vis[1] = 0;
    dp[(id[1] == 0 ? id[1] = ++tot : id[1])][0] = 1;
    for (int i = 0; i <= k; i++){
        for (int u = 1; u <= tot; u++){
            for (int j = head[u]; j; j = e[j].nxt){
                int v = e[j].v, w = e[j].w;
                if (i + w <= k) dp[v][i + w] = (dp[v][i + w] + dp[u][i]) % mod;
            }
        }
    }
    for (int i = 1, last = 1; i <= n; i++){
        if (!vis[i]) ans = (ans + dp[(id[i] == 0 ? id[i] = ++tot : id[i])][k]) % mod, last = i;
        else{
            ans = (ans + dp[(id[last] == 0 ? id[last] = ++tot : id[last])][k - (i - last)]) % mod;
        }
    }
    cout << ans;
    return 0;
}

Invertible Bracket Sequences

思路

考虑一个合法的括号序列是怎样的，将 "(" 抽象成 \(1\)，将 ")" 抽象成 \(-1\)，那么整个序列的和为 \(0\)，同时每个位置的前缀和 \(\ge 0\)。

枚举一个反转的左端点，看有多少个右端点能与它反转后符合题目条件。设左端点为 \(l\)，右端点为 \(r\)，前缀和为 \(pre\)，反转区间的和为 \(pre'\)，那么 \(pre_r = pre_{l - 1} + pre'\) ，反转过后，\(pre_r\ge 0,pre'\rightarrow -pre'\)，所以 \(pre_{l - 1}\ge pre'\)，代入上式，\(2pre_{l - 1}\ge pre_r\)，且 \(l\) 到 \(r\) 之间的所有 \(pre_i\) 都要满足上式，而一个反转区间的和为 \(0\)，即 \(pre'=pre_{l - 1}\)，所以倒着做，存下等于 \(pre_{l - 1}\) 的 \(pre'\) 的位置，对于一个 \(l\)，求 \(l\) 到 \(pre'\) 的位置之间的最大值，如果最大值满足 \(pre_{l - 1}\ge maxn\) 那么这个位置一定可以，于是二分求最多的 \(r\)。

代码

#include<iostream>
#include<cstring>
#include<vector>

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 T, n;
long long ans;
char s[N];
int a[N], pre[N], t[N << 2];
void build(int now, int l, int r){
    if (l == r){
        t[now] = pre[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(now << 1, l, mid);
    build(now << 1 | 1, mid + 1, r);
    t[now] = max(t[now << 1], t[now << 1 | 1]);
}
int query(int now, int l, int r, int x, int y){
    if (x <= l && r <= y) return t[now];
    int mid = (l + r) >> 1, res = 0;
    if (x <= mid) res = max(res, query(now << 1, l, mid, x, y));
    if (mid + 1 <= y) res = max(res, query(now << 1 | 1, mid + 1, r, x, y));
    return res;
}
vector<int> cnt[N];

signed main(){
    T = read();
    while (T--){
        cin >> s + 1;
        n = strlen(s + 1);
        for (int i = 1; i <= n; i++) a[i] = (s[i] == '(' ? 1 : -1), pre[i] = pre[i - 1] + a[i];
        build(1, 1, n);
        for (int i = n; i >= 1; i--){
            int l = 0, r = cnt[pre[i]].size() - 1, k = r + 1;
            while (l <= r){
                int mid = (l + r) >> 1, res = query(1, 1, n, i, cnt[pre[i]][mid]);
                if (2 * pre[i] >= res){
                    r = mid - 1;
                    k = mid;
                }else{
                    l = mid + 1;
                }
            }
            ans += cnt[pre[i]].size() - k;
            cnt[pre[i]].emplace_back(i);
        }
        cout << ans << '\n';
        for (int i = 0; i <= n; i++) cnt[i].clear();
        ans = 0;
    }
    return 0;
}