题解：CF2070E Game with Binary String

· · 题解

考察一个序列先手必胜的条件。

对于后手，如果有相邻的 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_0-3c_1=-1。

那很好了，我们视作 0 的权值为 1，1 的权值为 -3，然后做这个权值的前缀和，那么 [l, r] 合法等价于 s_r-s_{l-1} \ge 2 或 s_r-s_{l-1} = -1。随便搞一下就好了。