专栏文章

题解：CF2070E Game with Binary String

ppaper_
CF2070E题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miq247vc
此快照首次捕获于
2025/12/03 21:42
3 个月前
此快照最后确认于
2025/12/03 21:42
3 个月前
查看原文

主要思路

很显然 Bob 每次就一定会尽可能取 0101，这样就发现每一轮都会消掉一个 11 三个 00。
令序列中 00 的个数为 c0c_0，11 的个数为 c1c_1。
分类讨论：
  • 若 c0−3×c1≥2c_0-3\times c_1 \ge 2，最终一定会剩下不少于两个的 00，Alice 胜。
  • 若 c0−3×c1=0/1c_0 -3 \times c_1 = 0/1，最终剩下 0/10/1 个 00，Alice 无法操作，Bob 胜。
  • 若 c0−3×c1=−1c_0 - 3 \times c_1 = -1，Alice 操作后只剩下一个 11，Bob 无法操作，Alice 胜。
  • 若 c0−3×c1≤−2c_0 - 3 \times c_1 \le -2，最终会剩下若干个 11，Bob 胜。
当然，每轮 Alice 能操作的前提是有相邻的两个 00，所以要满足：c0−c1≥1c_0-c_1 \ge 1 才能保证，发现与 Alice 获胜的条件并不冲突，很多用这个方法的题解根本没有考虑这个点。
综上，只需要考虑满足 c0−3×c1≥2c_0-3\times c_1 \ge 2 或 c0−3×c1=−1c_0-3\times c_1 = -1 的区间个数就行了。
令 numi=c0,i−3×c1,inum_i=c_{0,i} - 3 \times c_{1,i}，c0/1,ic_{0/1,i} 表示 1∼i1 \sim i 中 0/10/1 的个数。
原式就变为 numr−numl−1≥2num_r - num_{l-1} \ge 2 或 numr−numl−1=−1num_r - num_{l-1} = -1 。
接下来就是动态开点板子了。

code

CPP
#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;
}

评论

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

正在加载评论...