2025春训第七场 - Star's Blog

这训练赛怎么越来越水了，C 考场上没做出来，D 调了很久，但是实际上都不怎么算难，剩下的四道就是纯粹的大水题了。

A. 抽牌#

我代码写的比较麻烦，实际上没必要。

答案为 0：已经满足其中一个条件了；
答案为 1：花色相同的牌中，有两个相同或者差 1 或 2；
答案为 2：以上都不满足。

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

5
using namespace std;
6

7
vector<int> t[128];
8

9
int main() {
10
    for (int i = 0; i < 3; ++i) {
11
        char c;
12
        int tmp;
13
        cin >> tmp >> c;
14
        t[c].push_back(tmp);
15
    }
16
    int res = 3;
17
    for (int i = 0; i < 128; ++i) {
18
        if (!t[i].empty()) {
19
            sort(t[i].begin(), t[i].end());
20
            if (t[i].size() == 1) res = min(res, 2);
21
            else if (t[i].size() == 2) {
22
                if (t[i][1] - t[i][0] == 2 || t[i][1] - t[i][0] == 1) res = min(res, 1);
23
                else res = min(res, 2);
24
                if (t[i][0] == t[i][1]) res = min(res, 1);
25
            }
26
            else if (t[i].size() == 3) {
27
                if (t[i][0] + 1 == t[i][1] && t[i][1] + 1 == t[i][2]) {
28
                    res = 0;
29
                    break;
30
                }
31
                else if (t[i][0] == t[i][1] && t[i][1] == t[i][2]) {
32
                    res = 0;
33
                    break;
34
                }
35
                else if (t[i][0] == t[i][1] || t[i][1] == t[i][2]) {
36
                    res = min(res, 1);
37
                }
38
                else if (t[i][1] - t[i][0] == 2 || t[i][1] - t[i][0] == 1 || t[i][2] - t[i][1] == 2 || t[i][2] - t[i][1] == 1) {
39
                    res = min(res, 1);
40
                }
41
            }
42
        }
43
    }
44
    printf("%d\n", res);
45
    return 0;
46
}

B. 区间求和#

直接前缀和 + map/二分就行。

ps：别学我把 int 爆了。

1
#include <iostream>
2
#include <vector>
3
#include <map>
4
#define int long long
5

6
using namespace std;
7

8
map<long long, int> mp;
9

10
signed main() {
11
    long long res = 0;
12
    int n, m;
13
    scanf("%lld%lld", &n, &m);
14
    vector<long long> s(n + 1, 0);
15
    mp[0] = 1;
16
    for (int i = 1; i <= n; ++i) {
17
        scanf("%lld", &s[i]);
18
        s[i] += s[i - 1];
19
        res += mp[s[i] - m];
20
        mp[s[i]] ++;
21
    }
22
    printf("%lld\n", res);
23
    return 0;
24
}

C. 鲁的要塞#

对于一组要塞，他们的的指挥中心的横(纵)坐标必然是他们横(纵)坐标的中位数，个数为偶数的情况任取中间的两个点都是可以的，所以中心的坐标一定在已有的数值中选；暴力枚举已经给出的点横纵坐标自由组合，对每个点分别求距离，排序前缀和更新答案即可。

ps：别学我把 int 爆了。

1
#include <iostream>
2
#include <algorithm>
3
#include <cstring>
4
#define int long long
5

6
using namespace std;
7

8
int p[110][2];
9
int a[110], b[110];
10

11
signed main() {
12
    int n, k;
13
    scanf("%lld%lld", &n, &k);
14
    for (int i = 1; i <= n; ++i) {
15
        scanf("%lld%lld", &p[i][0], &p[i][1]);
16
    }
17
    memset(a, 0x3f, sizeof(a));
18
    for (int i = 1; i <= n; ++i) {
19
        for (int j = 1; j <= n; ++j) {
20
            for (int k = 1; k <= n; ++k) {
21
                b[k] = abs(p[i][0] - p[k][0]) + abs(p[j][1] - p[k][1]);
22
            }
23
            sort(b + 1, b + n + 1);
24
            for (int k = 1; k <= n; ++k) {
25
                b[k] += b[k - 1];
26
                a[k] = min(a[k], b[k]);
27
            }
28
        }
29
    }
30
    for (int i = 1; i <= k; ++i) printf("%lld\n", a[i]);
31
    return 0;
32
}

D. 能源晶体#

这是一道 dp 题。

**关键性质：**题目中的方案数等价于用总长为 n 的长度为 [1, k] 的单调不减的线段右端点对齐覆盖 [1, k] 这个区间的方案数。这么做解除了 k 个位置的限制，并且仍然保持了 k 元组的有序性（这里的线段长包括端点，长度为 l，表示最后 l 个数都 +1）
定义状态： $f_{i, j}$ ，表示目前用了 i 个模块，最后一条线段长度为 j 的方案数，答案显然是 $f_{n, k}$ .
状态转移： $f_{i, j} = \sum_{l = 1}^{j}{f_{i - l, l}}$ ，求和可以在 dp 的过程中用前缀和优化，时间复杂度降到 $O(nk)$ .

1
#include <iostream>
2

3
using namespace std;
4

5
const int MOD = 998244353;
6

7
int f[5010][5010];
8
int n, k;
9

10
int main() {
11
    scanf("%d%d", &n, &k);
12
    for (int i = 1; i <= k; ++i) f[0][i] = 1;
13
    for (int i = 1; i <= n; ++i) {
14
        for (int j = 1; j <= k; ++j) {
15
            if (j <= i) f[i][j] = (f[i][j - 1] + f[i - j][j]) % MOD;
16
            else f[i][j] = f[i][j - 1];
17
        }
18
    }
19
    cout << ((f[n][k] - f[n][k - 1]) % MOD + MOD) % MOD << endl;
20
    return 0;
21
}

E. 资料页数#

鉴定为水题，把脚注的行数捆绑到行里面暴力模拟即可。

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

5
using namespace std;
6

7
const int N = 200010;
8
vector<int> ed[N];
9
int f[N];
10
int n, m, k;
11

12
bool dp(int x, int fa) {
13
    f[x] = 1;
14
    int t = 0;
15
    for (int y : ed[x]) {
16
        if (y == fa) continue;
17
        if (!dp(y, x)) return false;
18
        if (f[y]) t++;
19
        f[x] += f[y];
20
    }
21
    if (t > 2) return false;
22
    else if (t == 2) {
23
        if (f[x] != k) return false;
24
        else f[x] = 0;
25
    }
26
    else {
27
        f[x] %= k;
28
    }
29
    return true;
30
}
31

32
int main() {
33
    scanf("%d%d", &n, &k);
34
    for (int i = 1; i < n * k; ++i) {
35
        int x, y;
36
        scanf("%d%d", &x, &y);
37
        ed[x].push_back(y);
38
        ed[y].push_back(x);
39
    }
40
    if (dp(1, 1)) cout << "Yes" << endl;
41
    else cout << "No" << endl;
42
    return 0;
43
}

F. 再破难关#

代码量略大的水题，把状态压成 16 位二进制数，状态个数一共只有 $2^{16}$ 个，直接 bfs 即可。

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

5
using namespace std;
6

7
queue<int> q;
8

9
int s = 0, t = 0;
10
int f[100000];
11
int g[4][4];
12

13
void to_g(int mask) {
14
    for (int i = 0; i < 16; ++i) {
15
        g[i / 4][i % 4] = mask >> i & 1;
16
    }
17
}
18

19
int to_s() {
20
    int res = 0;
21
    for (int i = 0; i < 4; ++i) {
22
        for (int j = 0; j < 4; ++j) {
23
            res |= g[i][j] << (i * 4 + j);
24
        }
25
    }
26
    return res;
27
}
28

29
int main() {
30
    memset(f, -1, sizeof(f));
31
    int s, t;
32
    for (int i = 0; i < 4; ++i) {
33
        for (int j = 0; j < 4; ++j) {
34
            scanf("%1d", &g[i][j]);
35
        }
36
    }
37
    s = to_s();
38

39
    for (int i = 0; i < 4; ++i) {
40
        for (int j = 0; j < 4; ++j) {
41
            scanf("%1d", &g[i][j]);
42
        }
43
    }
44
    t = to_s();
45

46
    f[s] = 0;
47
    q.push(s);
48
    while (!q.empty()) {
49
        int x = q.front();
50
        q.pop();
51
        if (x == t) {
52
            printf("%d\n", f[x]);
53
            return 0;
54
        }
55
        to_g(x);
56
        for (int i = 0; i < 4; ++i) {
57
            for (int j = 0; j < 4; ++j) {
58
                if (i < 3 && g[i][j] != g[i + 1][j]) {
59
                    swap(g[i][j], g[i + 1][j]);
60
                    int y = to_s();
61
                    if (!(~f[y])) {
62
                        f[y] = f[x] + 1;
63
                        q.push(y);
64
                    }
65
                    swap(g[i][j], g[i + 1][j]);
66
                }
67
                if (j < 3 && g[i][j] != g[i][j + 1]) {
68
                    swap(g[i][j], g[i][j + 1]);
69
                    int y = to_s();
70
                    if (!(~f[y])) {
71
                        f[y] = f[x] + 1;
72
                        q.push(y);
73
                    }
74
                    swap(g[i][j], g[i][j + 1]);
75
                }
76
            }
77
        }
78
    }
79
    return 0;
80
}