CF2089B2 Canteen (Hard Version) 题解

StayAlone · 2025-04-06 14:31:07 · 题解

嗯？这不是模拟题吗？

一个纯模拟做法，无法从 Easy Version 导出。

时间复杂度 \mathcal O(\frac{n^2}{w})，但是跑得很快！

当一个 a_i 变成 0 之后，称之为无效；当一个 b_i 变成 0 之后，称之为无效。可以发现，每一次操作只有 a_i,b_i 均有效才有意义，每一次有意义的操作之后，要么 a_i 变得无效，要么 b_i 变得无效。

最初共 2n 个有效元素，每次有效操作减少一个有效元素，只要能找到每一轮的有效操作，时间复杂度就是对的。

考虑用两个 bitset 分别维护 a_i 和 b_i 的有效状态，每一轮对 a_i 的 bitset 右移，再将两个 bitset 按位与，就找到了有效操作的位置！

通过模拟，可以得知每一轮 a_i 的减少量，那么原问题就迎刃而解了。

这里手写 bitset，减少每个有效操作的代价是 \mathcal O(w)，因为要枚举其所在的 unsigned long long。总时间复杂度 \mathcal O(\frac{n^2}{w}+wn)，w 取 \sqrt n 最优，在线求一个 \sqrt n 位机。

由于一些原因，这里 w=64。

int n, a[MAXN], b[MAXN], tim, mx;
ull W, k, S, Sn;

struct {
    ull val[3200];

    il int query(int i) {
        return val[i >> 6] >> (i & 63) & 1;
    }

    il void change(int i) {
        val[i >> 6] ^= 1ull << (i & 63);
    }

    il void right() {
        int p = query(n - 1);
        rep2(i, mx, 1) {
            val[i] <<= 1;
            val[i] |= val[i - 1] >> 63;
        } val[0] <<= 1; val[0] |= p;
    }

    il void init() {
        rep1(i, 0, mx) val[i] = -1;
    }
} bal, cas;

il void find() {
    rep1(i, 0, mx) if (W = (bal.val[i] & cas.val[i])) {
        int pre = i << 6;
        rep1(j, 0, 63) if (W >> j & 1) {
            int x = pre + j, y = x < tim ? x - tim + n : x - tim, t = min(b[x], a[y]);
            if (x >= n) break;
            Sn += t;
            if (!(a[y] -= t)) bal.change(x);
            if (!(b[x] -= t)) cas.change(x);
        }
    }
}

il void solve() {
    read(n, k); mx = n - 1 >> 6; bal.init(); cas.init(); tim = S = Sn = 0;
    rer(i, 0, n - 1, a), S += a[i]; rer(i, 0, n - 1, b);
    if (k >= S) return puts("0"), void();
    while (true) {
        find(), ++tim;
        if (Sn + k >= S) return printf("%d\n", tim), void();
        bal.right();
    }
}

int main() {
    for (int T = read(); T--; ) solve();
    return 0;
}