题解：CF2070E Game with Binary String

paper_ · 2025-03-04 09:59:57 · 题解

主要思路

很显然 Bob 每次就一定会尽可能取 01，这样就发现每一轮都会消掉一个 1 三个 0。

令序列中 0 的个数为 c_0，1 的个数为 c_1。

分类讨论：

• 若 c_0-3\times c_1 \ge 2，最终一定会剩下不少于两个的 0，Alice 胜。
• 若 c_0 -3 \times c_1 = 0/1，最终剩下 0/1 个 0，Alice 无法操作，Bob 胜。
• 若 c_0 - 3 \times c_1 = -1，Alice 操作后只剩下一个 1，Bob 无法操作，Alice 胜。
• 若 c_0 - 3 \times c_1 \le -2，最终会剩下若干个 1，Bob 胜。

当然，每轮 Alice 能操作的前提是有相邻的两个 0，所以要满足：c_0-c_1 \ge 1 才能保证，发现与 Alice 获胜的条件并不冲突，很多用这个方法的题解根本没有考虑这个点。

综上，只需要考虑满足 c_0-3\times c_1 \ge 2 或 c_0-3\times c_1 = -1 的区间个数就行了。

令 num_i=c_{0,i} - 3 \times c_{1,i}，c_{0/1,i} 表示 1 \sim i 中 0/1 的个数。

原式就变为 num_r - num_{l-1} \ge 2 或 num_r - num_{l-1} = -1 。

接下来就是动态开点板子了。

code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 300010;
char s[N];
int rt = 1, idx = 1;
struct TREE {
    int l, r, sum;
}tr[N * 20];
void insert(int &k, int l, int r, int p) {
    if (!k) k = ++ idx;
    if (l == r) {
        tr[k].sum ++;
        return;
    }
    int mid = l + r >> 1;
    if (p <= mid) insert(tr[k].l, l, mid, p);
    else insert(tr[k].r, mid + 1, r, p);
    tr[k].sum = tr[tr[k].l].sum + tr[tr[k].r].sum;
}
int query(int k, int l, int r, int ql, int qr) {
    if (!k) return 0;
    if (l >= ql && r <= qr) return tr[k].sum;
    int mid = l + r >> 1, re = 0;
    if (ql <= mid) re = query(tr[k].l, l, mid, ql, qr);
    if (qr > mid) re += query(tr[k].r, mid + 1, r, ql, qr);
    return re;
}
signed main() {
    int n;cin >> n;
    cin >> s + 1;
    int c0 = 0, c1 = 0, ans = 0;
    insert(rt, -1e6, 1e6, 0);
    for (int i = 1; i <= n; i ++ ) {
        if (s[i] == '0') c0 ++;
        else c1 ++;
        int num = c0 - c1 * 3;
        ans += query(1, -1e6, 1e6, -1e6, num - 2) + query(1, -1e6, 1e6, num + 1, num + 1);
        insert(rt, -1e6, 1e6, num);
    }
    cout << ans;
    return 0;
}