贝壳找房 · 概率论 · 算法编程题
贝壳找房 概率论 n ≤ 10 时限 1 秒 / 256 MB

题目描述

牛牛要参加一场程序猿世界杯，一共有 2^n 名选手参加比赛，选手们依次编号从 1 到 2^n ，比赛采用单淘汰制，即第一轮 (1,2),(3,4),·s,(2^n-1,2^n) 进行比赛，第一轮的决胜者再与相连的选手进行比赛，每轮都会淘汰一半的选手，进行 n 之后能决出冠军。牛牛的编号为 m ，但是牛牛知道了各个选手与其他选手比赛时的胜率。牛牛想知道他能夺冠的概率是多少呢，牛牛给你各个选手之间若进行比赛时的胜率，请你告诉牛牛他夺冠可能的概率是多少呢

输入输出

输入描述
第一行为两个整数 n,m ，表示进行多少轮比赛，以及牛牛的编号。
接下来有 2^n 行，每行有 2^n 个整数，第 i 行第 j 个元素 P_ij 表示第 i 名选手战胜第 j 名选手的概率。
1≤ n≤ 10,0≤ P_ij≤ 100,P_ii=0,P_ij+P_ji=100
输出描述
输出为一个浮点数表示答案，答案的误差应小于0.000001。

样例共 1 组

样例 1 · 0.41=0.5*0.1*0.1+0.5*0.9*0.9
输入
2 3
0 10 90 90
90 0 10 10
10 90 0 50
10 90 50 0
输出
0.4100000000

算法解析依据充分

考点：概率论

数据规模 n ≤ 10 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 10
  • 元素值域：P_ij ≤ 100（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：概率论

本题切入点

单淘汰赛树形结构，用 DP 求每个选手进入每一轮的概率，逐轮向父节点合并计算夺冠概率。

用期望的线性性质拆解问题，避免枚举全部状态。

思路框架（概率论 通法 · 非本题专属）

  1. 期望的线性性：E(X+Y) = E(X)+E(Y)，即使变量不独立也成立。
  2. 把总期望拆成若干「指示变量」的期望之和，分别求每个事件发生的概率。
  3. 按定义算期望时，用 Σ(取值 × 概率)。
  4. 涉及无穷过程时，利用递推 / 马尔可夫性质列方程解。

实现要点：计数期望时，先算总方案数，再算目标方案数，比值即概率。

复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(1) ~ O(n)

该范式的通法易错点

  • 误以为期望线性性需要独立性。
  • 概率分母（总方案数）统计错。

对照本题

  • 数据规模 n ≤ 10，允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 元素值域最大到 100 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 2 3 / 0 10 90 90 / 90 0 10 10 / 10 90 0 50 / 10 90 50 0 → 输出 0.4100000000

0.41=0.5*0.1*0.1+0.5*0.9*0.9

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：贝壳找房2023届校招算法卷3。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解