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

罚时吃麻了，而且错误都特别蠢，可能是没睡醒吧……

前面四道是 CSP-X 2025 河南，后面两道是从 CSP-J 2025 里面选的。

A. 投票#

签到题，排序，优先队列，set 应该都可以。

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

4
using namespace std;
5

6
const int N = 110;
7
priority_queue<int> q;
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    int n;
13
    cin >> n;
14
    for (int i = 1; i <= n; ++i) {
15
        int t;
16
        cin >> t;
17
        q.emplace(t);
18
    }
19
    int mx = q.top();
20
    while (!q.empty() && q.top() == mx) q.pop();
21
    if (q.empty()) cout << "No" << endl;
22
    else cout << q.top() << endl;
23
    return 0;
24
}

B. 接网线#

按要求模拟即可。

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

4
using namespace std;
5

6
const int N = 1010;
7
int s[8], res[N];
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    string a, b;
13
    cin >> a >> b;
14
    for (int i = 0; i < a.length(); ++i) {
15
        for (int j = 0; j < b.length(); ++j) {
16
            if (a[i] == b[j]) {
17
                s[i] = j;
18
                break;
19
            }
20
        }
21
    }
22
    int n;
23
    cin >> n;
24
    for (int i = 0; i < n; ++i) {
25
        int t;
26
        cin >> t;
27
        res[i / 8 * 8 + s[i % 8]] = t;
28
    }
29
    for (int i = 0; i < n; ++i) cout << res[i] << ' ';
30
    cout << endl;
31
    return 0;
32
}

C. 简单排序题#

也是按要求统计，然后 sort 即可。

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

5
using namespace std;
6

7
const int N = 500010;
8
struct Node {
9
    int val, idx, t;
10
} a[N];
11
map<int, int> mp;
12

13
int main() {
14
    ios::sync_with_stdio(0);
15
    cin.tie(0), cout.tie(0);
16
    int n;
17
    cin >> n;
18
    for (int i = 1; i <= n; ++i) cin >> a[i].val, a[i].idx = i, a[i].t = 0, mp[a[i].val]++;
19
    for (int i = 1; i <= n; ++i) a[i].t = mp[a[i].val];
20
    sort(a + 1, a + n + 1, [](Node a, Node b) {
21
        return a.t == b.t ? a.idx < b.idx : a.t > b.t;
22
    });
23
    for (int i = 1; i <= n; ++i) cout << a[i].val << ' ';
24
    cout << endl;
25
    return 0;
26
}

D. 我要飞得更高#

需要注意题面说的是

前进次数不同或前进次数相同但是存在某一步前进距离不同，则认为两个方案不同。

所以相同步长但是不同火箭算为一个方案，把火箭做一个区间合并，合并完之后用新的做 DP 即可。记合并完了之后火箭数量为 $k$

f_i = \sum_{j = 0}^{k}\sum_{w = \max\left\{0, i - L_j\right\}}^{\max\left\{-1, i - R_j\right\}}{f_w}

做一个前缀和优化内部循环即可。

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

5
using namespace std;
6
typedef long long LL;
7
const int N = 100010, M = 210, MOD = 998244353;
8
LL s[N], f[N];
9
pair<int, int> a[M], b[M];
10
int n, m, k;
11

12
int main() {
13
    ios::sync_with_stdio(0);
14
    cin.tie(0), cout.tie(0);
15
    cin >> n >> m;
16
    for (int i = 1; i <= m; ++i) cin >> a[i].first >> a[i].second;
17
    sort(a + 1, a + m + 1);
18
    for (int i = 1; i <= m; ++i) {
19
        if (!k) b[++k] = a[i];
20
        else {
21
            if (a[i].first <= b[k].second + 1) b[k].second = max(b[k].second, a[i].second);
22
            else b[++k] = a[i];
23
        }
24
    }
25
    f[0] = s[0] = 1;
26
    for (int i = 1; i <= n; ++i) {
27
        for (int j = 1; j <= k; ++j) {
28
            auto &[L, R] = b[j];
29
            if (i - L >= 0) {
30
                f[i] = f[i] + s[i - L] % MOD;
31
                if (i - R > 0) f[i] = (f[i] - s[i - R - 1] + MOD) % MOD;
32
            }
33
        }
34
        s[i] = (s[i - 1] + f[i]) % MOD;
35
    }
36
    cout << f[n] << endl;
37
    return 0;
38
}

E. 拼数#

洛谷

直接把数字取出来排序就行。

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

5
using namespace std;
6

7
int main() {
8
    ios::sync_with_stdio(0);
9
    cin.tie(0), cout.tie(0);
10
    string s;
11
    vector<int> v;
12
    cin >> s;
13
    for (char c : s) if (isdigit(c)) v.emplace_back(c - '0');
14
    sort(v.begin(), v.end(), greater<int>());
15
    for (int i : v) cout << i;
16
    cout << endl;
17
    return 0;
18
}

F. 座位#

洛谷

好像没什么可说的，需要注意先输出列号，再输出行号，我输出反了怀疑自己改错了吃了一发发罚时……

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

4
using namespace std;
5
const int N = 110;
6
int a[N];
7

8
int main() {
9
    ios::sync_with_stdio(0);
10
    cin.tie(0), cout.tie(0);
11
    int n, m, k;
12
    cin >> n >> m;
13
    for (int i = 1; i <= n * m; ++i) cin >> a[i];
14
    k = a[1];
15
    sort(a + 1, a + n * m + 1, greater<int>());
16
    for (int i = 1; i <= n * m; ++i) {
17
        if (a[i] == k) {
18
            k = i;
19
            break;
20
        }
21
    }
22
    int x = (k + n - 1) / n, y = (x & 1) ? k - (x - 1) * n : n - (k - (x - 1) * n) + 1;
23
    cout << x << ' ' << y << endl;
24
    return 0;
25
}

Star's Blog