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

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

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

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

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

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

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

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

alt

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

🍅 01.LYA 的异或游戏

题目描述

LYA 非常喜欢玩游戏,最近她发明了一个新的游戏规则。给定两个长度为 的正整数数组 ,每一步可以从其中一个数组中删除一个元素。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
       

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

学长刷题笔记 文章被收录于专栏

这里收集了超全的刷题笔记,欢迎大家的订阅,会持续跟新的

全部评论
谢谢大佬分享
点赞 回复 分享
发布于 08-03 15:49 北京
第一道题的样例,若第一个数组不去,第二个数组只留下1,则和异或为7,不比答案大吗?是不是有点问题。
点赞 回复 分享
发布于 09-17 14:55 浙江

相关推荐

09-27 00:29
东北大学 Java
伟大的麻辣烫:查看图片
阿里巴巴稳定性 74人发布 投递阿里巴巴等公司10个岗位
点赞 评论 收藏
分享
6 10 评论
分享
牛客网
牛客企业服务