题目链接: https://pintia.cn/problem-sets/994805046380707840/problems/994805059118809088
题意: 给定 n 个人, 编号 0~n-1,0 为祖先, 每个人有一个师傅, 每次从师傅传功夫到徒弟时, 功力值会削弱 r, 但可能会出现得道者, 功力翻 n 倍, 计算所有得道者功力值之和.
思路: 因为计算功力值时要从祖先开始逐渐向下计算, 所以我们需要存储每个人的徒弟, 然后从上向下遍历即可, 我这里用的是邻接表实现的, 定义 maxn 个表头结点 head,head[i]其中包括它的第一个徒弟编号 nxt, 翻的倍数, 功力值; 定义 maxn 个表结点, 指向其兄弟结点. 然后用 dfs 从祖先编号 0 开始搜即可, 但我被两个细节点卡了一个多小时, 卡到崩溃 QAQ:1. 输入的 r 是 [0,100] 的值, 还需除 100; 2. 我写代码没带脑子, 在 dfs 函数中用全局变量 tmp 作为指向徒弟的指针, 然后程序一直在那运行错误的结果...
AC 代码:
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=100005;
- struct node{
- int nxt,bg;
- double gl;
- }head[maxn];
- int n,k,tmp,nxt[maxn];
- double z,r,sum;
- void dfs(int p){
- if(head[p].bg)
- sum+=head[p].gl*head[p].bg;
- else{
- int t=head[p].nxt;
- while(t){
- head[t].gl=head[p].gl*r;
- dfs(t);
- t=nxt[t];
- }
- }
- }
- int main(){
- scanf("%d%lf%lf",&n,&z,&r);
- r=1.0-0.01*r;
- head[0].gl=z;
- for(int i=0;i<n;++i){
- scanf("%d",&k);
- if(!k)
- scanf("%d",&head[i].bg);
- else
- while(k--){
- scanf("%d",&tmp);
- nxt[tmp]=head[i].nxt;
- head[i].nxt=tmp;
- }
- }
- dfs(0);
- printf("%lld\n",(long long)sum);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2995159.html