L2-020 功夫传人(树的建立和BFS)

简介: L2-020 功夫传人(树的建立和BFS)

描述:


一门武功能否传承久远并被发扬光大,是要看缘分的。一般来说,师傅传授给徒弟的武功总要打个折扣,于是越往后传,弟子们的功夫就越弱…… 直到某一支的某一代突然出现一个天分特别高的弟子(或者是吃到了灵丹、挖到了特别的秘笈),会将功夫的威力一下子放大N倍 —— 我们称这种弟子为“得道者”。


这里我们来考察某一位祖师爷门下的徒子徒孙家谱:假设家谱中的每个人只有1位师傅(除了祖师爷没有师傅);每位师傅可以带很多徒弟;并且假设辈分严格有序,即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z,每向下传承一代,就会减弱r%,除非某一代弟子得道。现给出师门谱系关系,要求你算出所有得道者的功力总值。


输入:


输入在第一行给出3个正整数,分别是:

N (<=105)——整个师门的总人数(于是每个人从0到N−1编号,祖师爷的编号为0);

Z——祖师爷的功力值(不一定是整数,但起码是正数);

r ——每传一代功夫所打的折扣百分比值(不超过100的正数)。

接下来有N行,第i行(i=0,⋯,N−1)描述编号为i的人所传的徒弟,格式为:

Ki ID1 ID2 IDKi

Ki 是徒弟的个数,后面跟的是各位徒弟的编号,数字间以空格间隔。

Ki为零表示这是一位得道者,这时后面跟的一个数字表示其武功被放大的倍数。

输出:

在一行中输出所有得道者的功力总值,只保留其整数部分。题目保证输入和正确的输出都不超过1010;


思路:树的建立和BFS,在题目中树根已经给出,就是祖师爷,借助队列实现BFS,但要注意n==1的情况


#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll maxx = 1e18;
const int N = 1e5+100;
const int pp = 1e4;
const double eps = 1e-8;
struct node{
  vector<int>ve;//存子节点 
  bool flag;//记录是否为得道者 
  double k;//在得道者中记录放大倍数,非得道者中记录徒弟个数 
  double sum;//记录功力值 
}a[N],p; 
int n,cnt,ks,son;//n 总人数 //cnt Ki  //ks 放大倍数 //son 子结点编号   
double z,ss,r,sums;//z 祖师爷功力值 //ss 缩小倍数 // r减弱百分比 //sums 得道者的功力总值 
queue<node>qu;//队列 
int main()
{
  cin>>n>>z>>r;
  if(n==1)
  {
    cin>>cnt>>ks;
    if(cnt==0) 
      cout<<ks*z;
    else
      cout<<"0";
    return 0;
  }//特判 n=1的情况,注意祖师爷本身为得道者的情况 
  ss=(100-r)/100;//算出缩小倍数 
  a[0].sum=z;//存入祖师爷的功力值 
  for(int i=0;i<n;i++)
  {
    cin>>cnt;
    if(cnt==0) 
    {
      cin>>ks;
      a[i].flag=1;
      a[i].k=ks;
    }//得道者做好标记,记录放大倍数(得道者都是叶节点) 
    else
    {
      for(int j=1;j<=cnt;j++)
      {
        cin>>son;
        a[i].ve.push_back(son); 
      }
      a[i].k=cnt;
    }//非得道者记录子节点并且记录子节点总数 
  }
  qu.push(a[0]);//放入根节点 
  while(!qu.empty())
  {
    p=qu.front();
    qu.pop();//取出队首元素 
    if(p.flag==1)
    {
      sums+=p.sum;
    }//得道者加上功力值 
    else
    { 
      for(int i=0;i<p.k;i++)
      {
        if(a[p.ve[i]].flag==1)
        {
          a[p.ve[i]].sum=p.sum*a[p.ve[i]].k*ss;//得道者的功力值一定是衰减后再放大的,注意不要漏掉放大倍数
        }
        else
        {
          a[p.ve[i]].sum=p.sum*ss;
        }
        qu.push(a[p.ve[i]]);
      }
    }//非得道者算出子节点的功力值放入队列,两个注意点 1.vector的下标从 0 开始 2. 先计算出子节点的功力值再压入队列,顺序反了计算无效 
  }
  cout<<(int)sums;//输出功力总值的整数部分 
  return 0; 
}

反思

1.注意得道者的功力值放大前也要衰减,注意细节

2.注意vector的下标从 0 开始,注意细节

3.注意先计算出功力值再进入队列,否则计算无效,注意细节;

4.注意特判 n==1 的情况,注意细节


目录
相关文章
|
资源调度 JavaScript IDE
使用Vue3+TS重构百星websocket插件(上)
使用Vue3+TS重构百星websocket插件(上)
使用Vue3+TS重构百星websocket插件(上)
|
SQL 缓存 PHP
PHP技术探究:优化数据库查询效率的实用方法
本文将深入探讨PHP中优化数据库查询效率的实用方法,包括索引优化、SQL语句优化以及缓存机制的应用。通过合理的优化策略和技巧,可以显著提升系统性能,提高用户体验,是PHP开发者不容忽视的重要议题。
|
安全 IDE Java
淘宝短视频流工程重构(下):实践篇-2
淘宝短视频流工程重构(下):实践篇
173 8
|
存储 消息中间件 算法
一文读懂 Paxos 算法
一文读懂 Paxos 算法
827 0
一文读懂 Paxos 算法
|
前端开发
简单几行代码CSS实现网页自动打文字效果
简单几行代码CSS实现网页自动打文字效果
140 1
简单几行代码CSS实现网页自动打文字效果
|
存储 关系型数据库 MySQL
存储成本最高降至原来的5%,PolarDB分布式冷数据归档的业务实践
国内某家兼具投资理财、文化旅游、票务为一体的大型综合型集团公司,2015年成立至今,由于业务高速发展,业务数据增长非常快,数据库系统屡次不堪重负。该公司数据库运维总监介绍,他们目前业务压力比较大的是票务和订单系统,他们的平台每天新增几千万的订单数据,订单的数据来自于各个终端,近几年每个月以300G的数据规模在高速增长,由于数据不断增加,数据库系统迄今为止迭代过了3次。
|
关系型数据库 MySQL Unix
Linux 目录结构简介
Linux 目录结构简介
136 0
|
Java Linux Spring
centos7系统运行、停止java程序常用命令,springboot打包运行
centos7系统运行、停止java程序常用命令,springboot打包运行
1434 0
centos7系统运行、停止java程序常用命令,springboot打包运行
|
程序员 项目管理 开发工具
gitt开源项目的意义,公司为什么会对在gitt上有开源项目的人更大机会
gitt开源项目的意义,公司为什么会对在gitt上有开源项目的人更大机会
189 0
|
前端开发 容器
奇思妙想 CSS 3D 动画 | 仅使用 CSS 能制作出多惊艳的动画? (上)
奇思妙想 CSS 3D 动画 | 仅使用 CSS 能制作出多惊艳的动画? (上)
587 0
奇思妙想 CSS 3D 动画 | 仅使用 CSS 能制作出多惊艳的动画? (上)