题解：P2418 yyy loves OI IV

Suin_tryin · 2025-10-07 17:47:42 · 题解

这是半个乱搞做法。

首先我一开始读错题了，没有考虑到整个宿舍膜拜同一个人的情况。

下面一段是部分的正解，也是这篇题解的侧重点。

设膜拜 yyy 的人是 1, 膜拜 c01 的人是 -1。此时一个区间的和是区间中膜拜 yyy 的人数减去膜拜 c01 的人数。计算前缀和。

状态定义：dp_i 表示前 i 个人，最小的宿舍数量。

暴力是 O(n^2) 的。考虑优化。

考虑一个合法区间 j + 1 \sim i ，\lvert{sum_i - sum_j}\rvert \le m，拆开可得 sum_i - m \le sum_j \le sum_i + m。我们其实要找的就是满足这个条件的最小的 dp_j。那很好了，我们直接把 dp_i 丢到一颗线段树里面，具体地，点 sum_i，值 dp_i，查 sum_i-m \sim sum_i+m。单点修改，区间查询，好写。

::::warning[70pts]

#include<iostream>
#include<algorithm>
using namespace std;
int n, m, bn;
int a[500010], sum[500010], mx[500010], mn[500010], b[1500010];
int tr[3000010], dp[500010];
void build(int u, int l, int r) {
    tr[u] = 1e9;
    if(l == r) return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}
void insert(int u, int l, int r, int x, int k) {
    tr[u] = min(tr[u], k);
    if(l == r) return ;
    int mid = l + r >> 1;
    if(x <= mid) insert(u << 1, l, mid, x, k);
    else insert(u << 1 | 1, mid + 1, r, x, k);
}
int query(int u, int l, int r, int x, int y) {
    if(x <= l && r <= y) return tr[u];
    int mid = l + r >> 1;
    int ans = 1e9;
    if(x <= mid) ans = min(ans, query(u << 1, l, mid, x, y));
    if(y > mid) ans = min(ans, query(u << 1 | 1, mid + 1, r, x, y));
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
        if(a[i] == 2) a[i] = -1;
        sum[i] = sum[i - 1] + a[i];
        b[++bn] = sum[i]; b[++bn] = sum[i] - m; b[++bn] = sum[i] + m;
    }
    sort(b + 1, b + bn + 2);
    bn = unique(b + 1, b + bn + 2) - b - 1;
    for(int i = 0; i <= n; i ++) {
        mx[i] = lower_bound(b + 1, b + bn + 1, sum[i] + m) - b;
        mn[i] = lower_bound(b + 1, b + bn + 1, sum[i] - m) - b;
        sum[i] = lower_bound(b + 1, b + bn + 1, sum[i]) - b;
    }
    build(1, 1, bn);
    insert(1, 1, bn, sum[0], 0);
    for(int i = 1; i <= n; i ++) {
        dp[i] = query(1, 1, bn, mn[i], mx[i]) + 1;
        insert(1, 1, bn, sum[i], dp[i]);
    }
    cout << dp[n] << '\n';
    return 0;
}

::::

你注意到三个 WA 的点数据范围不大。

然后就是乱搞了。

for(int i = 1; i <= n; i ++) {
    dp[i] = query(1, 1, bn, mn[i], mx[i]) + 1;
    for(int j = i - 1; j >= 1; j --) {
        if(a[j] == a[j + 1]) dp[i] = min(dp[i], dp[j - 1] + 1);
        else break;
    }
    insert(1, 1, bn, sum[i], dp[i]);
}