本文共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); } } }
queue<int> q; q.push(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; }
|
当前页共有次阅读,条评论。
若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏