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

没有牛客的第二天～～

A. 小Biu的骰子#

我刚开始的时候惯性思维的想遍历终点枚举起点，没有考虑到不同起点过来的概率还都得单独算，WA 了好几发之后才发现……

枚举起点会好做特别多。

1
#include <iostream>
2

3
using namespace std;
4
const int N = 1010;
5
int x[N];
6
double f[N], g[N];
7

8
int main() {
9
    int n;
10
    scanf("%d", &n);
11
    for (int i = 1; i <= n; ++i) {
12
        scanf("%d", &x[i]);
13
    }
14
    f[1] = x[1];
15
    g[1] = 1;
16
    for (int i = 1; i < n; ++i) {
17
        int t = min(6, n - i);
18
        for (int j = 1; j <= t; ++j) {
19
            f[i + j] += (f[i] + x[i + j] * g[i]) / t;
20
            g[i + j] += g[i] / t;
21
        }
22
    }
23
    printf("%.15lf\n", f[n]);
24
    return 0;
25
}

B. 小Biu的树#

我试图扭曲子树的定义 WA 了一发，是的，我的子树曾经还能剪枝😇。

很简单的树形dp，回溯的时候维护一个子树大小和一个子树最大值，如果一个点至少有两个孩子就取子树最大值最大的两个孩子更新答案。

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

5
using namespace std;
6
const int N = 100010;
7

8
int head[N], ver[N * 2], ne[N * 2], tot;
9
int a[N], f[N], g[N], n, res = INT_MIN;
10

11
void add(int x, int y) {
12
    ver[++tot] = y;
13
    ne[tot] = head[x];
14
    head[x] = tot;
15
}
16

17
void dfs(int x, int fa) {
18
    f[x] = a[x];
19
    priority_queue<int> q;
20
    int mx = 0;
21
    for (int i = head[x]; i; i = ne[i]) {
22
        int y = ver[i];
23
        if (y == fa) continue;
24
        dfs(y, x);
25
        f[x] += f[y];
26
        q.push(g[y]);
27
        g[x] = max(g[x], g[y]);
28
    }
29
    g[x] = max(g[x], f[x]);
30
    if (q.size() >= 2) {
31
        int t1 = q.top(), t2;
32
        q.pop();
33
        t2 = q.top();
34
        q.pop();
35
        res = max(res, t1 + t2);
36
    }
37
}
38

39
int main() {
40
    scanf("%d", &n);
41
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
42
    for (int i = 1; i < n; ++i) {
43
        int x, y;
44
        scanf("%d%d", &x, &y);
45
        add(x, y), add(y, x);
46
    }
47
    fill(g, g + n + 1, INT_MIN);
48
    dfs(1, 0);
49
    if (res == INT_MIN) printf("Impossible\n");
50
    else printf("%d\n", res);
51
    return 0;
52
}

C. 掰手腕#

直接排序差分在排序，贪心取最小的。

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

4
using namespace std;
5
const int N = 100010;
6

7
int a[N];
8

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

D. 踢石头#

直接模拟就行，每两次移动一定会忽略掉一个石头，直接模拟最多走 2e5 次。

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

4
using namespace std;
5

6
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
7

8
int main() {
9
    int n;
10
    scanf("%d", &n);
11
    for (int i = 1; i <= n; ++i) {
12
        int p, d;
13
        scanf("%d%d", &p, &d);
14
        q.push({p, d});
15
    }
16
    bool f = true;
17
    long long res = 0;
18
    while (!q.empty()) {
19
        auto [p, d] = q.top();
20
        q.pop();
21
        if (f) q.push({p + d, d});
22
        res = p;
23
        f ^= 1;
24
    }
25
    printf("%lld\n", res);
26
    return 0;
27
}

E. 蛋糕 (cake)#

这道题在考验优化常数的能力，主要的点是

不要尝试用 map 和 unordered_map，全都得 TLE；
不要用 printf 一位一位输出，建议用 putchar；
不要尝试 memset，同样会喜提 TLE。

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

5
using namespace std;
6
int res[2000010], sa[2000010], p[10000010];
7
int a, b, g, mark, l;
8

9
int gcd(int a, int b) {
10
    return b ? gcd(b, a % b) : a;
11
}
12

13
int main() {
14
    for (int t = 0; t < 18; ++t) {
15
        scanf("%d%d", &a, &b);
16
        g = gcd(a, b);
17
        a /= g, b /= g;
18
        printf("%d", a / b);
19
        if (a % b != 0) {
20
            a %= b;
21
            putchar('.');
22
            mark = 0, l = 0;
23
            while (a) {
24
                a *= 10;
25
                if (p[a]) {
26
                    mark = p[a];
27
                    break;
28
                }
29
                p[a] = ++l;
30
                res[l] = a / b;
31
                sa[l] = a;
32
                a %= b;
33
            }
34
            if (mark) {
35
                for (int i = 1; i < mark; ++i) {
36
                    putchar(res[i] + 48);
37
                    p[sa[i]] = 0;
38
                }
39
                putchar('(');
40
                for (int i = mark; i <= l; ++i) {
41
                    putchar(res[i] + 48);
42
                    p[sa[i]] = 0;
43
                }
44
                putchar(')');
45
            }
46
            else {
47
                for (int i = 1; i <= l; ++i) {
48
                    putchar(res[i] + 48);
49
                    p[sa[i]] = 0;
50
                }
51
            }
52
        }
53
        putchar('\n');
54
    }
55
    return 0;
56
}

I. 矩阵游戏#

双倍经验: 洛谷

今天上午我一直在犯迷糊，我快把二分图最大匹配的过程都模拟出来了还没想到跑二分图最大匹配……中午越想越不对劲，发现我之前好像做过这个题 (洛谷有两份 22 年 9 月的提交记录)。

其实只需要考虑每一行是否都能抽出来一个不重复的位置，把行标和列标建边跑二分图最大匹配，如果跑出来是 n 就可以，如果不是 n 就不可以。

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

5
using namespace std;
6

7
const int N = 210;
8
vector<int> ed[N];
9
bool vis[N];
10
int match[N];
11

12
bool dfs(int x) {
13
    if (vis[x]) return false;
14
    vis[x] = true;
15
    for (int y : ed[x]) {
16
        if (!match[y] || dfs(match[y])) {
17
            match[y] = x;
18
            return true;
19
        }
20
    }
21
    return false;
22
}
23

24
int main() {
25
    int T;
26
    scanf("%d", &T);
27
    while (T--) {
28
        int n;
29
        scanf("%d", &n);
30
        memset(match, 0, sizeof(int) * (n + 1));
31
        for (int i = 1; i <= n; ++i) ed[i].clear();
32
        for (int i = 1; i <= n; ++i) {
33
            for (int j = 1; j <= n; ++j) {
34
                int t;
35
                scanf("%d", &t);
36
                if (t) ed[i].emplace_back(j);
37
            }
38
        }
39
        int cnt = 0;
40
        for (int i = 1; i <= n; ++i) {
41
            memset(vis, 0, sizeof(bool) * (n + 1));
42
            if (dfs(i)) cnt++;
43
        }
44
        printf(cnt == n ? "Yes\n" : "No\n");
45
    }
46
    return 0;
47
}

J. 时态同步 ^ERROR#

双倍经验: 洛谷

我怀疑数据有问题……我的代码在洛谷过了，在这儿就只有 72.7 分，而且 72.7 的还不止我一个。

这是一个比较朴素的树形dp，反向思维，路径一样，不妨认为是从叶子流向根的，开一个 f 维护答案，一个 g 维护从叶子传到当前点的时间，从子树向根合并的时候以子节点的最长时间为准别的都补成这个时间。

1
#include <iostream>
2

3
using namespace std;
4

5
typedef long long LL;
6
const int N = 500010;
7
int head[N], ne[N * 2], ver[N * 2], t[N * 2], tot;
8
LL f[N], g[N]; // 需要的次数 传到子树根节点的时间
9

10
void add(int x, int y, int z) {
11
    ver[++tot] = y;
12
    ne[tot] = head[x];
13
    head[x] = tot;
14
    t[tot] = z;
15
}
16

17
void dp(int x, int fa) {
18
    LL s = 0;
19
    int cnt = 0;
20
    for (int i = head[x]; i; i = ne[i]) {
21
        int y = ver[i];
22
        if (y == fa) continue;
23
        dp(y, x);
24
        f[x] += f[y];
25
        cnt++;
26
        s += g[y] + t[i];
27
        g[x] = max(g[x], g[y] + t[i]);
28
    }
29
    f[x] += g[x] * cnt - s;
30
}
31

32
int main() {
33
    int n, s;
34
    scanf("%d%d", &n, &s);
35
    for (int i = 1; i < n; ++i) {
36
        int x, y, z;
37
        scanf("%d%d%d", &x, &y, &z);
38
        add(x, y, z), add(y, x, z);
39
    }
40
    dp(s, 0);
41
    printf("%lld\n", f[s]);
42
    return 0;
43
}

Star's Blog