2024-01-01 21:14 门头沟学院 golang

关注

24秋招(2023.9.24)米哈游笔试真题解析

整体的难度不是特别大，T1是一个签到题，直接枚举即可，T2是经典概率DP问题，T3又是一个数学题，考虑贡献法来统计权值，计算每个元素对结果产生的贡献

T1

题目描述

对于一个数组 $c$ ，定义 $f(c)$ 为 $c$ 数组所有元素的总和。现在给定两个长度为 $n$ 的数组 $a,b$ ，请你恰好删除一个数组 $a$ 的元素或者一个数组 $b$ 的元素，使得 $f(a)$ 异或 $f(b)$ 最大

输入格式

第一行输入一个整数 $n$

第二行输入 $n$ 个整数 $a_i$

第三行输入 $n$ 个整数 $b_i$

$1\le n,a_i,b_i \le 10^5$

输出描述

输出最大的异或和。

样例

输入

3
1 2 3
3 2 1

输出

说明

数组a数组中的3

题解：签到题，枚举删除 $a$ 数组或 $b$ 数组中的某一个数即可

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 5E5 + 10,mod=1e9+7;
typedef long long ll;
ll n,a[N],b[N];
int main() {
    cin>>n;
    ll s1=0,s2=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        s1+=a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
        s2+=b[i];
    }
    ll res=0;
    for(int i=0;i<n;i++){
        res=max({res,s1^(s2-b[i]),(s1-a[i])^s2});
    }
    cout<<res<<endl;
    return 0;
}

Python

N = 500010
mod = int(1e9) + 7
a = [0] * N
b = [0] * N

n = int(input())
s1 = s2 = 0
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(n):
    s1+=a[i]
    s2+=b[i]
res = 0
for i in range(n):
    res = max(res, max(s1 ^ (s2 - b[i]), (s1 - a[i]) ^ s2))
print(res)

T2

题目描述

米小游都快保底了还没抽到希儿，好生气哦!只能打会活动再拿点水晶了。米小游和世界第一可爱的魔法少女 $TeRiRi$ 正在打BOSS，BOSS当BOSS血量小于等于0时，BOSS死亡。 $TeRiRi$ 的血量为 $h$ ，有一套牌，在一轮中，她会按顺序一张一张的将卡牌打出，套牌中有两种卡牌:

1.时来运转，获得 $x$ 个幸运币

2.幸运一掷造成 $x$ 点伤害，并投掷所有幸运币，造成等于所有幸运币掷出的点数之和的伤害

幸运币可以等概率的投掷出1~6之间的点数。米小游想知道， $TeRiRi$ 的套牌在一轮内击杀BOSS的概率

输入格式

第一行输入两个整数 $n(1<n<100),h(1<<10^9)$ ，分别表示卡牌张数和BOSS血量。接下来 $n$ 行每行首先输入两个整数 $t(1\le t\le 2),x(1\le x\le 10)$ ， $t$ 为1表示卡牌为时来运转， $t$ 为2表示卡牌为幸运一掷。

输出格式

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

样例

输入

2 5
1 1
2 1

输出

0.5

说明

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

题解：期望DP

这里有一个细节就是，需要使用第二种卡牌的时候，收集到的硬币才会被打出，因此需要记录打出的硬币数，然后并把怪物的血量扣除固定值 $x$ 的伤害

定义 $f[i][j]$ 为投掷前 $i$ 次点数总和为 $j$ 的概率

最终首先判断投掷的次数 $num*6$ 是否小于 $h$

不小于的话，就把对应的概率之和累加

$f[i][j]=\sum_{k = j-6}^{k = j-1} f[i-1][k]$

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010,M=6010;
int n,t,h,x;
double f[N][M];  //投掷前i次 点数总和为j的概率
int main() {
    int cnt=0,num=0;  //硬币数量
    cin>>n>>h;
    for(int i=0;i<n;i++){
        cin>>t>>x;
        if(t==1){
            cnt+=x;
        }
        else{
            h-=x;
            num+=cnt;
            cnt=0;
        }
    }
    f[0][0]=1.0;
    for(int i=1;i<=num;i++){
        for(int j=i;j<=num*6;j++){
            for(int k=1;k<=6;k++){
                if(j>=k){
                    f[i][j]+=f[i-1][j-k]*1.0/6;
                }
            }
        }
    }
    double res=0.0;
    if(h<=num*6){
        for(int i=h;i<=num*6;i++){
            res+=f[num][i];
        }
    }
    cout<<res<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    static final int N = 1010;
    static final int M = 6010;
    static int n, t, h, x;
    static double[][] f = new double[N][M];  // 投掷前 i 次，点数总和为 j 的概率

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = 0, num = 0;  // 硬币数量
        n = sc.nextInt();
        h = sc.nextInt();
        for (int i = 0; i < n; i++) {
            t = sc.nextInt();
            x = sc.nextInt();
            if (t == 1) {
                cnt += x;
            } else {
                h -= x;
                num += cnt;
                cnt = 0;
            }
        }
        f[0][0] = 1.0;
        for (int i = 1; i <= num; i++) {
            for (int j = i; j <= num * 6; j++) {
                for (int k = 1; k <= 6; k++) {
                    if (j >= k) {
                        f[i][j] += f[i - 1][j - k] * 1.0 / 6;
                    }
                }
            }
        }
        double res = 0.0;
        if (h <= num * 6) {
            for (int i = h; i <= num * 6; i++) {
                res += f[num][i];
            }
        }
        System.out.printf("%.4f\n", res);
    }
}

Python

N = 1010
M = 6010
f = [[0.0 for _ in range(M)] for _ in range(N)]  # 投掷前 i 次，点数总和为 j 的概率

n, h = map(int, input().split())
cnt = num = 0  # 硬币数量
for _ in range(n):
    t, x = map(int, input().split())
    if t == 1:
        cnt += x
    else:
        h -= x
        num += cnt
        cnt = 0
f[0][0] = 1.0
for i in range(1, num + 1):
    for j in range(i, num * 6 + 1):
        for k in range(1, 7):
            if j >= k:
                f[i][j] += f[i - 1][j - k] * 1.0 / 6
res = 0.0
if h <= num * 6:
    for i in range(h, num * 6 + 1):
        res += f[num][i]
print("%.4f" % res)

T3

题目描述

米小游拿到了一个数组 $a$ ，她用这个数组构造一个新数组 $b$ ，其中 $a_i$ 代表 $b$ 数组中有 $a_i$ 个 $i$ 。例如，若 $a=[2,3,1]$ ，那么 $b=[1,1,2,2,2,3]$ ，因为a1 = 2，代表 $b$ 数组中有2个1; $a_2=3$ ，代表 $b$ 数组中有3个2， $a_3=1$ ，代表 $b$ 数组中有1个3。现在给定 $a$ 数组，你需要帮米哈游求出 $b$ 数组中所有连续子数组的极差之和。由于答案可能过大，请对 $10^9+7$ 取模。数组的极差指最大值减去最小值。

输入格式

第一行输入一个正整数 $n$ ，代表 $a$ 数组的元素数量

第二行输入 $n$ 个正整数 $a_i$ ，代表 $a$ 数组的元素。

$1\le n\le 10^5$

$1 \le a_i\le 10^9$

输出格式

一个整数，代表数组中所有区间的极差之和，对 $10^9+7$ 取模的值。

样例

输入

2
2 1

输出

说明

a=[2,1]时，b数组为[1,1,2]。

此时b数组共有6个连续子数组:

[1]的极差为0

[1]的极差为0

[2]的极差为0

[1,1]的极差为0

[1,2]的极差为1

[1,1,2]的极差为1

因此答案是0+0+0+0+1+1=2

题解：贡献法计数+前缀和

考虑第 $i$ 个元素对结果的贡献，选择第 $i$ 个元素对结果的贡献 $b[i]*(b[i+1]*1+b[i+2]*2+...+b[k]*(k-i))$

如果是选择第 $i+1$ 个元素，对结果的贡献为 $b[i+1]*(b[i+2]*1+b[i+3]*2+...+b[k]*(k-i-1))$

右边的差值其实就是 $b[i+1]+b[i+2]+...+b[k]$

因此可以预处理一个后缀和数组来去一遍遍历，一遍计算，当然，也可以不使用后缀和数组，维护两个变量即可，如下代码中的sum和s所示

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 5E5 + 10,mod=1e9+7;
typedef long long ll;
ll n,a[N];
int main() {
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ll res=0,sum=0,s=0;
    for(int i=2;i<=n;i++){
        sum+=1ll*a[i]*(i-1);
        s+=a[i];
    }
    for(int i=1;i<n;i++){  //考虑选择a[i]对结果的贡献 a[i]*(a[i+1]*1+a[i+2]*2+...+a[k]*(k-i)
        ll cur=1ll*a[i]*sum;
        res=(res+cur)%mod;
        sum-=s;
        s-=a[i+1];
    }
    cout<<res<<endl;
    return 0;
}

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] argv) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        final int mod = 1000000007;
        long[] preSum = new long[n];
        for (int i = 0; i < n; i++) {
            preSum[i] = i == 0 ? arr[0] : preSum[i-1]+arr[i];
        }
        long sum = 0;
        for (int i = n-1; i >= 0; i--) {
            sum += 1l * arr[i] * i;
            sum %= mod;
        }
        long res = 0;
        for (int i = 0; i < n; i++) {
            res += 1l * arr[i] * sum;
            res %= mod;
            sum -= preSum[n-1] - preSum[i];
            sum = (sum + mod) % mod;
        }
        System.out.println(res);

    }

}

Python

n = int(input())
arr = list(map(int, input().split()))

mod = 1000000007
preSum = [0] * n
for i in range(n):
    preSum[i] = arr[i] if i == 0 else preSum[i-1] + arr[i]

sum_val = 0
for i in range(n-1, -1, -1):
    sum_val += 1 * arr[i] * i
    sum_val %= mod

res = 0
for i in range(n):
    res += 1 * arr[i] * sum_val
    res %= mod
    sum_val -= preSum[n-1] - preSum[i]
    sum_val = (sum_val + mod) % mod

print(res)

以上内容均来自笔试刷题指南

#秋招##笔试##笔试真题##米哈游#

互联网笔试真题题解文章被收录于专栏

收录近两年互联网公司笔试真题解析，并提供Java，Python，C++三种语言版本的代码