Rigged Games

题目大意

给定一个长度为$n(1 \le n \le 10^5)$的$01$字符串以及两个整数$a$和$b(1 \le a, b \le 10 ^ 5)$，$1$表示这一小局$team \ A$获胜，$0$则表示$team \ B$获胜。当一个$team$获胜$a$小局后，记作获胜一大局，并将小局比分清空。获胜$b$大局后则赢得最终胜利。问将这个字符串以第$i(1 \le i \le n)$位作为起点开始循环时，最终获胜的队伍是不是$team$，若是输出$1$，否则输出$0$。

解题思路

考虑对于每个起点$i$预处理出从这个点开始完成一大局比赛后第二局比赛的起点，以及这一大局$team\ A$是否获胜。自然想到再用倍增预处理出进行$2 ^ 1,2^2,2^3,\dots$大局后$team\ A$获胜的次数。然后处理询问，只需要从最高位往下遍历凑出有一个队获胜的条件即可。至于预处理大局的起点，可以联想到双指针，因为每一小局在$1$~$n$上是连续的。

最后将上面的想法整理起来即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
#define maxn 100100
#define int long long
using namespace std;
const double eps = 1e-8;
int f[maxn][22], sum[maxn][22];

void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    string s;  cin >> s;
    int cnta = 0, cntb = 0;
    for (int i = 0, j = 0; i < n; ++i) {
        while(cnta < a && cntb < a) {
            if(s[j] == '0')  cntb++;
            else  cnta++;
            j = (j + 1) % n;
        }
        f[i][0] = j;
        sum[i][0] = (cnta > cntb);
        if(s[i] == '0')  cntb--;
        else  cnta--;
        // cout << sum[i][0] << ' ' << f[i][0] << '\n';
    }
    for (int j = 1; j < 20; ++j) {
        for (int i = 0; i < n; ++i) {
            sum[i][j] = sum[i][j - 1] + sum[f[i][j - 1]][j - 1];
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
    for (int i = 0; i < n; ++i) {
        int cur = 0, pos = i;
        cnta = 0, cntb = 0;
        for (int j = 19; j >= 0 && cnta < b && cntb < b; --j) {
            if(cur + (1 << j) > 2 * b - 1)  continue;
            if(cnta + sum[pos][j] > b)  continue;
            if(cntb + (1 << j) - sum[pos][j] > b)  continue;
            cnta += sum[pos][j];  cntb += (1 << j) - sum[pos][j];
            cur += (1 << j);  pos = f[pos][j];
        }
        // cout << cnta << ' ' << cntb << '\n';
        if(cnta == b)  cout << 1;
        else  cout << 0;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}