CF1320 D. Reachable Strings

发表于 | 阅读数

给你一个字符串$s$。可以将一段$110$变成$011$，或者$011$变成$110$。问是否能从$s[l,l+len-1]\rightarrow s[r,r+len-1]$

对于一个区间需要注意

  • 01数目相同
  • 通过变换$0$的奇偶不会发生变换，$0$的顺序也不会发生变换。也就是说如果之前变换为$0(奇）,0(偶），0(奇），0（偶）$，之后还是$0(奇）,0(偶），0(奇），0（偶）$。显然可以用$hash$维护，把奇的$0$和偶的$0$分别设置不同互质的数。
  • 发现如果$l\&1$,会$0$的奇偶会倒置。那么我们只需要维护两种$hash$。
代码 
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
56
57
58
59
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const ll cc = 23333;
ll base[N];
ll h[2][N], p[2];
int n, cnt[N];
char s[N];
ll getans(int l, int r)
{
    return (h[l & 1][r] + mod - h[l & 1][l - 1] * base[cnt[r] - cnt[l - 1]] % mod) % mod;
}
int main()
{
    scanf("%d", &n);
    scanf("%s", s + 1);
    base[0] = 1;
    for (int i = 1; i <= n; i++)
        base[i] = base[i - 1] * cc % mod;
    p[0] = 5, p[1] = 3;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '0')
        {
            h[0][i] = h[0][i - 1] * cc % mod + p[i & 1];
            h[0][i] %= mod;
            h[1][i] = h[1][i - 1] * cc % mod + p[(i & 1) ^ 1];
            h[1][i] %= mod;
            cnt[i] = cnt[i - 1] + 1;
        }
        else
        {
            cnt[i] = cnt[i - 1];
            h[0][i] = h[0][i - 1];
            h[1][i] = h[1][i - 1];
        }
    }
    int q;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        int l, r, len;
        scanf("%d%d%d", &l, &r, &len);
        if (getans(l, l + len - 1) == getans(r, r + len - 1))
            printf("Yes\n");
        else
            printf("No\n");
    }
}