2025牛客暑期多校训练营6

大概情况是这样的

STATUS	COUNT
AC	5
赛后补	1

排名是 161，这场配合明显比之前好一点了，能做出来的基本上都做了，没有很大的遗憾了

B. Base Conversion Master#

这么简单的题，一直没人做，最后被我捡了个漏……就是一个二分，唯一需要考虑的地方就是怎么防止非法数据把 long long 炸掉。

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
typedef long long LL;
7
const int N = 200010;
8
vector<LL> a[N];
9
int n;
10
LL y, M;
11

12
LL calc(LL s) {
13
    __int128_t cur = 0;
14
    for (int i = 1; i <= n; ++i) {
15
        cur = 0;
16
        for (int j : a[i]) {
17
            if (j >= s) return -1;
18
            cur = cur * s + j;
19
            if (cur >= 1000000010) {
20
                cur = 1000000010;
21
                break;
22
            }
23
        }
24
        s = cur;
25
    }
26
    return s;
27
}
28

29
LL checkl(LL s) {
30
    __int128_t cur = 0;
31
    for (int i = 1; i <= n; ++i) {
32
        cur = 0;
33
        for (int j : a[i]) {
34
            if (j >= s) return false;
35
            cur = cur * s + j;
36
            if (cur >= 1000000010) {
37
                cur = 1000000010;
38
                break;
39
            }
40
        }
41
        s = cur;
42
    }
43
    return s >= y;
44
}
45

46
LL checkr(LL s) {
47
    __int128_t cur = 0;
48
    for (int i = 1; i <= n; ++i) {
49
        cur = 0;
50
        for (int j : a[i]) {
51
            if (j >= s) return true;
52
            cur = cur * s + j;
53
            if (cur >= 1000000010) {
54
                cur = 1000000010;
55
                break;
56
            }
57
        }
58
        s = cur;
59
    }
60
    return s <= y;
61
}
62

63
int main() {
64
    int T;
65
    scanf("%d", &T);
66
    while (T--) {
67
        scanf("%d%lld%lld", &n, &y, &M);
68
        for (int i = 1; i <= n; ++i) {
69
            int k;
70
            scanf("%d", &k);
71
            a[i].resize(k);
72
            for (int j = 0; j < k; ++j) scanf("%lld", &a[i][j]);
73
        }
74
        // zuo bian jie
75
        LL l = 2, r = M;
76
        while (l < r) {
77
            LL mid = l + r >> 1;
78
            if (checkl(mid)) r = mid;
79
            else l = mid + 1;
80
        }
81
        LL rr = calc(l);
82
        if (rr == -1 || rr != y) {
83
            printf("-1 -1\n");
84
            continue;
85
        }
86
        else printf("%lld ", l);
87
        // you bian jie
88
        l = 2, r = M;
89
        while (l < r) {
90
            LL mid = l + r + 1 >> 1;
91
            if (checkr(mid)) l = mid;
92
            else r = mid - 1;
93
        }
94
        printf("%lld\n", r);
95
    }
96
    return 0;
97
}

C. Stack ^队友#

刚开始我卡了一会儿，讨论的时候我受到只考虑最后一个数的位置的启发想出来了正解，两个人的思路整合一下就完整了。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 500010;
6
const int MOD = 998244353;
7

8
long long f[N][4];
9

10
int main() {
11
    f[0][0] = 1;
12
    for (int i = 1; i <= 500000; ++i) {
13
        f[i][0] = f[i - 1][0] * i % MOD;
14
        f[i][1] = (f[i - 1][1] * i % MOD + f[i - 1][0] % MOD) % MOD;
15
        f[i][2] = (f[i - 1][2] * (i - 1) % MOD + f[i - 1][0] + 2LL * f[i - 1][1] + f[i - 1][2]) % MOD;
16
        f[i][3] = (f[i - 1][3] * (i - 1) % MOD + f[i - 1][0] + 3LL * f[i - 1][1] + 3LL * f[i - 1][2] + f[i - 1][3]) % MOD;
17
    }
18
    int T;
19
    scanf("%d", &T);
20
    while (T--) {
21
        int n;
22
        scanf("%d", &n);
23
        printf("%lld\n", f[n][3]);
24
    }
25
    return 0;
26
}

D. Beautiful Matrix ^队友#

我感觉挺难的，我没反应过来就已经被队友秒了，数学题的思路都挺巧的，两次差分转化了一下，思路就会变清晰了。

1
#include <iostream>
2

3
using namespace std;
4
typedef long long LL;
5
const int MOD = 998244353;
6

7
LL power(LL n, LL p) {
8
    LL res = 1, base = n;
9
    while (p) {
10
        if (p & 1) res = res * base % MOD;
11
        base = base * base % MOD;
12
        p >>= 1;
13
    }
14
    return res;
15
}
16

17
int main() {
18
    LL n, m;
19
    cin >> n >> m;
20
    LL a = 1, b = 1;
21
    for (int i = 1; i <= m; ++i) {
22
        a = a * (((n - 1) * n + m - i + 1) % MOD) % MOD;
23
        b = b * i % MOD;
24
    }
25
    cout << a * power(b, MOD - 2) % MOD << endl;
26
    return 0;
27
}

G. Turn around ^补#

学到了广义矩阵，这道题用 max 和加法替代了原来的加法和乘法，这个规则下的矩阵乘法依然满足结合律，之后开了线段树维护每个位置的转移矩阵。

又被边界卡了qwq，因为全是 L 的时候没有一个 R 把矩阵的 a_{2, 1} 变成 -∞，然后就出错了。

1
#include <iostream>
2

3
using namespace std;
4

5
struct mat {
6
    int a[2][2] = {};
7

8
    int res() {
9
        return max(0, a[1][0]);
10
    }
11
};
12

13
mat operator * (mat a, mat b) {
14
    mat c = {{{-0x3f3f3f3f, -0x3f3f3f3f}, {-0x3f3f3f3f, -0x3f3f3f3f}}};
15
    for (int k = 0; k < 2; ++k) {
16
        for (int i = 0; i < 2; ++i) {
17
            for (int j = 0; j < 2; ++j) {
18
                c.a[i][j] = max(c.a[i][j], a.a[i][k] + b.a[k][j]);
19
            }
20
        }
21
    }
22
    return c;
23
}
24
const int N = 200010;
25
const mat L = {{{1, -0x3f3f3f3f}, {0, 0}}}, R = {{{0, -0x3f3f3f3f}, {-0x3f3f3f3f, 1}}};
26

27
mat tr[N * 4];
28
char s[N];
29

30
void pushup(int u) {
31
    tr[u] = tr[u << 1] * tr[u << 1 | 1];
32
}
33

34
void init(int u, int l, int r) {
35
    if (l == r) tr[u] = s[l] == 'L' ? L : R;
36
    else {
37
        int mid = l + r >> 1;
38
        init(u << 1, l, mid), init(u << 1 | 1, mid + 1, r);
39
        pushup(u);
40
    }
41
}
42

43
void modify(int u, int l, int r, int p, mat v, int w) {
44
    if (l == r) tr[u] = v;
45
    else {
46
        int mid = l + r >> 1;
47
        if (p <= mid) modify(u << 1, l, mid, p, v, w);
48
        else modify(u << 1 | 1, mid + 1, r, p, v, w);
49
        pushup(u);
50
    }
51
}
52

53
int main() {
54
    int n, m, cnt = 0;
55
    scanf("%d%d%s", &n, &m, s + 1);
56
    init(1, 1, n);
57
    for (int i = 1; i <= n; ++i) {
58
        cnt += s[i] == 'L';
59
    }
60
    while (m--) {
61
        int p;
62
        scanf("%d", &p);
63
        if (s[p] == 'L') {
64
            s[p] = 'R';
65
            cnt--;
66
            modify(1, 1, n, p, R, 0);
67
        }
68
        else {
69
            cnt++;
70
            s[p] = 'L';
71
            modify(1, 1, n, p, L, 1);
72
        }
73
        printf("%d\n", cnt == n ? 0 : tr[1].res());
74
    }
75
    return 0;
76
}

K. Maximum GCD#

这道题是我想的，但是 WA 两次，我是战犯😭

第一次是因为里面的边界没处理好，少算了边界情况；
第二次是因为第一次改了之后判 0 又出问题了。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1000010;
6
int a[N];
7
int tr[N * 4];
8
int suf[N], p[N];
9

10
void init(int u, int l, int r) {
11
    if (l == r) tr[u] = a[l] - a[l - 1];
12
    else {
13
        int mid = l + r >> 1;
14
        init(u << 1, l, mid), init(u << 1 | 1, mid + 1, r);
15
        tr[u] = __gcd(tr[u << 1], tr[u << 1 | 1]);
16
    }
17
}
18

19
int query(int u, int l, int r, int ql, int qr) {
20
    if (ql > qr) return 0;
21
    else if (ql <= l && r <= qr) return tr[u];
22
    else {
23
        int mid = l + r >> 1, res = 0;
24
        if (ql <= mid) res = __gcd(res, query(u << 1, l, mid, ql, qr));
25
        if (qr > mid) res = __gcd(res, query(u << 1 | 1, mid + 1, r, ql, qr));
26
        return res;
27
    }
28
}
29

30
int main() {
31
    int T;
32
    scanf("%d", &T);
33
    while (T--) {
34
        int n;
35
        scanf("%d", &n);
36
        for (int i = 1; i <= n; ++i) {
37
            scanf("%d", &a[i]);
38
        }
39

40
        bool f = true;
41
        for (int i = 1; i <= n; ++i) {
42
            if (a[i] != a[1]) {
43
                f = false;
44
                break;
45
            }
46
        }
47
        if (f) {
48
            printf("0\n");
49
            continue;
50
        }
51

52
        int g = 0, len = 0;
53
        for (int i = n; i; --i) {
54
            int tg = __gcd(g, a[i]);
55
            if (tg < g) {
56
                len++;
57
                suf[len] = g;
58
                p[len] = i + 1;
59
            }
60
            g = tg;
61
        }
62
        g = 0;
63
        init(1, 1, n);
64
        int res = query(1, 1, n, 2, n);
65
        for (int i = 1; i <= n; ++i) {
66
            res = max(res, abs(__gcd(g, query(1, 1, n, i + 1, n))));
67
            for (int j = 1; j <= len; ++j) {
68
                res = max(res, abs(__gcd(g, __gcd(query(1, 1, n, i + 1, p[j] - 1), suf[j]))));
69
                if (i > p[j] - 1) break;
70
            }
71
            g = __gcd(g, a[i]);
72
        }
73
        printf("%d\n", res);
74
    }
75
    return 0;
76
}

L. Minimum Parenthesis String ^队友#

这道水一点，就是一个贪心。

1
#include <iostream>
2
#include <algorithm>
3
#include <cstring>
4

5
using namespace std;
6

7
const int N = 100010;
8
pair<int, int> a[N];
9
int b[N * 2];
10

11
int main() {
12
    int T;
13
    scanf("%d", &T);
14
    while (T--) {
15
        int n, m;
16
        scanf("%d%d", &n, &m);
17
        memset(b, 0, sizeof(int) * (n * 2 + 1));
18
        for (int i = 1; i <= m; ++i) {
19
            scanf("%d%d", &a[i].first, &a[i].second);
20
        }
21
        sort(a + 1, a + m + 1, greater<pair<int, int>>());
22
        int cnt = 0, ls = n * 2 + 1;
23
        for (int i = 1; i <= m; ++i) {
24
            if (a[i].first <= ls && ls <= a[i].second) continue;
25
            else {
26
                b[a[i].first] = 1;
27
                cnt++;
28
                ls = a[i].first;
29
            }
30
        }
31
        if (cnt > n) printf("-1\n");
32
        else {
33
            bool valid = true;
34
            int cur = 0;
35
            cnt = n - cnt;
36
            for (int i = 1; i <= n * 2; ++i) {
37
                if (!b[i] && cnt) b[i] = 1, cnt--;
38
                cur += b[i] ? 1 : -1;
39
                if (cur < 0) {
40
                    valid = false;
41
                    break;
42
                }
43
            }
44
            if (valid) {
45
                for (int i = 1; i <= n * 2; ++i) {
46
                    putchar(b[i] ? '(' : ')');
47
                }
48
                putchar('\n');
49
            }
50
            else {
51
                printf("-1\n");
52
            }
53
        }
54
    }
55
    return 0;
56
}

Star's Blog

B. Base Conversion Master#

C. Stack 队友#

D. Beautiful Matrix 队友#

G. Turn around 补#

K. Maximum GCD#

L. Minimum Parenthesis String 队友#

C. Stack ^队友#

D. Beautiful Matrix ^队友#

G. Turn around ^补#

L. Minimum Parenthesis String ^队友#