【秋招突围】2024届秋招-米哈游笔试题-第一套

大家好这里是清隆Coding ，一枚热爱算法的程序员

ACM金牌团队️ | 多次AK大厂笔试 ｜ 编程一对一辅导

✨ 本系列打算持续跟新 秋招笔试题

感谢大家的订阅➕ 和 喜欢 和 手里的小花花

✨ 笔试合集传送们 -> 春秋招笔试合集

今晚米哈游的提前批就要开始啦，我们来看看去年秋招米哈游真题卷的难度怎么样

第一题比较简单是个基础的位运算贪心 问题，第二题是一个 概率DP，不太好做，第三题考察的是 计数相关的DP，也是比较难的一类，总体来看这次笔试还是不简单的

米哈游-2023年-秋招(第3场)

01.LYA 的异或游戏

题目描述

LYA 非常喜欢玩游戏，最近她发明了一个新的游戏规则。给定两个长度为 的正整数数组 和 ，每一步可以从其中一个数组中删除一个元素。LYA 的目标是使得游戏结束时，两个数组剩余元素的总和的异或值最大。

现在 LYA 想请你帮忙计算，按照最优策略进行游戏，最后能得到的最大异或值是多少。

输入格式

第一行输入一个正整数 ，表示数组的长度。

第二行输入 个正整数 ，表示数组 的元素。

第三行输入 个正整数 ，表示数组 的元素。

输出格式

输出一个整数，表示按照最优策略进行游戏，最后能得到的最大异或值。

样例输入

3
1 2 3
3 2 1

样例输出

5

样例说明

删除数组 中的元素 ，剩余元素的总和为 ；数组 的元素总和为 。两者的异或值为 。可以证明这是最大的异或值。

数据范围

题解

本题可以使用贪心的思想来解决。我们可以发现，异或运算的一个重要性质是：对于任意两个非负整数 和 ，有 ，当且仅当 和 的二进制表示中至少有一位不同时取等号。

因此，为了使异或值最大，我们希望两个数组剩余元素的总和之差尽可能大，同时要让它们的二进制表示有尽可能多的不同位。

基于这个思路，我们可以先计算出两个数组的元素总和 和 ，然后枚举删除一个元素的所有情况，更新异或值的最大值即可。

具体地，对于数组 中的每个元素 ，删除它后两个数组的元素总和之差为 ，异或值为 ；对于数组 中的每个元素 ，删除它后两个数组的元素总和之差为 ，异或值为 。我们取所有情况中的最大值作为答案。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))




sum_a = sum(a)
sum_b = sum(b)




ans = 0
for i in range(n):
    ans = max(ans, sum_b ^ (sum_a - a[i]))
    ans = max(ans, sum_a ^ (sum_b - b[i]))




print(ans)

• Java

import java.io.*;
import java.util.*;




public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(str[i]);
        }
        str = br.readLine().split(" ");
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = Integer.parseInt(str[i]);
        }
        
        int sum_a = 0, sum_b = 0;
        for (int i = 0; i < n; i++) {
            sum_a += a[i];
            sum_b += b[i];
        }
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, sum_b ^ (sum_a - a[i]));
            ans = Math.max(ans, sum_a ^ (sum_b - b[i]));
        }
        
        System.out.println(ans);
    }
}

• Cpp

#include <iostream>
#include <vector>
using namespace std;




int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    int sum_a = 0, sum_b = 0;
    for (int i = 0; i < n; i++) {
        sum_a += a[i];
        sum_b += b[i];
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, sum_b ^ (sum_a - a[i]));
        ans = max(ans, sum_a ^ (sum_b - b[i]));
    }
    
    cout << ans << endl;
    
    return 0;
}

02. BOOS挑战

问题描述

LYA 是一位勇敢的游戏玩家，她正在挑战一个 BOSS。BOSS 有 点血量，当 BOSS 的血量小于等于 时，BOSS 就被击败了。

LYA 有一套由 张卡牌组成的卡组。在挑战 BOSS 的过程中，她会按照卡组的顺序依次打出每张卡牌。卡组中有两种类型的卡牌：

1. 激励卡：打出后可以获得 个能量币。
2. 攻击卡：打出后会对 BOSS 造成 点伤害，并额外投掷当前拥有的所有能量币，每个能量币可以等概率地掷出 到 点伤害，最终额外造成的伤害等于所有能量币掷出点数之和。

LYA 想知道，使用这套卡组一次性挑战 BOSS 并将其击败的概率是多少。

输入格式

第一行包含两个整数 和 （，），分别表示卡牌数量和 BOSS 的初始血量。

接下来 行，每行包含两个整数 和 （，），其中 表示该卡牌是激励卡， 表示该卡牌是攻击卡， 表示激励卡提供的能量币数量或攻击卡造成的基础伤害值。

输出格式

输出一个实数，表示 LYA 一次性击败 BOSS 的概率，结果保留 位小数。

样例输入

2 5
1 1
2 1

样例输出

0.5000

数据范围

题解

这是一道概率动态规划问题。我们可以用 表示使用前 张卡牌，累计获得 点额外伤害的概率。

首先，我们遍历卡牌，统计激励卡的能量币总数 ，并累计攻击卡的基础伤害，将 BOSS 的血量 减去这部分伤害。

然后，我们进行概率动态规划。初始化 ，表示使用 张卡牌获得 点额外伤害的概率为 。

接下来，我们从第 张能量币开始，逐步计算 的值。对于每个状态 ，我们枚举当前能量币掷出的点数 （），将 的概率累加到 上，并除以 ，表示当前能量币掷出 点的概率为 。

最后，我们统计 中 的概率之和，即为 LYA 一次性击败 BOSS 的概率。

时间复杂度：，其中 为卡牌数量， 为能量币总数。 空间复杂度：，需要开设 数组记录状态。

参考代码

• Python

def calculate_probability(n, h, cards):
    cnt = 0
    for t, x in cards:
        if t == 1:
            cnt += x
        else:
            h -= x