2026寒假集训个人训练赛第五场

前四道应该是 CSP-X 辽宁，都是大水题，后三道是 CSP-J 2024。

A. 字符串数数#

1
#include <iostream>
2

3
using namespace std;
4

5
int t[26];
6

7
int main() {
8
    ios::sync_with_stdio(0);
9
    cin.tie(0), cout.tie(0);
10
    string s;
11
    cin >> s;
12
    for (char c : s) t[c - 'a']++;
13
    for (int i : t) cout << i << endl;
14
    return 0;
15
}

B. 积分#

维护个二维前缀和然后暴力检查即可。

1
#include <iostream>
2

3
using namespace std;
4
typedef long long LL;
5
const int N = 1010;
6
LL a[N][N];
7

8
int main() {
9
    ios::sync_with_stdio(0);
10
    cin.tie(0), cout.tie(0);
11
    int n, m, x, y;
12
    LL res = -1e18;
13
    cin >> n >> m >> x >> y;
14
    for (int i = 1; i <= n; ++i) {
15
        for (int j = 1; j <= m; ++j) {
16
            cin >> a[i][j];
17
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
18
            if (i >= x && j >= x) res = max(res, a[i][j] - a[i - x][j] - a[i][j - x] + a[i - x][j - x]);
19
            if (i >= y && j >= y) res = max(res, a[i][j] - a[i - y][j] - a[i][j - y] + a[i - y][j - y]);
20
        }
21
    }
22
    cout << res << endl;
23
    return 0;
24
}

C. ⼩ L 打⽐赛#

经典的贪心问题，直接右端点排序然后能选择选。

1
#include <iostream>
2
#include <algorithm>
3
using namespace std;
4
typedef long long LL;
5
const int N = 500010;
6
pair<int, int> a[N];
7

8
int main() {
9
    ios::sync_with_stdio(0);
10
    cin.tie(0), cout.tie(0);
11
    int n;
12
    cin >> n;
13
    for (int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second;
14
    sort(a + 1, a + n + 1, [](pair<int, int> a, pair<int, int> b) {
15
        return a.second < b.second;
16
    });
17
    int t = 0;
18
    int r = 0;
19
    for (int i = 1; i <= n; ++i) {
20
        if (a[i].first > r) r = a[i].second, t++;
21
    }
22
    cout << t << endl;
23
    return 0;
24
}

D. 购物#

n 很小，直接暴力所有情况挨个检查。

1
#include <iostream>
2
#include <algorithm>
3
using namespace std;
4
typedef long long LL;
5
const int N = 20;
6
LL a[N][2];
7

8
int main() {
9
    ios::sync_with_stdio(0);
10
    cin.tie(0), cout.tie(0);
11
    int n, res = 0;
12
    LL s;
13
    cin >> n >> s;
14
    for (int i = 0; i < n; ++i) cin >> a[i][0] >> a[i][1];
15
    for (int i = 0; i < (1 << n); ++i) {
16
        LL t = 0;
17
        for (int j = 0; j < n; ++j) {
18
            t += a[j][i >> j & 1];
19
        }
20
        if (s >= t) res++;
21
    }
22
    cout << res << endl;
23
    return 0;
24
}

E. 地图探险#

洛谷

直接暴力模拟即可。

1
#include <iostream>
2
#include <algorithm>
3
using namespace std;
4
typedef long long LL;
5
const int N = 1010;
6
// d=0 代表向东，d=1 代表向南，d=2 代表向西，d=3 代表向北
7
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
8
char a[N][N];
9
bool v[N][N];
10

11
int main() {
12
    ios::sync_with_stdio(0);
13
    cin.tie(0), cout.tie(0);
14
    int T;
15
    cin >> T;
16
    while (T--) {
17
        int n, m, k, x, y, d;
18
        cin >> n >> m >> k >> x >> y >> d;
19
        for (int i = 1; i <= n; ++i) cin >> (a[i] + 1);
20
        int res = 1;
21
        v[x][y] = true;
22
        for (int i = 0; i < k; ++i) {
23
            int tx = x + dx[d], ty = y + dy[d];
24
            if (0 < tx && tx <= n && 0 < ty && ty <= m && a[tx][ty] == '.') {
25
                x = tx, y = ty;
26
                if (!v[x][y]) v[x][y] = true, res++;
27
            }
28
            else d = (d + 1) % 4;
29
        }
30
        for (int i = 1; i <= n; ++i) {
31
            for (int j = 1; j <= m; ++j) v[i][j] = false;
32
        }
33
        cout << res << endl;
34
    }
35
    return 0;
36
}

F. 小木棍#

洛谷

首先要让位数最小，位数最小的前提下保证最高位较小。所以结论是尽可能的选用木棍数量最多的 8，根据余数微调高位。因为余数只有 $0, 1, \dots 6$ 七种，很容易分类讨论，手推或者打表都行。

结论是

当只有 1~6 根的时候，答案分别是 -1, 1, 7, 4, 2, 6
除此之外先尽可能填满 8，填到不能再填，然后做以下微调
- 余数为 6，直接高位补 6
- 余数为 5，直接高位补 2
- 余数为 4，删掉一个 8，高位补 20
- 余数为 3
  - 如果有两个及以上的 8，删掉 2 个 8，高位补 200
  - 否则删掉一个 8 高位补 22
- 余数为 2，直接高位补 1
- 余数为 1，删掉一个 8，高位补 10
- 余数为 0，全填 8

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
        int n;
12
        cin >> n;
13
        if (n < 7) {
14
            if (n <= 1) cout << -1 << endl;
15
            else if (n == 2) cout << 1 << endl;
16
            else if (n == 3) cout << 7 << endl;
17
            else if (n == 4) cout << 4 << endl;
18
            else if (n == 5) cout << 2 << endl;
19
            else cout << 6 << endl;
20
        }
21
        else {
22
            int a = n / 7, b = n % 7;
23
            if (b == 6) cout << 6;
24
            else if (b == 5) cout << 2;
25
            else if (b == 4) cout << 20, a--;
26
            else if (b == 3) {
27
                if (a == 1) cout << 22, a--;
28
                else cout << 200, a -= 2;
29
            }
30
            else if (b == 2) cout << 1;
31
            else if (b == 1) cout << 10, a--;
32
            for (int i = 0; i < a; ++i) cout << 8;
33
            cout << endl;
34
        }
35
    }
36
    return 0;
37
}

G. 接龙^(补)#

洛谷

普及组都冒出来蓝题了，当时感觉怎么算时间复杂度都不对，但是实际上就是一个暴力 + 常数优化。我当时的思路是每一个人的词库都相当于一张图，我用 n 种颜色分别标记每个人图中的边，然后合成一个大的图，模拟 100 轮手动走不同颜色的边，bfs 走相同颜色的边，理论上时间复杂度是对的，但是可惜常数太大被卡了，终于今天在我的不懈努力下终于优化过去了😭（这个代码洛谷还是会被卡，但是时间复杂度的正确性肯定没问题，搜素改成滑动窗口 + 遍历常数应该还能更小，但是不想改了）。

1
#include <iostream>
2
#include <tuple>
3
#include <cstring>
4
#include <vector>
5
#include <algorithm>
6

7
using namespace std;
8

9
const int N = 200010;
10
int f[101][N];
11
int a[N], l[N], r[N];
12
bool vis[N];
13
tuple<int, int, int> q[N * 2];
14
vector<int> values;
15
vector<pair<int, int>> ne[N]; // 颜色 下标
16
int n, k, qq;
17

18
void solve() {
19
    cin >> n >> k >> qq;
20
    values.clear();
21
    for (int i = 1; i <= n; ++i) {
22
        int len;
23
        cin >> len;
24
        l[i] = r[i - 1] + 1, r[i] = r[i - 1] + len;
25
        for (int j = l[i]; j <= r[i]; ++j) {
26
            cin >> a[j];
27
            values.emplace_back(a[j]);
28
        }
29
    }
30
    sort(values.begin(), values.end());
31
    values.erase(unique(values.begin(), values.end()), values.end());
32
    int m = values.size();
33
    for (int i = 1; i <= m; ++i) ne[i].clear();
34
    for (int i = 1; i <= n; ++i) {
35
        for (int j = l[i]; j <= r[i]; ++j) {
36
            a[j] = lower_bound(values.begin(), values.end(), a[j]) - values.begin() + 1;
37
            if (j < r[i]) ne[a[j]].emplace_back(i, j + 1);
38
        }
39
    }
40
    for (int i = 1; i <= 100; ++i) {
41
        for (int j = 1; j <= m; ++j) f[i][j] = 0;
42
    }
43
    f[0][1] = -1;
44
    for (int t = 1; t <= 100; ++t) {
45
        int hh = 0, tt = -1;
46
        for (int i = 1; i <= m; ++i) {
47
            if (f[t - 1][i]) {
48
                if (f[t - 1][i] == -1) {
49
                    for (auto &[c, j] : ne[i]) {
50
                        q[++tt] = {c, 1, j};
51
                    }
52
                }
53
                else {
54
                    for (auto &[c, j] : ne[i]) {
55
                        if (c != f[t - 1][i]) {
56
                            q[++tt] = {c, 1, j};
57
                        }
58
                    }
59
                }
60
            }
61
        }
62
        memset(vis, 0, sizeof(bool) * (r[n] + 1));
63
        while (hh <= tt) {
64
            auto [c, len, x] = q[hh++];
65
            if (f[t][a[x]]) {
66
                if (f[t][a[x]] != c) f[t][a[x]] = -1;
67
            }
68
            else f[t][a[x]] = c;
69
            if (vis[x]) continue;
70
            vis[x] = true;
71
            if (x < r[c] && len + 1 < k) q[++tt] = {c, len + 1, x + 1};
72
        }
73
        // for (int i = 1; i <= 9; ++i) cout << f[t][i] << ' ';
74
        // cout << endl;
75
    }
76
    while (qq--) {
77
        int r, c;
78
        cin >> r >> c;
79
        auto t = lower_bound(values.begin(), values.end(), c);
80
        if (t == values.end() || *t != c) cout << 0 << endl;
81
        else cout << (f[r][t - values.begin() + 1] != 0) << endl;
82
    }
83
}
84

85
int main() {
86
    ios::sync_with_stdio(0);
87
    cin.tie(0), cout.tie(0);
88
    int T;
89
    cin >> T;
90
    while (T--) {
91
        solve();
92
    }
93
    return 0;
94
}

Star's Blog