Peter_Matthew的博客

题解 GPLT L2-020 功夫传人

2025-08-06

本文共386字,大约需要阅读1分钟。

使用 BFS来遍历整棵树,并记录每个节点的深度(即第几代弟子)。若某位得道者在第 d 代,则功力为:
$$Z \times (1 - r/100)^d \times 倍数$$

因此从根节点(祖师爷,编号0)开始做BFS,记录每个节点的深度。如果是得道者,计算其功力,加入总和。最后取整输出所有得道者功力之和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;

int main() {
int N;
double Z, r;
cin >> N >> Z >> r;

vector<vector<int>> tree(N); // 存储师傅到徒弟的关系
vector<bool> isLeaf(N, false); // 标记是否是得道者(即叶子节点)
vector<double> multiplier(N, 1.0); // 得道者的功力倍数
vector<int> depth(N, 0); // 每个节点的深度(代数)

for (int i = 0; i < N; ++i) {
int K;
cin >> K;
if (K == 0) {
isLeaf[i] = true;
double m;
cin >> m;
multiplier[i] = m;
} else {
for (int j = 0; j < K; ++j) {
int child;
cin >> child;
tree[i].push_back(child);
}
}
}

// BFS 遍历整棵树并记录深度
queue<int> q;
q.push(0); // 祖师爷编号为0
depth[0] = 0;

while (!q.empty()) {
int current = q.front();
q.pop();
for (int child : tree[current]) {
depth[child] = depth[current] + 1;
q.push(child);
}
}

// 计算所有得道者的功力
double totalPower = 0.0;
double rate = 1.0 - r / 100.0;

for (int i = 0; i < N; ++i) {
if (isLeaf[i]) {
double power = Z * pow(rate, depth[i]) * multiplier[i];
totalPower += power;
}
}

// 输出功力总值的整数部分
cout << (long long)(totalPower) << endl;

return 0;
}
标签: 题解
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏