大家好这里是清隆Coding ,一枚热爱算法的程序员
ACM金牌团队️ | 多次AK大厂笔试 | 编程一对一辅导
✨ 本系列打算持续跟新
秋招笔试题
感谢大家的订阅➕ 和 喜欢 和 手里的小花花
今晚米哈游的提前批就要开始啦,我们来看看去年秋招米哈游真题卷的难度怎么样
第一题比较简单是个基础的
位运算贪心
问题,第二题是一个概率DP
,不太好做,第三题考察的是计数相关的DP
,也是比较难的一类,总体来看这次笔试还是不简单的
LYA 非常喜欢玩游戏,最近她发明了一个新的游戏规则。给定两个长度为 的正整数数组 和 ,每一步可以从其中一个数组中删除一个元素。LYA 的目标是使得游戏结束时,两个数组剩余元素的总和的异或值最大。
现在 LYA 想请你帮忙计算,按照最优策略进行游戏,最后能得到的最大异或值是多少。
第一行输入一个正整数 ,表示数组的长度。
第二行输入 个正整数 ,表示数组 的元素。
第三行输入 个正整数 ,表示数组 的元素。
输出一个整数,表示按照最优策略进行游戏,最后能得到的最大异或值。
3
1 2 3
3 2 1
5
删除数组 中的元素 ,剩余元素的总和为 ;数组 的元素总和为 。两者的异或值为 。可以证明这是最大的异或值。
本题可以使用贪心的思想来解决。我们可以发现,异或运算的一个重要性质是:对于任意两个非负整数 和 ,有 ,当且仅当 和 的二进制表示中至少有一位不同时取等号。
因此,为了使异或值最大,我们希望两个数组剩余元素的总和之差尽可能大,同时要让它们的二进制表示有尽可能多的不同位。
基于这个思路,我们可以先计算出两个数组的元素总和 和 ,然后枚举删除一个元素的所有情况,更新异或值的最大值即可。
具体地,对于数组 中的每个元素 ,删除它后两个数组的元素总和之差为 ,异或值为 ;对于数组 中的每个元素 ,删除它后两个数组的元素总和之差为 ,异或值为 。我们取所有情况中的最大值作为答案。
时间复杂度为 ,空间复杂度为 。
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)
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);
}
}
#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;
}
LYA 是一位勇敢的游戏玩家,她正在挑战一个 BOSS。BOSS 有 点血量,当 BOSS 的血量小于等于 时,BOSS 就被击败了。
LYA 有一套由 张卡牌组成的卡组。在挑战 BOSS 的过程中,她会按照卡组的顺序依次打出每张卡牌。卡组中有两种类型的卡牌:
LYA 想知道,使用这套卡组一次性挑战 BOSS 并将其击败的概率是多少。
第一行包含两个整数 和 (,),分别表示卡牌数量和 BOSS 的初始血量。
接下来 行,每行包含两个整数 和 (,),其中 表示该卡牌是激励卡, 表示该卡牌是攻击卡, 表示激励卡提供的能量币数量或攻击卡造成的基础伤害值。
输出一个实数,表示 LYA 一次性击败 BOSS 的概率,结果保留 位小数。
2 5
1 1
2 1
0.5000
这是一道概率动态规划问题。我们可以用 表示使用前 张卡牌,累计获得 点额外伤害的概率。
首先,我们遍历卡牌,统计激励卡的能量币总数 ,并累计攻击卡的基础伤害,将 BOSS 的血量 减去这部分伤害。
然后,我们进行概率动态规划。初始化 ,表示使用 张卡牌获得 点额外伤害的概率为 。
接下来,我们从第 张能量币开始,逐步计算 的值。对于每个状态 ,我们枚举当前能量币掷出的点数 (),将 的概率累加到 上,并除以 ,表示当前能量币掷出 点的概率为 。
最后,我们统计 中 的概率之和,即为 LYA 一次性击败 BOSS 的概率。
时间复杂度:,其中 为卡牌数量, 为能量币总数。 空间复杂度:,需要开设 数组记录状态。
def calculate_probability(n, h, cards):
cnt = 0
for t, x in cards:
if t == 1:
cnt += x
else:
h -= x