2025夏季个人训练赛第三十六场

中午没睡醒，一睁眼发现三点多了，于是在宿舍先把剩下一道题写了，又写了写题解，拷到 U 盘里面了，然后回机房之后发现 U 盘落宿舍了……

A. 婚礼上的小杉#

1
#include <iostream>
2
#include <algorithm>
3
#include <sstream>
4
using namespace std;
5

6
const int N = 1010;
7
pair<int, string> a[N];
8

9
int main() {
10
    string s;
11
    getline(cin, s);
12
    stringstream ss(s);
13
    int i, n = 0;
14
    while (ss >> i) a[++n].first = i;
15
    getline(cin, s);
16
    ss = stringstream(s);
17
    n = 0;
18
    while (ss >> s) a[++n].second = s;
19
    sort(a + 1, a + n + 1);
20
    for (int i = 1; i <= n; ++i) cout << a[i].second << endl;
21
    return 0;
22
}

B. 最佳课题选择#

分组背包。

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

4
using namespace std;
5
typedef long long LL;
6
const int N = 10010;
7
LL f[N];
8

9
LL power(LL n, LL p) {
10
    LL res = 1;
11
    for (int i = 0; i < p; ++i) res *= n;
12
    return res;
13
}
14

15
int main() {
16
    int n, m;
17
    scanf("%d%d", &n, &m);
18
    fill(f + 1, f + n + 1, LLONG_MAX / 2);
19
    for (int i = 1; i <= m; ++i) {
20
        LL a, b;
21
        scanf("%lld%lld", &a, &b);
22
        for (int j = n; j; --j) {
23
            for (int x = 1; x <= j; ++x) {
24
                LL t = a * power(x, b);
25
                f[j] = min(f[j], f[j - x] + t);
26
            }
27
        }
28
    }
29
    printf("%lld\n", f[n]);
30
    return 0;
31
}

C. 武器配备#

最有的方案一定是机枪和盔甲分别排序，然后各抽出一个长度为 n 的子序列，问题转化成了维护这个子序列的最小不满意度。

f_{i, j, k} 表示前 j 个机枪和前 k 个盔甲选了 i 对的最小不满意度，类似最长公共子序列的思路

f_{i, j, k} = \min \{f_{i, j - 1, k} f_{i, j, k - 1}, f_{i - 1, j - 1, k - 1} + (m_j - n_k)^2\}

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

5
using namespace std;
6

7
typedef long long LL;
8
const int N = 90;
9
LL f[N][N][N]; // 前 j 个 a 和前 k 个 b 配了 i 对的最小值
10
LL c[N], d[N];
11

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

D. 圣诞岛的走廊#

典型的 bfs 问题，直接 bfs，第一次搜到终点的距离就是答案，代码其实还有很多可以优化的地方，比如好像不可能往上回，但是无伤大雅了，能过就行。

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

5
using namespace std;
6

7
const int N = 100010;
8
int a[N][2];
9
bool v[N][2];
10

11
int main() {
12
    int n;
13
    scanf("%d", &n);
14
    for (int i = 1; i <= n; ++i) {
15
        scanf("%d%d", &a[i][0], &a[i][1]);
16
    }
17
    queue<tuple<int, int, int>> q;
18
    v[1][0] = true;
19
    q.push({1, 0, 0});
20
    while (!q.empty()) {
21
        auto [x, y, d] = q.front();
22
        q.pop();
23
        if (x == n) {
24
            printf("%d\n", d);
25
            return 0;
26
        }
27
        if (!v[x][y ^ 1] && !a[x][y ^ 1]) v[x][y ^ 1] = true, q.push({x, y ^ 1, d + 1});
28
        if (x > 1 && !v[x - 1][y] && !a[x - 1][y]) v[x - 1][y] = true, q.push({x - 1, y, d + 1});
29
        if (!v[x + 1][y] && !a[x + 1][y]) v[x + 1][y] = true, q.push({x + 1, y, d + 1});
30
    }
31
    printf("Poor\n");
32
    return 0;
33
}

E. 心情很方 (square)#

看似考数学，实则考 int128，根据初中知识，AD’ 长度是 $\frac{a^2}{b}$ ，a 和 b 比较大需要妥善处理，防止溢出。

1
#include <iostream>
2

3
using namespace std;
4

5
typedef long long LL;
6

7
__int128_t gcd(__int128_t a, __int128_t b) {
8
    return b ? gcd(b, a % b) : a;
9
}
10

11
void print(__int128_t a) {
12
    if (a) {
13
        print(a / 10);
14
        putchar(a % 10 + 48);
15
    }
16
}
17

18
int main() {
19
    int T;
20
    scanf("%d", &T);
21
    while (T--) {
22
        __int128_t a, b;
23
        LL c, d;
24
        scanf("%lld%lld", &c, &d);
25
        a = c, b = d;
26
        a *= a;
27
        __int128_t g = gcd(a, b);
28
        __int128_t res = a / g + b / g;
29
        if (!res) putchar('0');
30
        else print(res);
31
        putchar('\n');
32
    }
33
    return 0;
34
}

H. 皇帝的烦恼#

答案一定不小于 $\max{a_i + a_{i + 1}}$ .

如果 n 是偶数这个下界就是答案，因为正好奇数偶数的颜色可以错开；
如果 n 是奇数就错不开了，考虑二分答案，维护从 1 开始填到第 i 个时和 1 的最小冲突和最大冲突，如果最后一个的最小冲突不是 0 就不合法。 $\begin{align} mx_i &= \min \{a_i, a_1 - mn_{i - 1}\}\\ mn_i &= \max \{0, a_i - \left(\left(mid - a_{i - 1}\right) - \left(a_i - mx_i\right)\right)\} \end{align}$

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 20010;
6

7
int a[N], n;
8

9
bool check(int mid) {
10
    int mxt = a[1], mnt = a[1];
11
    for (int i = 2; i <= n; ++i) {
12
        int t1, t2;
13
        t1 = min(a[1] - mnt, a[i]);
14
        t2 = max(0, a[i] - (mid - a[i - 1] - a[1] + mxt));
15
        mxt = t1, mnt = t2;
16
    }
17
    return mnt > 0 ? false : true;
18
}
19

20
int main() {
21
    int l = 0, r = 300000;
22
    scanf("%d", &n);
23
    for (int i = 1; i <= n; ++i) {
24
        scanf("%d", &a[i]);
25
        if (i > 1) l = max(l, a[i] + a[i - 1]);
26
    }
27
    l = max(l, a[1] + a[n]);
28
    if (n == 1) {
29
        printf("%d\n", a[1]);
30
        return 0;
31
    }
32
    while (l < r) {
33
        int mid = l + r >> 1;
34
        if (check(mid)) r = mid;
35
        else l = mid + 1;
36
    }
37
    printf("%d\n", l);
38
    return 0;
39
}

I. GameZ游戏排名系统#

平衡树板子题，被我用线段树打过去了，也可以用 STL 里面的平衡树 __gnu_pbds 写。

关了流同步之后千万不要肌肉记忆的 printf😭，害我吃了一发罚时。

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

6
using namespace std;
7

8
struct Query
9
{
10
    int t, op, val;
11
    string s;
12

13
    Query(const int &t, const int &op, const int &val, const string &s) : t(t), op(op), val(val), s(s) {}
14
};
15
vector<Query> qs;
16
map<string, int> score; // ren -> fen
17
vector<string> person; // fen -> ren
18
vector<pair<int, int>> values;
19
vector<int> tr;
20

21
void modify(int u, int l, int r, int p, int v) {
22
    if (l == r) tr[u] += v;
23
    else {
24
        int mid = l + r >> 1;
25
        if (p <= mid) modify(u << 1, l, mid, p, v);
26
        else modify(u << 1 | 1, mid + 1, r, p, v);
27
        tr[u] = tr[u << 1] + tr[u << 1 | 1];
28
    }
29
}
30

31
int query_sum(int u, int l, int r, int ql, int qr) {
32
    if (ql <= l && r <= qr) return tr[u];
33
    else {
34
        int mid = l + r >> 1;
35
        int res = 0;
36
        if (ql <= mid) res = query_sum(u << 1, l, mid, ql, qr);
37
        if (qr > mid) res += query_sum(u << 1 | 1, mid + 1, r, ql, qr);
38
        return res;
39
    }
40
}
41

42
int query_k(int u, int l, int r, int k) {
43
    if (l == r) return l;
44
    else {
45
        int mid = l + r >> 1;
46
        if (k <= tr[u << 1]) return query_k(u << 1, l, mid, k);
47
        else return query_k(u << 1 | 1, mid + 1, r, k - tr[u << 1]);
48
    }
49
}
50

51
int main() {
52
    ios::sync_with_stdio(0);
53
    cin.tie(0), cout.tie(0);
54
    int T, val;
55
    string s;
56
    cin >> T;
57
    qs.reserve(T);
58
    for (int t = 0; t < T; ++t) {
59
        cin >> s;
60
        if (s[0] == '+') cin >> val, qs.emplace_back(t, 1, -val, s.substr(1)), values.emplace_back(-val, t);
61
        else if (isdigit(s[1])) qs.emplace_back(t, 2, stoi(s.substr(1)), "");
62
        else qs.emplace_back(t, 3, -1, s.substr(1));
63
    }
64
    sort(values.begin(), values.end());
65
    for (auto &[t, a, b, c] : qs) {
66
        if (a == 1) b = lower_bound(values.begin(), values.end(), pair<int, int>(b, t)) - values.begin() + 1;
67
    }
68
    int n = values.size();
69
    tr = vector<int>(n * 4 + 1, 0);
70
    person = vector<string>(n + 1);
71
    for (auto &[_, op, val, s] : qs) {
72
        if (op == 1) {
73
            if (score.find(s) != score.end()) modify(1, 1, n, score[s], -1);
74
            modify(1, 1, n, val, 1);
75
            score[s] = val;
76
            person[val] = s;
77
        }
78
        else if (op == 3) {
79
            cout << query_sum(1, 1, n, 1, score[s]) << endl;
80
        }
81
        else {
82
            int l = val, r = min(val + 9, tr[1]);
83
            for (int i = l; i <= r; ++i) {
84
                cout << person[query_k(1, 1, n, i)] << ' ';
85
            }
86
            cout << endl;
87
        }
88
    }
89
    return 0;
90
}

J. 反质数#

详见进阶指南 140 页，搜前 10 个素数的 30 以内的单调不增幂次构造出来的数，找到满足要求的最小的一个。

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

5
using namespace std;
6
typedef long long LL;
7
int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
8
int n;
9
vector<LL> t;
10

11
void dfs(int x, int pre, LL res) {
12
    if (res > n) return;
13
    if (x == 10) {
14
        t.emplace_back(res);
15
        // cout << res << ' ';
16
        return;
17
    }
18
    LL bs = 1;
19
    for (int i = 0; i <= pre; ++i) {
20
        dfs(x + 1, i, res * bs);
21
        bs *= p[x];
22
        if (res * bs > n) break;
23
    }
24
}
25

26
int main() {
27
    scanf("%d", &n);
28
    dfs(0, 30, 1);
29
    int mx = 0, res = 1;
30
    for (auto i : t) {
31
        int x = i, l = sqrt(i), ct = 1;
32
        for (int j = 2; j <= l; ++j) {
33
            int t = 1;
34
            while (x % j == 0) {
35
                x /= j;
36
                t++;
37
            }
38
            ct *= t;
39
        }
40
        if (x != 1) ct *= 2;
41
        if (ct > mx) res = i, mx = ct;
42
        else if (ct == mx && i < res) res = i;
43
    }
44
    printf("%d\n", res);
45
    return 0;
46
}

Star's Blog