专栏文章

题解：CF1998E1 Eliminating Balls With Merging (Easy Version)

__jxy
CF1998E1题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipobpct
此快照首次捕获于
2025/12/03 15:16
3 个月前
此快照最后确认于
2025/12/03 15:16
3 个月前
查看原文
和 这题 几乎一样。
观察样例后发现题意就是说有 nn 个数，每个数 aia_i 每次可以选择一个 j∈{i+1,i−1}j \in \{i+1,i-1\}，使得 ai≥aja_i \ge a_j，将aia_i 变为 ai+aja_i+a_j 并将 aja_j 删除，问有多少个 aia_i 可以将其它的 n−1n-1 个数全部删除。
显然我们删数是一块一块删的，能往左删就一直往左删，不能删了删右边，右边不行了再删左边，直到删完为止。
我们大概模拟一下这个过程，如果区间 [L,i−1][L,i-1] 的最大值小于等于 aia_i，这一段一定可以被 aia_i 删掉。同理，区间 [i+1,R][i+1,R] 的最大值小于等于 aia_i 也一定可以被删掉。其中，用 ST 表维护处区间最大值后 LL 和 RR 是可以二分算出来的。这样就做完了。
时间复杂度我不会证，估计是两个或者三个 log⁡\log，反正能过。
CPP
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;
int a[N], n;
ll s[N];
ll sum(int l, int r) {
    return s[r] - s[l - 1];
}
int st[N][30];
void st_init() {
    for (int i = 1; i <= n; i++) st[i][0] = a[i];
    int p = __lg(n);
    for (int k = 1; k <= p; k++) {
        for (int s = 1; s + (1 << k) <= n + 1; s++) {
            st[s][k] = max(st[s][k - 1], st[s + (1 << (k - 1))][k - 1]);
        }
    }
}
int mx(int l, int r) {
    int k = __lg(r - l + 1);
    int x = max(st[l][k], st[r - (1 << k) + 1][k]);
    return x;
}
int main() {
    int _;
    scanf("%d", &_);
    while (_--) {
        scanf("%d%*d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
        st_init();
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int l = i, r = i;
            ll res = a[i], lr = a[i];
            while (1) {
                int L = 1, R = l - 1, p = l;
                while (L <= R) {
                    int mid = L + R >> 1;
                    if (mx(mid, l - 1) <= res) {
                        p = mid;
                        R = mid - 1;
                    } else {
                        L = mid + 1;
                    }
                }
                if (p <= l - 1) {
                    res += sum(p, l - 1);
                    l = p;
                }
                L = r + 1, R = n, p = r;
                while (L <= R) {
                    int mid = L + R >> 1;
                    if (mx(r + 1, mid) <= res) {
                        p = mid;
                        L = mid + 1;
                    } else {
                        R = mid - 1;
                    }
                }
                if (r + 1 <= p) {
                    res += sum(r + 1, p);
                    r = p;
                }
                if (res == lr) break;
                lr = res;
                if (l == 1 && r == n) break;
            }
            if (res == s[n]) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...