2025春训第六场 - Star's Blog

感觉这次做的还行，主要还是简单题多了一点。数学题赛后被 GPT 秒了，而我追着 GPT 问了半天……

A. 魔法石#

签到题，但是有点绕（我就被坑了）。有解的条件是三个数都相等或者两个数相等，另一个比这两个小；前者直接输出三个相等的，后者输出一个较大的和两个较小的即可。

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

4
using namespace std;
5

6
int main() {
7
    long long a[3];
8
    scanf("%lld%lld%lld", &a[0], &a[1], &a[2]);
9
    sort(a, a + 3);
10
    if (a[0] != a[1] && a[1] != a[2]) printf("NO\n");
11
    else if (a[1] < a[2]) printf("NO\n");
12
    else printf("YES\n%lld %lld %lld\n", a[1], a[0], a[0]);
13
    return 0;
14
}

B. 回文立方数#

直接枚举 $i \in [1, \lfloor \sqrt[3]{N} \rfloor]$ ，验证 i³ 是否回文，找最大的即可。

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

4
using namespace std;
5

6
bool check(long long t) {
7
    string s = to_string(t);
8
    for (int i = 0; i < s.length(); ++i) {
9
        if (s[i] != s[s.length() - i - 1]) return false;
10
    }
11
    return true;
12
}
13

14
int main() {
15
    long long n, t = 0;
16
    cin >> n;
17
    for (int i = 1; (long long)i * i * i <= n; ++i) {
18
        if (check((long long)i * i * i)) {
19
            t = (long long)i * i * i;
20
        }
21
    }
22
    printf("%lld\n", t);
23
    return 0;
24
}

C. gcd#

还没问明白 GPT，但是强迫症趋势我必须在第七场前发第六场，所以先🐦一下。

这是事后不知道什么原理过了的代码，似乎要求 a 是 b - a 的倍数而且和 b - a 二进制位不重叠。

1
#include <iostream>
2

3
using namespace std;
4

5
int main(){
6
    int n;
7
    cin >> n;
8
    long long ans = 0;
9
    for (int d = 1; d <= n; d++){
10
        for (int a = d; a + d <= n; a += d) {
11
            if ((a ^ (a + d)) == d) {
12
                ans++;
13
            }
14
        }
15
    }
16
    cout << ans << endl;
17
    return 0;
18
}

E. 摘Galo#

类似树形背包问题，树形dp回溯的时候用孩子的 f 数组更新父亲的 f 数组，最后父亲的 $f_1 = min\{f_1, w\}$ ，注意优化常数，容易被卡成 TLE。

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

5
using namespace std;
6

7
const int N = 100010;
8

9
int head[N], ne[N], ver[N], tot;
10
int w[N];
11
vector<long long> f[N];
12
int cnt[N];
13
int n, k;
14

15
void add(int x, int y) {
16
    ver[++tot] = y;
17
    ne[tot] = head[x];
18
    head[x] = tot;
19
}
20

21
void dp(int x) {
22
    cnt[x] = 1;
23
    long long s = 0;
24
    for (int i = head[x]; i; i = ne[i]) {
25
        int y = ver[i];
26
        dp(y);
27
        cnt[x] += cnt[y];
28
        for (int j = min(k + 1, cnt[x]); j; --j) {
29
            for (int l = min(cnt[y], j); l >= 0; --l) {
30
                f[x][j] = max(f[x][j], f[x][j - l] + f[y][l]);
31
            }
32
        }
33
    }
34
    f[x][1] = max(f[x][1], (long long)w[x]);
35
}
36

37
int main() {
38
    scanf("%d%d", &n, &k);
39
    for (int i = 2; i <= n; ++i) {
40
        int f;
41
        scanf("%d%d", &f, &w[i]);
42
        add(f, i);
43
    }
44
    for (int i = 1; i <= n; ++i) {
45
        f[i] = vector<long long>(k + 2, 0);
46
    }
47
    dp(1);
48
    long long res = 0;
49
    for (int i = 0; i <= k + 1; ++i) {
50
        res = max(res, f[1][i]);
51
    }
52
    printf("%lld\n", res);
53
    return 0;
54
}

F. 队列安排#

排序，从小到大排就行。

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

4
using namespace std;
5

6
long long a[100010];
7

8
int main() {
9
    int n;
10
    scanf("%d", &n);
11
    for (int i = 1; i <= n; ++i) {
12
        scanf("%lld", &a[i]);
13
    }
14
    sort(a + 1, a + n + 1);
15
    long long s = 0;
16
    for (int i = 1; i < n; ++i) {
17
        a[i] += a[i - 1];
18
        s += a[i];
19
    }
20
    printf("%lld\n", s);
21
    return 0;
22
}