【秋招突围】2024届秋招-米哈游笔试题-第一套
🍭 大家好这里是清隆Coding ,一枚热爱算法的程序员
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 编程一对一辅导
✨ 本系列打算持续跟新
秋招笔试题
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷春秋招笔试合集
🌰 今晚米哈游的提前批就要开始啦,我们来看看去年秋招米哈游真题卷的难度怎么样
💡第一题比较简单是个基础的
位运算贪心
问题,第二题是一个概率DP
,不太好做,第三题考察的是计数相关的DP
,也是比较难的一类,总体来看这次笔试还是不简单的
米哈游-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 的过程中,她会按照卡组的顺序依次打出每张卡牌。卡组中有两种类型的卡牌:
- 激励卡:打出后可以获得 个能量币。
- 攻击卡:打出后会对 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%内容,订阅专栏后可继续查看/也可单篇购买
这里收集了超全的刷题笔记,欢迎大家的订阅,会持续跟新的