2025年夏季个人训练赛第一场

第一天前面的英文题还是比较简单的，但是后面的中文题一个不会😭

A. Roller Coaster Ride#

签到题

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int n, c, p;
7
    cin >> n >> c >> p;
8
    if (n <= c * p) cout << "yes" << endl;
9
    else cout << "no" << endl;
10
    return 0;
11
}

B. Donut Shop#

跟着题目要求模拟就可以了。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int n, m;
7
    scanf("%d%d", &n, &m);
8
    while (m--) {
9
        char s[2];
10
        int q;
11
        scanf("%s%d", s, &q);
12
        n += (s[0] == '+' ? 1 : -1) * q;
13
    }
14
    printf("%d\n", n);
15
    return 0;
16
}

C. Product Codes#

刚开始数据混乱，但是后来修好重判了。

字符串模拟题，利用类似快读的思想读数字求和，其他字符遇到大写字母就输出大写字母即可。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    ios::sync_with_stdio(0);
7
    cin.tie(0), cout.tie(0);
8
    int T;
9
    cin >> T;
10
    while (T--) {
11
        string s;
12
        long long f = 1, res = 0, val = 0;
13
        cin >> s;
14
        for (char c : s) {
15
            if (isdigit(c)) res = res * 10 + c - 48;
16
            else {
17
                val += res * f;
18
                // cout << res * f << ' ' ;
19
                res = 0;
20
                f = 1;
21
                if (c == '-') f = -1;
22
                else if (isupper(c)) cout << c;
23
            }
24
        }
25
        val += res * f;
26
        cout << val << endl;
27
        if (val == -3000) {
28
            cout << s << endl;
29
            return 0;
30
        }
31
    }
32
    return 0;
33
}

D. Sunny Days#

类似滑动窗口的思想，一个滑动窗口里面不能有两个 P，如果右边进来一个 P，就不断向右挪左端点直到队列里面只有一个 P，对于每个右端点对应的滑动窗口长度取 max 即可。

需要注意：n = 1，只有一个 S 的时候需要特判，我就被坑了。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 500010;
6
int f[N];
7

8
int main() {
9
    int n, res = 0, l = 1, pre = 0;
10
    bool flag = false;
11
    scanf("%d", &n);
12
    for (int i = 1; i <= n; ++i) {
13
        char s[2];
14
        scanf("%s", s);
15
        f[i] = s[0] == 'S';
16
        if (!f[i]) {
17
            if (!flag) {
18
                flag = true;
19
            }
20
            else {
21
                while (f[l++]);
22
            }
23
        }
24
        res = max(res, i - l + 1);
25
    }
26
    printf("%d\n", res - !(flag));
27
    return 0;
28
}

E. Connecting Territories#

本质上其实就是一个简单的二维 dp

f_{i, j} = \min\{f_{i - 1, j - 1}, f_{i - 1, j}, f_{i - 1, j + 1}\} + M_{i, j}

这么开会爆空间，所以开一个滚动数组优化一下即可。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 20010;
6

7
int f[N][2];
8

9
int main() {
10
    int n, m, p;
11
    int res = 0x3f3f3f3f;
12
    scanf("%d%d%d", &n, &m, &p);
13
    f[0][0] = f[0][1] = f[m + 1][0] = f[m + 1][1] = 0x3f3f3f3f;
14
    int t = 0;
15
    for (int i = 1; i <= n; ++i) {
16
        for (int j = 1; j <= m; ++j) {
17
            bool tt = i & 1;
18
            f[j][tt] = t + 1 + min(min(f[j - 1][tt ^ 1], f[j][tt ^ 1]), f[j + 1][tt ^ 1]);
19
            t = (t + 1) % p;
20
        }
21
    }
22
    for (int j = 1; j <= m; ++j) {
23
        res = min(res, f[j][n & 1]);
24
    }
25
    printf("%d\n", res);
26
    return 0;
27
}

F. 情景剧#

感谢 liuxx 佬的支持

可以枚举当每个位置作为最小值时有趣长度的最大值，固定了最小值之后，区间长度变长一定是正提升。

最长区间长度: 可以用单调栈维护，开一个单调递增的单调栈，入栈后他压住的是左侧比他小的第一个位置，顶出去他的是右侧比他小的第一个位置。
区间最大值: 可以用线段树或者st表维护，个人感觉线段树不容易挂所以用了线段树。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 2000010;
6

7
int a[N], l[N], tr[N * 4], st[N], tp;
8

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

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

29
void print(__int128_t n) {
30
    if (n) {
31
        print(n / 10);
32
        printf("%d", n % 10);
33
    }
34
}
35

36
int main() {
37
    int n;
38
    scanf("%d", &n);
39
    for (int i = 1; i <= n; ++i) {
40
        scanf("%d", &a[i]);
41
    }
42
    __int128_t res = 0;
43
    build(1, 1, n);
44
    for (int i = 1; i <= n; ++i) {
45
        while (tp && a[i] <= a[st[tp]]) {
46
            res = max(res, (__int128_t)(i - 1 - l[st[tp]]) * a[st[tp]] * query(1, 1, n, l[st[tp]] + 1, i - 1));
47
            tp--;
48
        }
49
        l[i] = st[tp];
50
        st[++tp] = i;
51
    }
52
    while (tp) {
53
        res = max(res, (__int128_t)(n - l[st[tp]]) * a[st[tp]] * query(1, 1, n, l[st[tp]] + 1, n));
54
        tp--;
55
    }
56
    print(res);
57
    printf("\n");
58
    return 0;
59
}

Star's Blog