2025 春训第十场 - Star's Blog

A. 鲁的学生#

大水题，但是我没看到要取模连 WA 两次。

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

4
using namespace std;
5

6
const int MOD = 1000000007;
7

8
int main() {
9
    long long res = 0;
10
    int n;
11
    scanf("%d", &n);
12
    for (int i = 1; i <= n; ++i) {
13
        int t;
14
        scanf("%d", &t);
15
        res += (long long)i * (n - i + 1) % MOD * t % MOD;
16
        res %= MOD;
17
    }
18
    printf("%lld\n", res);
19
    return 0;
20
}

B. 鲁的探险#

n 个点 n 条边，而且每个点都至少有 1 度，显然这张图是基环树（一棵树随便加一条边构成的连通的只有一个环的图）构成森林。所有的点最后都会走到对应连通块的环里，随后绕一圈结束；明白了这点那么做法就很简单了，记点 i 的答案为 $val_i$

划分连通块；
对每个连通块找到环的位置；
对于每个环，环上的点的 $A_i$ 求和赋给这个环上的所有点；
从所有环上的点开始搜索反图，更新其他点的 $val_i$ 。

代码比较恶心，如需参考，请谨慎。

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <cstring>
5
using namespace std;
6

7
const int N = 200010;
8

9
vector<int> ed[N];
10
int pre[N];
11
int a[N], vis[N], tot;
12
int cir[N];
13
long long sum[N];
14
bool mark[N];
15
bool v[N];
16
// 这里我原来是把 val 用作标记数组，然后因为有 val 是 0 但是确实访问过的数据导致不是爆栈就是 t
17
// 发现之后一怒之下开了这个 vvvvv
18
bool vvvvv[N];
19
long long val[N];
20

21
void bfs(int i) {
22
    queue<int> q;
23
    q.push(i);
24
    vis[i] = tot;
25
    while (!q.empty()) {
26
        int x = q.front();
27
        q.pop();
28
        for (int y : ed[x]) {
29
            if (vis[y]) continue;
30
            vis[y] = tot;
31
            q.push(y);
32
        }
33
        if (!vis[pre[x]]) {
34
            vis[pre[x]] = tot;
35
            q.push(pre[x]);
36
        }
37
    }
38
}
39

40
int main() {
41
    int n;
42
    scanf("%d", &n);
43
    for (int i = 1; i <= n; ++i) {
44
        scanf("%d", &a[i]);
45
    }
46
    for (int i = 1; i <= n; ++i) {
47
        scanf("%d", &pre[i]);
48
        ed[pre[i]].push_back(i);
49
    }
50
    for (int i = 1; i <= n; ++i) {
51
        if (!vis[i]) {
52
            tot++;
53
            bfs(i);
54
        }
55
    }
56
    queue<int> q;
57
    for (int i = 1; i <= n; ++i) {
58
        if (!mark[vis[i]]) {
59
            mark[vis[i]] = true;
60
            int x, y;
61
            for (x = i; !v[x]; x = pre[x]) {
62
                v[x] = true;
63
            }
64
            y = x;
65
            do {
66
                cir[y] = vis[i];
67
                sum[vis[i]] += a[y];
68
                y = pre[y];
69
            } while (y != x);
70
        }
71
    }
72
    for (int i = 1; i <= n; ++i) {
73
        if (cir[i]) {
74
            q.push(i);
75
            vvvvv[i] = true;
76
            val[i] = sum[cir[i]];
77
        }
78
    }
79
    while (!q.empty()) {
80
        int x = q.front();
81
        q.pop();
82
        for (int y : ed[x]) {
83
            if (vvvvv[y]) continue;
84
            vvvvv[y] = true;
85
            val[y] = val[x] + a[y];
86
            q.push(y);
87
        }
88
    }
89
    for (int i = 1; i <= n; ++i) {
90
        printf("%lld\n", val[i]);
91
    }
92
    return 0;
93
}

C. 他会输出啥#

我用 python 写的，实际上用 C++ 区别不大，注意别爆 int 就行。

思路是把第二个循环直接用等差数列求和公式算出来，只跑第一层循环时间复杂度是完全够的的。

1
def fun(a, b, c):
2
    if a in range(a, b, c):
3
        t = len(range(a, b, c))
4
        return a * t + c * t * (t - 1) // 2
5
    else:
6
        return 0
7
input()
8
s = input()
9
a, b, c = map(int, s[s.find('(') + 1:s.find(')')].split(','))
10
s = input()
11
d, e, f = s[s.find('(') + 1:s.find(')')].split(',')
12
if d.isalpha() and e.isalpha():
13
    print(sum(fun(i, i, int(f)) for i in range(a, b, c)))
14
elif d.isalpha():
15
    print(sum(fun(i, int(e), int(f)) for i in range(a, b, c)))
16
elif e.isalpha():
17
    print(sum(fun(int(d), i, int(f)) for i in range(a, b, c)))
18
else:
19
    print(sum(fun(int(d), int(e), int(f)) for i in range(a, b, c)))