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

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

A. 评奖#

简单模拟。

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

4
using namespace std;
5

6
const int N = 100010;
7

8
int a[N], b[N], c[N];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    int n;
14
    cin >> n;
15
    for (int i = 1; i <= n; ++i) cin >> a[i];
16
    for (int i = 1; i <= n; ++i) cin >> b[i];
17
    for (int i = 1; i <= n; ++i) cin >> c[i];
18
    int t1 = 0, t2 = 0;
19
    for (int i = 1; i <= n; ++i) {
20
        int t[] = {a[i], b[i], c[i]};
21
        sort(t, t + 3);
22
        if (t[0] == 100) t1++;
23
        else if (t[0] >= 90 && t[1] >= 95) t2++;
24
    }
25
    cout << t1 << ' ' << t2 << endl;
26
    return 0;
27
}

B. IOI 串#

洛谷

$n^2$ 枚举分隔点即可。

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

4
using namespace std;
5

6
const int N = 5010;
7
int pre[N];
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    string s;
13
    cin >> s;
14
    s = " " + s;
15
    for (int i = 1; i < s.length(); ++i) {
16
        pre[i] = pre[i - 1] + (s[i] == 'O');
17
    }
18
    int res = s.length();
19
    for (int i = 1; i < s.length(); ++i) {
20
        for (int j = i + 2; j < s.length(); ++j) {
21
            res = min(res, pre[i] + pre[s.length() - 1] - pre[j - 1] + (j - i - 1) - (pre[j - 1] - pre[i]));
22
        }
23
    }
24
    cout << res << endl;
25
    return 0;
26
}

C. 能量水晶#

洛谷

NOTE
我简直是🐷，做红温了，吃了 5 发罚时。我从一开始就把堆的大小限制成了 $k$ （应该限制成 $m$ ），后来检查的时候都没发现。我一开始写的二分，我就怀疑二分不行，又重构成暴力，最后做完剩下三道了检查了半天才猛然发现，我堆的大小限制错了。

注意到 $a_i$ 很小，可以枚举一个最大值把所有的小行星的水晶全拆的不小大于这个值，然后选最后 $k$ 个，所有情况取一个 max 即可。如果 $a_i$ 变大了同样可以通过二分找到这个值。

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

6
using namespace std;
7

8
const int N = 2010;
9

10
int a[N], b[N], c[N];
11
int n, m, k;
12

13
int check(int mid) {
14
    int res = 0;
15
    memcpy(c, b, sizeof(b));
16
    priority_queue<int, vector<int>, greater<int>> q;
17
    for (int i = 1; i <= m; ++i) {
18
        if (b[i] <= mid) {
19
            q.emplace(b[i]);
20
        }
21
        else {
22
            while (b[i] > mid && (q.size() < m || q.top() < min(b[i] - mid, mid))) {
23
                if (q.size() == m) q.pop();
24
                q.emplace(min(b[i] - mid, mid));
25
                b[i] -= min(b[i] - mid, mid);
26
            }
27
            q.emplace(b[i]);
28
        }
29
    }
30
    int r = 0;
31
    while (q.size() > m) q.pop();
32
    for (int i = 0; i < k; ++i) {
33
        if (q.empty()) break;
34
        r += q.top();
35
        q.pop();
36
    }
37
    memcpy(b, c, sizeof(b));
38
    return r;
39
}
40

41
int main() {
42
    ios::sync_with_stdio(0);
43
    cin.tie(0), cout.tie(0);
44
    cin >> n >> m >> k;
45
    if (k == 0) {
46
        cout << 0 << endl;
47
        return 0;
48
    }
49
    for (int i = 1; i <= n; ++i) cin >> a[i];
50
    sort(a + 1, a + n + 1);
51
    for (int i = 1; i <= m; ++i) {
52
        b[i] = n - m + i >= 1 ? a[n - m + i] : 0;
53
    }
54
    int res = 0;
55
    for (int l = 0; l <= 2000; ++l) {
56
        res = max(res, check(l));
57
    }
58
    cout << res << endl;
59
    return 0;
60
}

D. 勇者斗恶龙#

洛谷

不难发现任何一个勇者想要和两边都不一样至多只会提升 2 次，所以就可以做线性 dp 了，维护第 $i$ 个勇者提升 $j (j \le 2)$ 时前 $i$ 个勇者不冲突的最少代价。

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

4
using namespace std;
5

6
typedef long long LL;
7
const int N = 200010;
8
LL f[N][3];
9
int a[N], b[N];
10

11

12
int main() {
13
    ios::sync_with_stdio(0);
14
    cin.tie(0), cout.tie(0);
15
    int n;
16
    cin >> n;
17
    a[0] = -123123;
18
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
19
    memset(f, 0x3f, sizeof(f));
20
    f[0][0] = f[0][1] = f[0][2] = 0;
21
    for (int i = 1; i <= n; ++i) {
22
        for (int j = 0; j < 3; ++j) {
23
            for (int k = 0; k < 3; ++k) {
24
                if (a[i - 1] + k != a[i] + j) {
25
                    f[i][j] = min(f[i][j], f[i - 1][k] + b[i] * j);
26
                }
27
            }
28
        }
29
    }
30
    cout << min(f[n][1], min(f[n][2], f[n][0])) << endl;
31
    return 0;
32
}

E. 异或和#

洛谷

容易证明贪心是对的，从左往右扫一遍，假设现在扫到了 $i$ ，如果 $[1, i]$ 的后缀异或和里面有一个是 $k$ 就直接选掉一定不劣。这个后缀可以用 set + 懒标记维护。

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

4
using namespace std;
5

6
typedef long long LL;
7
set<LL> s;
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    int n;
13
    LL k, cur = 0, res = 0;
14
    cin >> n >> k;
15
    s.insert(0);
16
    for (int i = 1; i <= n; ++i) {
17
        LL t;
18
        cin >> t;
19
        if (s.find(cur ^ t ^ k) != s.end()) {
20
            res++;
21
            s.clear();
22
            s.insert(0);
23
            cur = 0;
24
            // cout << i << " ";
25
        }
26
        else {
27
            cur ^= t;
28
            s.insert(cur);
29
        }
30
    }
31
    cout << res << endl;
32
    return 0;
33
}

F. 多边形#

洛谷

如果将 $m$ 根从小到大排序，他的条件等价为

m \ge 3\ \land\ \sum_{i = 1}^{m - 1}{l_i} > l_m

先从小到大排序，用 dp 维护 $f_{i, j, k}$ : 前 $i$ 根里面选了 $k$ 根，且长度和为 $j$ 的方案数。由于单根长度最大只有 5000，所以太大的 $j$ 直接归到 5001 里面即可；我们只关注是否够三根，所以太大的 $k$ 全部归到 2 里面即可。现在时间复杂度是 $O(n \cdot \max{a_i})$ ，可以过了。但是 UPC 的 oj 限制内存 128MB，可能会爆掉，开个滚动数组优化一下即可。

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

5
using namespace std;
6

7
typedef long long LL;
8
const int N = 5010, MOD = 998244353;
9

10
int a[N];
11
LL f[2][N * 2][3];
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) {
19
        cin >> a[i];
20
    }
21
    sort(a + 1, a + n + 1);
22
    LL res = 0;
23
    f[0][0][0] = 1;
24
    for (int i = 1; i <= n; ++i) {
25
        for (int j = a[i] + 1; j <= 5001; ++j) {
26
            res = (res + f[0][j][2]) % MOD;
27
        }
28
        memset(f[1], 0, sizeof(f[1]));
29
        for (int k = 0; k < 3; ++k) {
30
            for (int j = 0; j <= 5001; ++j) {
31
                auto &t = f[1][min(j + a[i], 5001)][min(k + 1, 2)];
32
                t = (t + f[0][j][k]) % MOD;
33
                f[1][j][k] = (f[1][j][k] + f[0][j][k]) % MOD;
34
                // if (j < 10) cout << f[1][j][k] << ' ';
35
            }
36
            // cout << endl;
37
        }
38
        // cout << endl;
39
        swap(f[0], f[1]);
40
    }
41
    cout << res << endl;
42
    return 0;
43
}

Star's Blog

A. 评奖#

B. IOI 串#

C. 能量水晶#

D. 勇者斗恶龙#

E. 异或和#

F. 多边形#