主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：CF2070E Game with Binary String
最后更新于 2025-08-28 08:34:47
作者
2huk
分类
题解
题解
CF2070E
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
考察一个序列先手必胜的条件。 对于后手，如果有相邻的 $0,1$ 是一定要操作它们的，因为这样能减少 $0$ 的数量。 注意到序列是环形，那么存在相邻的 $0,1$ 等价于序列不全相同。显然序列全相同时胜负能定。所以后手只能操作 $0,1$ 而不是 $1,1$。 令序列中 $0,1$ 的个数分别为 $c_0,c_1$。注意到一轮操作后 $0$ 会少三个，$1$ 会少一个，也就是最多能操作 $\min(c_0/3,c_1)$ 轮。于是考虑 $c_0,c_1$ 的关系对先手是否必胜的影响。 - $c_0 - 3c_1 \ge 2$：操作完 $c_1$ 轮后全是 $0$，先手胜。 - $c_0-3c_1=1$：操作完 $c_1$ 轮后只剩一个 $0$，后手胜。 - $c_0-3c_1=0$：操作完 $c_1$ 轮后全删完了，后手胜。 - $c_0-3c_1=-1$：操作完 $c_1-1$ 轮后，还剩两个 $0$ 和一个 $1$，先手胜。 - $c_0 - 3c_1=-2$：操作完 $c_1-1$ 轮后，还剩一个 $0$ 和一个 $1$，后手胜。 - $c_0-3c_1\le -3$：操作完 $\lfloor c_0/3 \rfloor$ 轮后全是 $0$，先手胜。 也就是说先手胜等价于 $c_0 - 3c_1 \ge 2$ 或 $c_0-3c_1=-1$。 那很好了，我们视作 $0$ 的权值为 $1$，$1$ 的权值为 $-3$，然后做这个权值的前缀和，那么 $[l, r]$ 合法等价于 $s_r-s_{l-1} \ge 2$ 或 $s_r-s_{l-1} = -1$。随便搞一下就好了。
正在渲染内容...
点赞
3
收藏
0
