1106 Lowest Price in Supply Chain
1. 本题和1090 Highest Price in Supply Chain适成对比，都是先构建一棵树，但本题是求最小层数和个数，链接题是求最大层数和个数。在极值更换和个数更新方面，两道题是一样的，但要注意，如果是求最小，一开始要初始化成最大，求最大，一开始要初始化成最小。
2. 我一开始尝试用链接题的DFS修改来通过这道，发现行不通，原因是DFS只会让层数增大，不可能越增大反而更容易满足，于是改成层次遍历，结点也加上层的属性，就做出来了。
AC代码
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
typedef long long LL;using namespace std;const int maxn = 100010;int n;//结点总数
double initPrice,rate;//出厂价和利率
int endDepth = maxn,deepNum= 0;struct Node{vector<int> children;int layer;
}node[maxn]; bool appear[maxn] = {false};int findRoot(){for(int i=0;i<n;i++){if(!appear[i])return i;}
} void layerOrder(int root){queue<int> que;node[root].layer = 0;que.push(root);while(!que.empty()){int top = que.front();que.pop();int size = node[top].children.size();if(!size){//到了叶子结点了，看能不能替换最小层数 if(node[top].layer<endDepth){endDepth = node[top].layer;deepNum = 1;}else if(node[top].layer==endDepth)deepNum++;}else{for(int i=0;i<size;i++){int childI = node[top].children[i];node[childI].layer = node[top].layer+1;que.push(childI);}}}
}int main(){scanf("%d %lf %lf",&n,&initPrice,&rate); int root,childNum,nodeIdx;for(int i=0;i<n;i++){scanf("%d",&childNum);while(childNum--){scanf("%d",&nodeIdx);appear[nodeIdx] = true;node[i].children.push_back(nodeIdx);}}root = findRoot();layerOrder(root);double hPrice = initPrice*pow(1+rate/100,endDepth);printf("%.4f %d",hPrice,deepNum); return 0;
}相关文章：
积极拥抱.NET Core开源社区
潘正磊在上海的Tech Summit 2018 大会上给我们的.NET Core以及开源情况带来了最新信息。 .Net Core 开源后取得了更加快速的发展，目前越活跃用户高达400万人，每月新增开发者45万，在 GitHub 上的月度增长达到15%。目前有来自超过3,700家企业的…
13_文件的操作模式
私有文件访问测试 package cn.itcast.test;import java.io.ByteArrayOutputStream; import java.io.File; import java.io.FileInputStream;import android.test.AndroidTestCase; import android.util.Log;public class AccessOtherAppPrivateTest extends AndroidTestCase {p…
Vcastr 2.2 flv 网络播放器 参数设置
Vcastr 2.2 flv 网络播放器 参数设置 参数名称参数说明默认值vcastr_file方法2传递影片flv文件地址参数，多个使用|分开空vcastr_title影片标题参数，多个使用|分开，与方法2配合使用空vcastr_xml方法3 传递影片flv文件地址参数，样板…
1094 The Largest Generation
1. 开始测试点1答案错误，上网查了发现是因为用了层次遍历的原因，改成先根遍历，即DFS答案就正确了。启示：BFS不行就试试DFS。 2. 这题也不需要结构体数组，向量数据即可，有几个较为关键的变量 int numOflay…
JS魔法堂：mmDeferred源码剖析
一、前言 avalon.js的影响力愈发强劲，而作为子模块之一的mmDeferred必然成为异步调用模式学习之旅的又一站呢！本文将记录我对mmDeferred的认识，若有纰漏请各位指正，谢谢…
asp vb 插入,更新,删除数据库操作。
记笔记。离开学校，东西都还给老师了，哎。Select Case str Case "insert": sql"select * from ["&tablename&"] where idnull" rs.open sql,conn,1,3 rs.addnew For Each key In request.Form …
第五次作业：四则运算之升级
本次作业要求来源：https://edu.cnblogs.com/campus/gzcc/GZCC-16SE2/homework/2232 我的github地址：https://github.com/yellowjy/study 结对同伴的学号姓名：201606120069 缪国锋 一、基本要求： 生成题目，单个题目最多…
妙用vector:根据第一个不等的元素比较两个序列大小的利器
如下面的代码，可以看到向量容器va和vb的第六个元素是第一个不等的元素，且va[5]>vb[5]，因此输出va>vb时结果应该为1。 int main(){vector<int> va,vb;int a[10] {0,1,2,3,4,6};int b[10] {0,1,2,3,4,5,6,7,8,9};for(int i0;i&l…
四个超好用的优质资源搜索网站，海量优质资源等你发现！
在网上找资源的时候总找不到满意的优质资源？今天小编把办公室大佬珍藏多年的四个超好用优质资源搜索网站分享给你，只要你想找，没有找不到的资源！一、学习资料库学习资料库中有大量的免费学习资料，学习资料涵盖多种学科…
sql server 2008 修改sa密码
问题： 当我们用windows本身验证之后需要修改sa密码，出现这样的错误。 解决方案： 转载于:https://www.cnblogs.com/hcfan/p/4164777.html
Sql Server数据库连接Oracle数据库
Select * From opendatasource(MSDAORA, Data SourceAPPDATA;User IDuname;Passwordpwd)..BYERP.MAT_CLASS APPDATA--连接字符串名称 用户.表名 http://www.cnblogs.com/luqingfei/articles/538005.html转载于:https://www.cnblogs.com/hanwater/archive/2009/12/04/1616864.ht…
普通二叉树、二叉查找树、平衡二叉树常见操作汇总
目录 总览表 普通二叉树 二叉查找树 平衡二叉树 总览表 普通二叉树 struct Node{int data;Node* lchild,rchild; };Node* newNode(int v){Node* node new Node;//申请变量的地址空间node->lchild node->rchild NULL;//新建的结点没有左右孩子node->data v;//…
Java IO系列之字节流拷贝文件性能比较
Java IO 字节流基类 InputStream--输入流， OutPutStream--输出流， 输入流用于读，输出流用于写. 字节流默认一次只读取或输出一个字节。 package jonavin.io;import java.io.BufferedInputStream; import java.io.BufferedOutputStream; impo…
引用 提高开发水平的几项必备技术
很好的一篇文章!!!（偶遇此文，英雄所见略同！） 本文列出了当今计算机软件开发和应用领域最重要十种关键技术排名，如果你想保证你现在以及未来的几年不失业，那么你最好跟上这些技术的发展。虽然你不必对这十种…
移动磁盘由于IO设备错误，要怎样寻回文件
J盘打不开由于IO设备错误，是因为这个I盘的文件系统内部结构损坏导致的。要恢复里面的数据就必须要注意，这个盘不能格式化，否则数据会进一步损坏。具体的恢复方法看正文 工具/软件：流星数据恢复软件 步骤1：先百度搜索并…
1043 Is It a Binary Search Tree
1. 这是二叉查找树BST那节的习题，要做出来这题，需要具备的基础知识有：BST的创建，涉及函数createBST，insertBST，newNode，二叉树的先序遍历、后序遍历。 2. 需要转过来的弯的有： 给定…
运用比较纯的CSS打造很Web2.0的按钮
警告：如果你在使用IE浏览此文，那么请回避一下吧! 什么，你用的还是IE6？你真奥特曼(推荐你去打小怪兽)！ 先上图，所谓有图有真相。 如果您觉得图片上这些按钮不够2.0，那没办法，请回避吧…
Elasticsearch 参考指南（脚本）
脚本 脚本模块使你可以使用脚本来评估自定义表达式，例如，你可以使用脚本将“脚本字段”作为搜索请求的一部分返回，或者为查询评估自定义分数。 默认脚本语言是Painless，附加的lang插件使你可以运行用其他语言编写的脚本࿰…
eclipse如何卸载adt插件
1、选择 Help Install New Software； 2、在Details 面板中, 点击What is already installed? 链接； 3、在Eclipse Installation Details 对话框中，选择Android DDMS和Android Development Tools ，然后点击Uninstall；…
1099 Build A Binary Search Tree
1. 本题给出了树的样子，给出了用来填充的数列，并且告诉是一棵二叉查找树。 2. 先用静态存储的方式将树的框架建立起。然后对数列进行小到大排序，利用BST中序遍历是升序的性质，通过中序遍历将数值填充的树中。 3. 层序输出的时候…
redis4.0.6集群部署（5.0.2版本更新补充）
Redis集群安装4版本需要ruby 5版本不需要ruby就能集群1集群机器分布192.168.1.133 redis1192.168.1.134 redis2192.168.1.135 redis32 免密登录ssh-keygenssh-copy-id 192.168.1.133ssh-copy-id 192.168.1.134ssh-copy-id 192.168.1.1353 关闭防火墙sy…
PHP多图片上传 并检查 加水印 源码
参数说明:$max_file_size : 上传文件大小限制, 单位BYTE$destination_folder : 上传文件路径$watermark : 是否附加水印(1为加水印,其他为不加水印);使用说明:1. 将PHP.INI文件里面的"extensionphp_gd2.dll"一行前面的;号去掉,因为我们要用到GD库;2. 将extension_dir…
C#中的委托和事件 (4)---事件和委托的编译代码
事件和委托的编译代码 这时候，我们不得不注释掉编译错误的行，然后重新进行编译，再借助Reflactor来对 event的声明语句做一探究，看看为什么会发生这样的错误： public event GreetingDelegate MakeGreet; 可以看到&#…
1066 Root of AVL Tree 需再做
1. 这题如果不知道平衡二叉树怎么平衡的(左旋右旋那一套)应该不可能做出吧，那就输出中位数回点血了。 2. 需要具备的基础知识：怎么将结点插入平衡二叉树。 3. 我犯的一个错误：把更新高度的函数直接返回了高度，而不没有修改高度。…
easyui-menu 解决disableItem不能禁用绑定事件的方法
版本：1.4. menu的disableItem方法不能禁用使用onClick方式绑定的事件。 解决思路如下： 重写disableItem方法和enableItem方法。 /*** menu方法扩展* param {Object} jq* param {Object} itemEl*/ $.extend($.fn.menu.methods, {/*** 激活选项࿰…
hadoop无法访问50070端口怎么办？
转载请注明出处：www.oldboyedu.com Hadoop 50070是hdfs的web管理页面，在搭建Hadoop集群环境时，有些大数据开发技术人员会遇到Hadoop 50070端口打不开的情况，引起该问题的原因很多，想要解决这个问题需要从以下方面进行排…
表情的机器自动识别(有图有真相)
这幅图片是我自己用C#编写的表情的机器自动识别。主要是AdaBoost的实现，训练做了几个不同版本：线性、并行和分布式，训练数据集采用的JAFFE。 有朋友问这东西有什么用处，其实主要是为了玩而已了。这是基于Paul Ekman那本著名的《情…
并查集专题练习：好朋友(未完待续)
有空再把题目补上 输入样例1 4 2 1 4 2 3 样例输出1 2 输入样例2 7 5 1 2 2 3 3 1 1 4 5 6 输出样例2 3 解题思路： 1. 这题放在并查集的专题后面，有查找也有合并，需要具备的基础只是是合并和查找的函数要会写(都很简单)。但是读到每…
android Viewpager取消预加载及Fragment方法的学习
1.在使用ViewPager嵌套Fragment的时候，由于VIewPager的几个Adapter的设置来说，都会有一定的预加载。通过设置setOffscreenPageLimit（int number) 来设置预加载的熟练，在V4包中，默认的预加载是1，即使你设置为…
前端Js框架 UI框架汇总 特性 适用范围 选择
身为一个资深后端工程师，面对层出不穷的前端框架，总让人眼花缭乱，做一个综合解析贴，从全局着眼，让我们明白各种前端框架的应用范围，为如何选择前端框架，从不同的维度提供一些线索，做…