2025年夏季个人训练赛第十四场

A. 公交线路#

按要求模拟即可。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 20;
6
int a[N], b[N];
7

8
int main() {
9
    int n, x, y;
10
    scanf("%d%d%d", &n, &x, &y);
11
    for (int i = 1; i <= n; ++i) {
12
        scanf("%d", &a[i]);
13
    }
14
    int m;
15
    scanf("%d", &m);
16
    for (int i = 1; i <= m; ++i) {
17
        scanf("%d", &b[i]);
18
    }
19
    bool l = true, r = true;
20
    for (int i = 1; i <= m; ++i) {
21
        int p = x + i;
22
        if (p < 0 || p > n) {
23
            r = false;
24
            break;
25
        }
26
        else if (b[i] != a[p]) {
27
            r = false;
28
            break;
29
        }
30
    }
31
    for (int i = 1; i <= m; ++i) {
32
        int p = x - i;
33
        if (p < 0 || p > n) {
34
            l = false;
35
            break;
36
        }
37
        else if (b[i] != a[p]) {
38
            l = false;
39
            break;
40
        }
41
    }
42
    if (l && r) printf("Unsure\n");
43
    else if (!l && !r) {
44
        printf("qwq\n");
45
        return 123;
46
    }
47
    else if (x < y && r || x > y && l) printf("Right\n");
48
    else printf("Wrong\n");
49
    return 0;
50
}

B. 攻防演练#

C. 连锁商店#

2³⁶ 会爆空间和时间，但是 2¹⁸ 正好不会，最多 36 个景点，只有公司出现次数 ≥ 2 的点记录状态才有意义，统计一下出现次数 ≥ 2 的景点拓扑排序 + 状压dp 就可以解决。

记得初始化😭

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <cstring>
5

6
using namespace std;
7

8
const int N = 40;
9

10
int f[N][1 << 18], cnt[N], a[N], b[N], c[N], w[N], deg[N];
11
vector<int> ed[N];
12

13
int main() {
14
    int n, m;
15
    scanf("%d%d", &n, &m);
16
    for (int i = 1; i <= n; ++i) {
17
        scanf("%d", &c[i]);
18
        cnt[c[i]]++;
19
    }
20
    for (int i = 1; i <= n; ++i) {
21
        scanf("%d", &w[i]);
22
    }
23
    for (int i = 1; i <= m; ++i) {
24
        int x, y;
25
        scanf("%d%d", &x, &y);
26
        if (x > y) swap(x, y);
27
        ed[x].push_back(y);
28
        deg[y]++;
29
    }
30

31
    int len = 0;
32
    for (int i = 1; i <= n; ++i) {
33
        if (cnt[i] > 1) a[++len] = i, b[i] = len;
34
    }
35
    queue<int> q;
36
    q.push(1);
37
    memset(f, -0x3f, sizeof(f));
38
    if (b[c[1]]) f[1][1 << (b[c[1]] - 1)] = w[c[1]];
39
    else f[1][0] = w[c[1]];
40
    while (!q.empty()) {
41
        int x = q.front();
42
        q.pop();
43
        for (int y : ed[x]) {
44
            if (b[c[y]])
45
                for (int mask = 0; mask < (1 << len); ++mask) {
46
                    if (mask >> (b[c[y]] - 1) & 1) f[y][mask] = max(f[y][mask], f[x][mask]);
47
                    else f[y][mask | (1 << b[c[y]] - 1)] = max(f[y][mask | (1 << b[c[y]] - 1)], f[x][mask] + w[c[y]]);
48
                }
49
            else
50
                for (int mask = 0; mask < (1 << len); ++mask) {
51
                    f[y][mask] = max(f[y][mask], f[x][mask] + w[c[y]]);
52
                }
53
            if (--deg[y] == 0) q.push(y);
54
        }
55
    }
56
    for (int i = 1; i <= n; ++i) {
57
        int res = 0;
58
        for (int j = 0; j < (1 << len); ++j) {
59
            res = max(res, f[i][j]);
60
        }
61
        printf("%d\n", res);
62
    }
63
    return 0;
64
}

D. 修建道路#

从左到右连成一条链一定是最优的，如果中间跨越了几个村庄，代价就是中间的所有的路取 max，一定不比连成一条链小。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 200010;
6
int a[N];
7

8
int main() {
9
    int n;
10
    long long res = 0;
11
    scanf("%d", &n);
12
    for (int i = 1; i <= n; ++i) {
13
        scanf("%d", &a[i]);
14
    }
15
    for (int i = 2; i <= n; ++i) {
16
        res += max(a[i], a[i - 1]);
17
    }
18
    printf("%lld\n", res);
19
    return 0;
20
}

G. 3G网络#

$r \rarr + \infty$ 了，圆心的距离就能忽略了，所以答案是 $\frac{1}{n}$ .

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int n;
7
    scanf("%d", &n);
8
    printf("%.15f\n", 1.0 / n);
9
    return 0;
10
}

I. 驾驶卡丁车#

一般的大模拟，都挺好实现的。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 60;
6
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
7
char mp[N][N], s[510];
8

9
int main() {
10
    int n, m, x, y;
11
    scanf("%d%d", &n, &m);
12
    for (int i = 0; i <= m + 1; ++i) mp[0][i] = mp[n + 1][i] = '#';
13
    for (int i = 1; i <= n; ++i) {
14
        scanf("%s", mp[i] + 1);
15
        for (int j = 1; j <= n; ++j) {
16
            if (mp[i][j] == '*') {
17
                x = i, y = j;
18
            }
19
        }
20
        mp[i][0] = mp[i][m + 1] = '#';
21
    }
22
    int q, v = 0, d = 0;
23
    scanf("%d%s", &q, s);
24
    for (int i = 0; i < q; ++i) {
25
        if (s[i] == 'L') d = (d + 7) % 8;
26
        else if (s[i] == 'R') d = (d + 1) % 8;
27
        else if (s[i] == 'U') v++;
28
        else if (s[i] == 'D') v = max(v - 1, 0);
29
        else {
30
            cout << "qwq" << endl;
31
            return 123;
32
        }
33
        for (int j = 1; j <= v; ++j) {
34
            if (mp[x + dx[d]][y + dy[d]] == '#' || (d & 1) && mp[x + dx[(d + 7) % 8]][y + dy[(d + 7) % 8]] == '#' && mp[x + dx[(d + 1) % 8]][y + dy[(d + 1) % 8]] == '#') {
35
                v = 0;
36
                printf("Crash! ");
37
                break;
38
            }
39
            else x += dx[d], y += dy[d];
40
        }
41
        printf("%d %d\n", x, y);
42
    }
43
    return 0;
44
}

K. 音乐游戏#

数据有问题，实际上 n 不太准，直接统计 - 的个数就是对的。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 1010;
6

7
int main() {
8
    string s;
9
    int res = 0;
10
    getline(cin, s);
11
    while (getline(cin, s)) {
12
        for (char c : s) if (c == '-') res++;
13
    }
14
    cout << res << endl;
15
    return 0;
16
}

Star's Blog