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

Bertha 。 2023-07-23 11:54 19阅读 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 条评论，19人围观）

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

相关阅读

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

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

喜欢ヅ旅行/ 2024年04月24日 06:11/ 0 赞/ 86 阅读

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

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

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

相关 2011.计算机院.Problem A.反转单词

题目描述给出一句英文句子(只由大小写字母和空格组成，不含标点符号，也不会出现连续的空格),请将其中的所有单词顺序翻转输入格式多组数据，以EOF结束。每行一

阳光穿透心脏的1/2处/ 2023年07月23日 10:59/ 0 赞/ 10 阅读

相关 2012.计算机院.Problem C.二叉排序树

题目描述: 二叉排序树，也称为二叉查找树。可以是一颗空树,也可以是一颗具有如下特性的非空二叉树: 若左子树非空,则左子树上所有节点关键字值均不大于根节点的关键字值;

淡淡的烟草味﹌/ 2023年07月21日 08:43/ 0 赞/ 13 阅读

相关 2012.计算机院.Problem B.矩阵幂

题目描述给你一个n\n的矩阵，求其矩阵的k次幂，即Pk 输入格式第一行，一个整数T（0<T<=10），表示要求矩阵的个数。接下来有T组数据，每组数据格式如

小鱼儿/ 2023年07月21日 06:20/ 0 赞/ 14 阅读

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

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

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

相关 2013.计算机院.Problem C.中序遍历序列

题目描述给出一个序列，判断该序列是不是某二叉搜索树的中序遍历序列，如果是输出"Yes"，否则输出"No"。一颗带权二叉树是一颗二叉搜索树（二叉排序树），当且仅当对于

待我称王封你为后i/ 2023年07月19日 15:29/ 0 赞/ 14 阅读

相关 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 赞/ 14 阅读

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

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

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

相关 2015.计算机院.Problem B.LIST

描述：在该LIST上实现3种操作 1、append x在该LIST末尾添加x，x是32位整数 2、pop删除该LIST末尾的数 3、find i寻找第i个数，

Bertha 。/ 2023年05月28日 14:23/ 0 赞/ 13 阅读