2011.计算机院.Problem C.寻找宝藏

Bertha 。 2023-07-23 11:54 1阅读 0赞

**题目描述**  
有一棵多叉树T，你在树根处，宝藏在某一叶子节点L。现在你沿着树枝向叶子方向走去，从不回头，如果遇到树叉节点，你等概率地挑选一个分支继续走。请问，在给定T，L的情况下，你有多大概率拿到宝藏？

**输入格式**  
第一行，整数N，M，L(1< N< 1000，0< M< 1000，0< L< N)，分别代表树T上的节点数、树枝的个数，宝藏所在节点。树根为0号结点。  
然后有M行，每行两个整数A，B(0≤ A,B< N)代表从节点A到节点B有一条树枝。可以假设节点A总是更靠近树根。

**输出格式**  
所求的概率，输出四舍五入到6位小数，然后换行。

**输入样例**

6 5 5
    0 1
    1 3
    0 2
    2 4
    2 5

**输出样例**

0.250000

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]

#include<bits/stdc++.h>
    using namespace std;
    int t[1005];
    int dp[1005];
    int main() { 
    	double sum=1;
    	int N,M,L,a,b;
    	cin>>N>>M>>L;
    	memset(t,-1,sizeof(t));
    	memset(dp,0,sizeof(dp));
    	while(M--){ 
    		cin>>a>>b;//a->b
    		t[b]=a;
    		dp[a]++;
    	}
    	while(t[L]!=-1){ 
    		L=t[L];
    		sum*=dp[L];
    	}
    	printf("%lf",1.0/sum);
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20230528/34f000d2a2b24fba85aead5017822904.png

发表评论取消回复

表情：

评论列表（有 0 条评论，1人围观）

还没有评论，来说两句吧...

相关阅读

相关华为OD机试 Python【寻找宝藏】

在横坐标和纵坐标的数位之和不大于 k 的方格中存在黄金（每个方格中仅存在一克黄金），但横坐标和纵坐标之和大于 k 的方格存在危险不可进入。2、在 dfs 函数中，使用栈来...

我不是女神ヾ/ 2024年04月24日 06:11/ 0 赞/ 80 阅读

相关 2011.计算机院.Problem C.寻找宝藏

题目描述有一棵多叉树T，你在树根处，宝藏在某一叶子节点L。现在你沿着树枝向叶子方向走去，从不回头，如果遇到树叉节点，你等概率地挑选一个分支继续走。请问，在给定T，L的情况

Bertha 。/ 2023年07月23日 11:54/ 0 赞/ 2 阅读

相关 2012.计算机院.Problem A.二进制数

题目描述大家都知道，数据在计算机里中存储是以二进制的形式存储的。有一天，小明学了C语言之后，他想知道一个类型为unsigned int 类型的数字，存储在计算机中的

深藏阁楼爱情的钟/ 2023年07月21日 06:19/ 0 赞/ 4 阅读

相关 2013.计算机院.Problem D.最小距离查询

题目描述给定一个由小写字母a到z组成的字符串S，其中第i个字符为S\[i\]（下标从0开始）。你需要完成下面两个操作： INSERT c 其中c是一个待输入的字符

川长思鸟来/ 2023年07月19日 12:12/ 0 赞/ 2 阅读

相关 2016.计算机院.Problem C.寻找i*j=m的个数

问题描述 3\3的矩阵内容。 1 2 3 2 4 6 3 6 9 即a\[i\]\[j\] (1<=i<=n,1<=j<=n)= i \ j。

- 日理万妓/ 2023年07月17日 09:59/ 0 赞/ 2 阅读

相关 2016.计算机院.Problem A.三元组

问题描述给你一个长度为m的数组(数组元素从0到m-1)，如果数组里有a\[i\]+a\[j\]==ak，便称之为三元组。现在给你一个数组，让你求三元组的个数。

川长思鸟来/ 2023年07月17日 09:57/ 0 赞/ 1 阅读

相关 Android健身APP源码 | 寻找C站宝藏

Android健身APP源码 | 寻找C站宝藏 \有奖征文｜寻找C站“宝藏”\ 推荐类型：【下载资源】资源链接： > [一个Android健身APP源码][And

男娘i/ 2022年10月18日 01:40/ 0 赞/ 148 阅读

相关我PICK的Python专栏 | 寻找C站宝藏

> 橡皮擦，一个逗趣的互联网高级网虫夏日来临，CSDN 的新活动也来临，寻找 C 站宝藏专栏，这事我熟，如果非要我从 C 站上万个专栏中，选出 3 个，我会毫不犹豫

川长思鸟来/ 2022年10月17日 05:23/ 0 赞/ 133 阅读

相关 iOS精彩博文选登(持续更新) | 寻找C站“宝藏”

文章目录引言 I、 OCR II、iOS安全 III 蓝牙打印商品价格标签、交易小票 see also iOS精品资源汇总：(

àì夳堔傛蜴生んèń/ 2022年10月17日 01:58/ 0 赞/ 187 阅读

相关让Python学起来更轻松 | 寻找C站宝藏

让Python学起来更轻松 | 寻找C站宝藏为什么学习python 简而言之，python能做网络后端、自动化运维、数据分析、自动化测试、网络爬虫、ERP系统、机

绝地灬酷狼/ 2022年10月05日 03:55/ 0 赞/ 168 阅读