Asusetic
0%

2021.05.23模拟赛

发表于 分类于 Valine：
本文字数： 1.5k 阅读时长 ≈ 1 分钟

字符串场（存疑）

2021.05.23 模拟赛

T1 序列的故事

比较拉跨的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
60
61
62
63
64
65
#include <cstdio>
#include <iostream>
using namespace std;
typedef unsigned long long ull;
const int N     = 500010;
const ull Base1 = 19260817;
int n, prime[N], mindiv[N];
int pcnt;
bool vis[N];
char s[N];
int factor[N];
ull pw[N], Hash[N];
void pre(int x) {
    for (int i = 2; i <= x; i++) {
        if (!vis[i]) {
            prime[++pcnt] = i;
            mindiv[i]     = prime[pcnt];
        }
        for (int j = 1; j <= pcnt && prime[j] * i <= x; j++) {
            vis[prime[j] * i]    = 1;
            mindiv[prime[j] * i] = prime[j];
            if (!(i % prime[j])) {
                break;
            }
        }
    }
}
ull getHash(int l, int r) {
    return Hash[r] - Hash[l - 1] * pw[r - l + 1];
}
bool check(int l, int r, int len) {
    return getHash(l, r - len) == getHash(l + len, r);
}
int main() {
    pre(N);
    cin >> n >> s + 1;
    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i]   = pw[i - 1] * Base1;
        Hash[i] = Hash[i - 1] * Base1 + s[i] - 'a' + 1;
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        int len = r - l + 1;
        if (check(l, r, 1)) {
            cout << 1 << endl;
        } else {
            int fcnt = 0;
            while (len != 1) {
                factor[++fcnt] = mindiv[len];
                len            = len / mindiv[len];
            }
            len = r - l + 1;
            for (int i = 1; i <= fcnt; i++) {
                if (check(l, r, len / factor[i])) {
                    len /= factor[i];
                }
            }
            printf("%d\n", len);
        }
    }
}

T2 大(big)

题面

其实明白了操作是啥就蛮好想的

实际上那个 ⌊2x2n⌋+(2x mod 2n)\lfloor\frac{2x}{2^n}\rfloor+(2x \bmod 2^n) 就是循环左移一位

对于异或这种按位的操作其实根本没啥影响

在 ii 后面操作就相当于把 ii 前面的所以数字全都循环左移一位

一共就 m+1m+1 种可能的异或值，全插进 Trie 里扫就行，如果有俩儿子说明不管怎么选都有一种方法把这一位变成 00 反之不能

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
60
61
62
63
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m;
ll a[N];
namespace Trie {
int ch[N * 25][2], tot, rt = 0;
void insert(ll x) {
    int now = rt;
    for (int i = n; i; i--) {
        int id = (x >> (i - 1)) & 1;
        if (!ch[now][id]) {
            ch[now][id] = ++tot;
        }
        now = ch[now][id];
    }
}
} // namespace Trie
ll ans = 0;
ll lshift(ll s) {
    return ((s << 1ll) / (1ll << n) + (s << 1ll) % (1ll << n));
}
int cnt;
void dfs(int now, int dep, ll sum) {
    using namespace Trie;
    if (dep == n) {
        if (sum > ans) {
            ans = sum;
            cnt = 1;
        } else if (sum == ans) {
            ++cnt;
        }
        return;
    }
    if (ch[now][0] && ch[now][1]) {
        dfs(ch[now][0], dep + 1, sum);
        dfs(ch[now][1], dep + 1, sum);
    } else if (ch[now][0]) {
        dfs(ch[now][0], dep + 1, sum | (1ll << (n - dep - 1)));
    } else if (ch[now][1]) {
        dfs(ch[now][1], dep + 1, sum | (1ll << (n - dep - 1)));
    }
    return;
}
ll xors = 0, xorp = 0;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        scanf("%lld", &a[i]);
        xors ^= a[i];
    }
    Trie::insert(xors);
    for (int i = 1; i <= m; i++) {
        xorp ^= lshift(a[i]);
        xors ^= a[i];
        Trie::insert(xorp ^ xors);
    }
    dfs(0, 0, 0);
    printf("%lld\n%d\n", ans, cnt);
    return 0;
}

T3 最长重复子串

题面

n2n^2 过 10510^5 绝了

考虑分治做法

对于 SS 的重复子串 Sl,rS_{l,r} midmid 为分治中点，当 r≤midr \le mid 或 l≥midl \ge mid 都可以直接分治处理

中间的合并这样考虑

如果这个重复子串长度为 2k2k

那 Sl,r=AA=Sl,l+kSr−k,rS_{l,r}=AA=S_{l,l+k}S_{r-k,r}

当 l+k≤midl+k \le mid 时

有 Sl,mid−k=Sl+k,midS_{l,mid-k}=S_{l+k,mid} 且 Smid−k,l+k=Smid,rS_{mid-k,l+k}=S_{mid,r}

即 mid−k−l≤LCS(Smid−l,Smid)mid-k-l \le LCS(S_{mid-l},S_{mid})

l+2k−m≤LCP(Smid−k,n,Smid,n)l+2k-m\le LCP(S_{mid-k,n},S_{mid,n})

整理的

k≤LCP(Smid−k,n,Smid,n)+LCS(Smid−k,Smid)k\le LCP(S_{mid-k,n},S_{mid,n})+LCS(S_{mid-k},S_{mid})

另一种情况 l+k>midl+k > mid

同理得 k≤LCP(Smid,n,Smid+k,n)+LCS(Smid,Smid+k)k \le LCP(S_{mid,n},S_{mid+k,n})+LCS(S_{mid},S_{mid+k})

枚举长度即可

至于 LCP or LCS 能求就行 exKMP或者SA均可

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e6 + 5;
int len, ans;
char s[N];
struct SA {
    int len;
    int sa[N], rk[N], oldrk[N], cnt[N], id[N], px[N], height[N];
    bool cmp(int x, int y, int w) {
        return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
    }
    void build(char *s) {
        int m = 127, p;
        for (int i = 1; i <= len; i++) {
            rk[i] = s[i];
            ++cnt[rk[i]];
        }
        for (int i = 1; i <= m; i++) {
            cnt[i] += cnt[i - 1];
        }
        for (int i = len; i >= 1; i--) {
            sa[cnt[rk[i]]--] = i;
        }
        for (int w = 1;; w *= 2, m = p) {
            p = 0;
            for (int i = len; i > len - w; i--) {
                id[++p] = i;
            }
            for (int i = 1; i <= len; i++) {
                if (sa[i] > w) {
                    id[++p] = sa[i] - w;
                }
            }
            memset(cnt, 0, sizeof(cnt));
            for (int i = 1; i <= len; i++) {
                px[i] = rk[id[i]];
                ++cnt[px[i]];
            }
            for (int i = 1; i <= m; i++) {
                cnt[i] += cnt[i - 1];
            }
            for (int i = len; i >= 1; i--) {
                sa[cnt[px[i]]--] = id[i];
            }
            memcpy(oldrk, rk, sizeof(rk));
            p = 0;
            for (int i = 1; i <= len; i++) {
                rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
            }
            if (p == len) {
                for (int i = 1; i <= len; i++) {
                    sa[rk[i]] = i;
                }
                break;
            }
        }
    }
    void getHeight(char *s) {
        for (int i = 1, k = 0; i <= len; ++i) {
            if (k)
                --k;
            int j = sa[rk[i] - 1];
            while (s[i + k] == s[j + k])
                ++k;
            height[rk[i]] = k;
        }
    }
    int st[N][21], lg[N];
    void init(char *s, int n) {
        len = n;
        build(s);
        getHeight(s);
        lg[1] = 0;
        for (int i = 2; i <= len; ++i)
            lg[i] = lg[i >> 1] + 1;
        for (int i = 1; i <= len; ++i) {
            st[i][0] = height[i];
        }
        for (int j = 0; j < 20; ++j) {
            for (int i = 1; i + (1 << j) <= len; ++i) {
                st[i][j + 1] = std::min(st[i][j], st[i + (1 << j)][j]);
            }
        }
    }
    int query(int l, int r) {
        int t = lg[r - l + 1];
        return min(st[l][t], st[r - (1 << t) + 1][t]);
    }
    int lcp(int x, int y) {
        if (x == y)
            return len - x + 1;
        int l = rk[x], r = rk[y];
        if (l > r)
            swap(l, r);
        return query(l + 1, r);
    }
} S, revS;
int lcp(int x, int y) {
    return S.lcp(x, y);
}
int lcs(int x, int y) {
    return revS.lcp(revS.len - x + 1, revS.len - y + 1);
}

void solve(int l, int r) {
    if (l >= r || r - l + 1 <= ans * 2)
        return;
    int mid = (l + r) >> 1;
    for (int i = mid - l + 1; i > ans; --i)
        if (i <= lcs(mid - i, mid) + lcp(mid - i + 1, mid + 1))
            ans = max(ans, i);
    for (int i = r - mid; i > ans; --i)
        if (i <= lcs(mid, mid + i) + lcp(mid + 1, mid + i + 1))
            ans = max(ans, i);
    solve(l, mid);
    solve(mid + 1, r);
}

int main() {
    cin >> s + 1;
    len = strlen(s + 1);
    S.init(s, len);
    reverse(s + 1, s + len + 1);
    revS.init(s, len);
    solve(1, len);
    cout << ans * 2 << endl;
    return 0;
}

T4 卷积神经网络

题面

肯定是得数不合法的方案，然后看到 cc 这么小必然得把状态压下来

然后不会了

先大力设 dp 式子 dp[x][y][S][i][j]dp[x][y][S][i][j] 表示 (x,y)(x,y) 轮廓线上的点能否匹配第一个模板串的末尾的状态 SS ，第一行匹配到 ii 第二行匹配到 jj 的方案数

考虑从 (x,y)→(x,y+1)(x,y) \rightarrow (x,y+1) 的转移

枚举这一位填啥，如果填对了那么对应的 i/ji/j 会加一，否则应该不断的跳 borderborder ，SS 仅需判断是否为 cc 即可

仅有当 SS 的 jj 位为 11 且 j=cj=c 时不能转移，其他均可

上一行到下一行仅需把上一行的状态全加进去即可

前两维完全可以滚动掉

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 105, M = 13;
const int mod = 1e9 + 7;
int n, m, c, q;
int dp[2][(1 << M)][7][7];
char c1[7], c2[7];
int a1[7], a2[7], nxt1[7], nxt2[7], to1[7][4], to2[7][4];
void KMP(int *s, int *nxt) {
    int j = 0;
    for (int i = 2; i <= c; i++) {
        if (j && s[j + 1] != s[i]) {
            j = nxt[j];
        }
        if (s[j + 1] == s[i]) {
            j++;
        }
        nxt[i] = j;
    }
}
void pre(int *s, int *nxt, int to[][4]) {
    for (int i = 0; i < c; i++) {
        for (int j = 0; j <= 2; j++) {
            int k = i;
            while (k && s[k + 1] != j) {
                k = nxt[k];
            }
            if (s[k + 1] == j) {
                k++;
            }
            to[i][j] = k;
        }
    }
}
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b /= 2;
    }
    return res;
}
int main() {
    cin >> n >> m >> c >> q;
    int U      = 1 << (m - c + 1);
    auto trans = [](char c) -> int {
        if (c == 'W')
            return 0;
        if (c == 'B')
            return 1;
        if (c == 'X')
            return 2;
        return 0;
    };
    while (q--) {
        cin >> c1 + 1 >> c2 + 1;
        for (int i = 1; i <= c; i++) {
            a1[i] = trans(c1[i]);
            a2[i] = trans(c2[i]);
        }
        KMP(a1, nxt1);
        KMP(a2, nxt2);
        pre(a1, nxt1, to1);
        pre(a2, nxt2, to2);
        memset(dp[0], 0, sizeof(dp[0]));
        dp[0][0][0][0] = 1;
        int now        = 1;
        for (int i = 1; i <= n; i++) {
            memset(dp[now], 0, sizeof(dp[now]));
            for (int s = 0; s < U; s++) {
                for (int a = 0; a < c; a++) {
                    for (int b = 0; b < c; b++) {
                        dp[now][s][0][0] += dp[now ^ 1][s][a][b];
                        dp[now][s][0][0] %= mod;
                    }
                }
            }
            now ^= 1;
            for (int j = 1; j <= m; j++) {
                memset(dp[now], 0, sizeof(dp[now]));
                for (int s = 0; s < U; s++) {
                    for (int a = 0; a < c; a++) {
                        for (int b = 0; b < c; b++) {
                            if (!dp[now ^ 1][s][a][b])
                                continue;
                            for (int p = 0; p <= 2; p++) {
                                int pa = to1[a][p];
                                int pb = to2[b][p];
                                int S  = s;
                                if (j >= c) {
                                    if ((S >> (j - c)) & 1) {
                                        S ^= 1 << (j - c);
                                    }
                                }
                                if (pa == c) {
                                    S ^= 1 << (j - c);
                                    pa = nxt1[c];
                                }
                                if (pb == c) {
                                    if ((s >> (j - c)) & 1) {
                                        continue;
                                    }
                                    pb = nxt2[c];
                                }
                                dp[now][S][pa][pb] += dp[now ^ 1][s][a][b];
                                dp[now][S][pa][pb] %= mod;
                            }
                        }
                    }
                }
                now ^= 1;
            }
        }
        ll ans = qpow(3, n * m);
        for (int i = 0; i < U; i++) {
            for (int j = 0; j < c; j++) {
                for (int k = 0; k < c; k++) {
                    ans = (ans - dp[now ^ 1][i][j][k] + mod) % mod;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}
// Asusetic eru quionours

我知道这图超大，但我就是想试一下

Kal'tsit.jpeg