• 大厂秋招真题【DP】米哈游20230924秋招T2-米小游与魔法少女-奇运

    米哈游20230924秋招T2-米小游与魔法少女-奇运

    题目描述与示例

    题目描述

    米小游都快保底了还没抽到希儿，好生气哦！只能打会活动再拿点水晶。

    米小游和世界第一可爱的魔法少女 TeRiRi 正在打 BOSS，BOSS 的血量为h，当 BOSS 血量小于等于0时，BOSS 死亡。TeRiRi 有一套牌，在一轮中，她会按顺序一张一张的将卡牌打出，套牌中有两种卡牌：

    1. 时来运转：获得x个幸运币。
    2. 幸运一掷：造成x点伤害，并投掷所有幸运币，造成等于所有幸运币掷出的点数之和的伤害。

    幸运币可以等概率的投掷出1∼6之间的点数。 （所以为什么不叫骰子呢？）

    米小游想知道，TeRiRi 的套牌在一轮内击杀 BOSS 的概率。

    输入描述

    第一行输入两个整数n (1≤n≤100)，h (1≤h≤10^9)，分别表示卡牌张数和 BOSS 血量。

    接下来n行，每行首先输入两个整数t (1≤t≤2)，x (1≤x≤10)，t为1表示卡牌为时来运转，t为2表示卡牌为幸运一掷。

    输出描述

    输出一个实数表示答案，你的答案与标准答案的误差不超过10^−4都被认为是正确答案。

    示例一

    输入

    2 5
1 1
2 1

    • 1
    • 2
    • 3

    输出

    0.5

    • 1

    说明

    幸运币掷出4及以上的概率为0.5，再加上1点固定伤害，即可击杀BOSS。

    示例二

    输入

    3 1145
1 4
1 9
1 9

    • 1
    • 2
    • 3
    • 4

    输出

    0

    • 1

    说明

    无论如何都无法击杀BOSS。

    解题思路

    对于固定顺序的套牌，投掷幸运币的数量是固定的。这里要注意的是，由于时来运转之后必须接上幸运一掷才能将幸运币打出造成伤害，所以如果最后的若干张连续的卡牌是时来运转，这些最后获得的幸运币也是无法造成伤害的。

    我们将造成的伤害分为两部分，固定伤害和随机伤害，前者为打出y个幸运币必定造成的z点伤害，后者为y个幸运币掷出点数和的伤害。

    假设整套卡牌一共投掷了y个幸运币，造成的固定伤害为z点，如果想要击杀BOSS，随机伤害必须至少达到h-z点才可以。当然，如果h-z≤0，则必定可以击杀BOSS。

    问题就转换为，投掷出y个幸运币，点数总和超过h-z的概率是多少？

    由于每一个幸运币都是独立的，在掷出第i个幸运币时，其结果是从掷出第i-1个幸运币时得到的各种结果转移得到的，因此我们可以使用动态规划来解决该问题。我们考虑动态规划三部曲：

    1. dp数组的含义是什么？
    • dp数组是一个长度为(y+1)×(h-z+1)的二维矩阵，dp[i][j]表示掷出第i个幸运币时，有多大的概率可以取得和为j的结果，即造成和为j的伤害。
    • 特别地，由于只需要判断伤害之和大于等于h-z的概率，而不用关心具体的分布，dp数组内层的第h-z个元素，即dp[i][h-z]，表示求和大于等于h-z的概率。
    1. 动态转移方程是什么？
    • 由于幸运币掷出点数1-6是等概率的，故对于某一个特定的dp[i-1][j]，在掷出第i个幸运币时，dp[i-1][j]的结果将等概率地转换到dp[i][j+1]，dp[i][j+2]，dp[i][j+3]，dp[i][j+4]，dp[i][j+5]，dp[i][j+6]，即每一个状态都可以取得1/6的转移。
    • 另外，如果j+k之后超过了h-z，则将直接获得(7-k)/6 * dp[i-1][j]的概率。
    for i in range(1, y+1):
    for j in range(i-1, h-z+1):
        for k in range(1, 7):
            if j + k >= h - z:
                dp[i][h-z] += (7-k)/6 * dp[i-1][j]
                break
            else:
                dp[i][j+k] += 1/6 * dp[i-1][j]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    1. dp数组如何初始化？
    • 考虑不投掷任何幸运币的情况，那么只有一种情况，也就是在投掷0个幸运币的时候获得求和为0的概率为恒定1。故初始化dp[0][0] = 1
    dp = [[0] * (h-z+1) for _ in range(y+1)]
dp[0][0] = 1

    • 1
    • 2

    考虑完上述问题后，代码其实呼之欲出了。

    代码

    Python

    # 题目：【DP】米哈游2023秋招-米小游与魔法少女-奇运
# 作者：闭着眼睛学数理化
# 算法：DP
# 代码有看不懂的地方请直接在群上提问


y = 0       # 掷出幸运币的总个数
z = 0       # 全部造成的固定伤害
x_temp = 0  # 时来运转获得的幸运币

n, h = map(int, input().split())
for _ in range(n):
    t, x = map(int, input().split())
    # 时来运转
    if t == 1:
        x_temp += x
    # 幸运一掷
    else:
        y += x_temp
        x_temp = 0
        z += x

# 如果固定伤害已经大于h，直接输出1
if h - z <= 0:
    print(1)
# 否则才需要进行dp过程
else:
    # 初始化dp数组
    # dp[i][j]表示掷出了i个幸运币时，
    # 有多大的概率可以取得和为j的结果，即造成和为j的伤害。
    dp = [[0] * (h-z+1) for _ in range(y+1)]
    dp[0][0] = 1


    # 考虑每一个幸运币
    for i in range(1, y+1):
        # 对于每一个幸运币考虑打出i-1个硬币后的
        # 每一种求和结果的概率
        # 注意，由于已经掷出了i-1个幸运币
        # 那么求和结果至少为i-1，因为每个幸运币点数至少为1点
        # 因此j遍历时起点可以从i-1开始
        for j in range(i-1, h-z+1):
            # 如果求和j尚未在上一次投掷中取得，
            # 则可以直接考虑下一个幸运币
            if dp[i-1][j] == 0:
                break
            # 遍历掷出六种不同点数k的情况，
            # 当前点数则可以取得j+k
            for k in range(1, 7):
                # 如果当前点数j+k超过了击杀所需点数
                # 则更新dp[i][h-z]
                # 为dp[i-1][j]对应的概率乘以(7-k)/6
                if j + k >= h - z:
                    dp[i][h-z] += (7-k)/6 * dp[i-1][j]
                    break
                # 如果当前点数j+k尚未超过击杀所需点数
                # 则其概率由dp[i-1][j]六等分后转移得到
                else:
                    dp[i][j+k] += 1/6 * dp[i-1][j]


    # 输出最后一行的最后一个元素
    # 表示打出第y个幸运币后，造成伤害大于等于h-z点的概率
    print(dp[y][h-z])

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64

    Java

    import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int y = 0;            // 掷出幸运币的总个数
        int z = 0;            // 全部造成的固定伤害
        int x_temp = 0;       // 时来运转获得的幸运币

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int h = scanner.nextInt();

        for (int i = 0; i < n; i++) {
            int t = scanner.nextInt();
            int x = scanner.nextInt();
            // 时来运转
            if (t == 1) {
                x_temp += x;
            }
            // 幸运一掷
            else {
                y += x_temp;
                x_temp = 0;
                z += x;
            }
        }

        // 如果固定伤害已经大于h，直接输出1
        if (h - z < 0) {
            System.out.println("1");
        }
        // 否则才需要进行dp过程
        else {
            // 初始化dp数组
            // dp[i][j]表示掷出了i个幸运币时，
            // 有多大的概率可以取得和为j的结果，即造成和为j的伤害。
            double[][] dp = new double[y + 1][h - z + 1];
            dp[0][0] = 1.0;

            // 考虑每一个幸运币
            for (int i = 1; i <= y; i++) {
                // 对于每一个幸运币考虑打出i-1个硬币后的
                // 每一种求和结果的概率
                // 注意，由于已经掷出了i-1个幸运币
                // 那么求和结果至少为i-1，因为每个幸运币点数至少为1点
                // 因此j遍历时起点可以从i-1开始
                for (int j = i - 1; j <= h - z; j++) {
                    // 如果求和j尚未在上一次投掷中取得，
                    // 则可以直接考虑下一个幸运币
                    if (dp[i - 1][j] == 0) {
                        break;
                    }
                    // 遍历掷出六种不同点数k的情况，
                    // 当前点数则可以取得j+k
                    for (int k = 1; k <= 6; k++) {
                        // 如果当前点数j+k超过了击杀所需点数
                        // 则更新dp[i][h-z]
                        // 为dp[i-1][j]对应的概率乘以(7-k)/6
                        if (j + k >= h - z) {
                            dp[i][h - z] += (7 - k) / 6.0 * dp[i - 1][j];
                            break;
                        }
                        // 如果当前点数j+k尚未超过击杀所需点数
                        // 则其概率由dp[i-1][j]六等分后转移得到
                        else {
                            dp[i][j + k] += 1.0 / 6.0 * dp[i - 1][j];
                        }
                    }
                }
            }

            // 输出最后一行的最后一个元素
            // 表示打出第n个幸运币后，造成伤害大于等于h-z点的概率
            System.out.println(String.format("%.5f", dp[y][h - z]));
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77

    C++

    #include 
#include 
#include 

using namespace std;

int main() {
    int y = 0;            // 掷出幸运币的总个数
    int z = 0;            // 全部造成的固定伤害
    int x_temp = 0;       // 时来运转获得的幸运币

    int n, h;
    cin >> n >> h;
    for (int i = 0; i < n; i++) {
        int t, x;
        cin >> t >> x;
        // 时来运转
        if (t == 1) {
            x_temp += x;
        }
        // 幸运一掷
        else {
            y += x_temp;
            x_temp = 0;
            z += x;
        }
    }

    // 如果固定伤害已经大于h，直接输出1
    if (h - z < 0) {
        cout << fixed << setprecision(10) << 1 << endl;
    }
    // 否则才需要进行dp过程
    else {
        // 初始化dp数组
        // dp[i][j]表示掷出了i个幸运币时，
        // 有多大的概率可以取得和为j的结果，即造成和为j的伤害。
        vector<vector<double>> dp(y + 1, vector<double>(h - z + 1, 0));
        dp[0][0] = 1.0;

        // 考虑每一个幸运币
        for (int i = 1; i <= y; i++) {
            // 对于每一个幸运币考虑打出i-1个硬币后的
            // 每一种求和结果的概率
            // 注意，由于已经掷出了i-1个幸运币
            // 那么求和结果至少为i-1，因为每个幸运币点数至少为1点
            // 因此j遍历时起点可以从i-1开始
            for (int j = i - 1; j <= h - z; j++) {
                // 如果求和j尚未在上一次投掷中取得，
                // 则可以直接考虑下一个幸运币
                if (dp[i - 1][j] == 0) {
                    break;
                }
                // 遍历掷出六种不同点数k的情况，
                // 当前点数则可以取得j+k
                for (int k = 1; k <= 6; k++) {
                    // 如果当前点数j+k超过了击杀所需点数
                    // 则更新dp[i][h-z]
                    // 为dp[i-1][j]对应的概率乘以(7-k)/6
                    if (j + k >= h - z) {
                        dp[i][h - z] += (7 - k) / 6.0 * dp[i - 1][j];
                        break;
                    }
                    // 如果当前点数j+k尚未超过击杀所需点数
                    // 则其概率由dp[i-1][j]六等分后转移得到
                    else {
                        dp[i][j + k] += 1.0 / 6.0 * dp[i - 1][j];
                    }
                }
            }
        }

        // 输出最后一行的最后一个元素
        // 表示打出第n个幸运币后，造成伤害大于等于h-z点的概率
        cout << fixed << setprecision(5) << dp[y][h - z] << endl;
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79

    时空复杂度

    时间复杂度：O(yh)。其中y为投掷出的幸运币的总数，h为BOSS总血量，dp过程需要进行双重循环。

    空间复杂度：O(yh)。dp数组所占空间。如果使用滚动dp，空间复杂度可以降低到O(h)

    华为OD算法/大厂面试高频题算法练习冲刺训练

    • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

    • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

    • 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

    • 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

    • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

    • 可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)

    • 绿色聊天软件戳 od1336了解更多

  • 相关阅读:
    java冒泡排序-正序排列、倒序排列（逻辑思维）《软件编程 从0基础到入门＜全民编程系列＞》
    HTML静态网页作业——澳门英文旅游网站设计与实现HTML+CSS+JavaScript
    MyBatisPlus学习笔记
    Spring 事务(测试)--在这个笔记中记录的是没有添加事务，数据库返回的效果。...
    java健康饮食信息管理系统计算机毕业设计MyBatis+系统+LW文档+源码+调试部署
    IP协议详解
    【VSCode】自动生成Jupyter(ipynb)文件的目录
    NTC温敏电阻温度计算
    Java三大版本及 JVM JDK JRE 及 SDK API
    NodeJS技巧：在循环中管理异步函数的执行次数
  • 原文地址：https://blog.csdn.net/weixin_48157259/article/details/133435019