蓝桥杯 2022 国 B 故障

P8804 [蓝桥杯 2022 国 B] 故障 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

在软件或系统开发中，我们会遇到各种各样的故障。为了从故障现象反推故障原因，工程师们会总结一种叫做相关性矩阵的二维表格，来表示故障原因与故障现象之间的关系。比如:

其中每行表示一种故障原因，每一列表示一种故障现象。该矩阵表示故障原因 $A$ 可能产生故障现象 $2$、$3$、$4$，故障原因 $B$ 可能产生故障现象 $1$、$3$。

在实际开发过程中，如果出现了故障原因，工程师就可以根据故障现象，去计算每种故障原因产生的概率，并按照概率大小对故障原因进行排查，以达到快速定位故障原因的目的。

现在，我们假设系统开发中同一时间只会出现一种故障原因, 并且故障原 因引起各故障现象是独立事件。举个例子来说:

假设系统现在发生了故障原因 $A$, 有 $\frac{1}{3}$ 的概率出现故障现象 $2$，有 $\frac{1}{4}$ 的概率出现故障现象 $3$，有 $\frac{1}{2}$ 的概率出现故障现象 $4$。由于 $3$ 种现象是独立发生的，因此有 $\frac{1}{2\times 3\times 4}$ 的概率同时出现故障 $2$、$3$、$4$。

约定若相关性矩阵中没有 x 记号, 则表示该故障原因一定不会产生某故障现象，比如故障原因 $A$，一定不会产生故障现象 $1$。根据历史经验数据，我们统计得到了每一种故障原因出现的概率以及每一种故障原因对应的故障现象产生概率。

现在已知系统出现的故障现象，求问各个故障原因发生的概率。

输入格式

第 $1$ 行：$2$ 个正整数 $N,M,N$ 表示故障原因的个数（编号 $1\dots N)，M$ 表示故障现象的个数（编号 $1\dots M$）。

第 $2$ 行: $N$ 个整数，第 $i$ 个数表示故障原因 $i$ 产生的概率 $P_i$。

第 $3\dots N+2$ 行：每行 $M+1$ 个整数，第 $i+1$ 行第 $j$ 个整数 $P_{ij}$ 表示故障原因 $i$ 出现故障现象 $j$ 的概率（百分比）。

第 $N+3$ 行：$1$ 个正整数 $K$，表示目前出现的故障现象数量。

第 $N+4$ 行：$K$ 个正整数，依次为当前出现的故障现象编号，不会重复。

输出格式

第 $1\dots N$ 行：按概率从高到低输出每种故障原因及其可能的概率，若出现 概率相同则优先输出编号小的故障原因。第 $1$ 个数为故障原因编号, 第 $2$ 个数为故障概率（百分比），保留 $2$ 位小数。

样例 #1

样例输入 #1

3 5
30 20 50
0 50 33 25 0
30 0 35 0 0
0 0 0 25 60
1
3

样例输出 #1

2 56.89
1 43.11
3 0.00

提示

对于所有测试用例，$1\le N\le 40,1\le M\le 20,0\le P_i\le 100,\sum \left(P_i\right)=100$, $0\le P_{ij}\le 100$。

蓝桥杯 2022 国赛 B 组 G 题。

思路

代码