01-01 21:19 门头沟学院 golang

关注

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

1.米小游学英语

题目描述

米小游读小学了，学校里新开了英语课。

某一天老师进行了一对一的口语考试，考试内容为复述老师说的话。考试要求每个人一共进行 $t$ 次测试，每次测试中，老师会说一句话，包含 $n$ 个单词，米小游每复述出一个单词，就能够获得一分，但是当分数低于0时，本次测试就会结束，并且该次测试未通过。

米小游英语很差，因此他想知道自己一共能通过多少次测试。

输入描述

第一行输入一个正整数 $t$ ，代表米小游需要进行的测试数量

接下来的3*t行，每3行用于描述一次测试:

第一行输入一个正整数 $n$ ，代表老师说的一句话包含的单词数量。

第二行输入 $n$ 个仅由小写字母组成的字符串，用空格隔开。代表老师说的单词。

第三行输入 $n$ 个仅由小写字母组成的字符串，用空格隔开。代表米小游复述的话。

$1\le t \le 10,1\le n \le 100$

单词的长度均不超过10。

输出描述

一个整数，代表米小游最终通过了多少次测试。

样例

输入

3
2
hello hello
hello hello
3
how are you
hwo are you
4
how old are you
how old are yuo

输出

题解：模拟

维护一个变量score和cnt表示米小游每次答题的分数和能通过多少次测试，如果某一轮测试中某一时刻的score的值<0，则直接跳出当前循环，如果最终有 $score\ge 0$ ，则cnt计数+1。

复杂度分析

时间复杂度： $O(n*t*10)$

空间复杂度： $O(n)$

C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
#define x first
#define y second
typedef long long ll;
const int N=2E5+10,mod=1e9+7;
int n,m;
string w[N],t[N];
int main(){
    cin>>n;
    int cnt=0;
    for(int i=0;i<n;i++){
        cin>>m;
        for(int i=0;i<m;i++){
            cin>>w[i];
        }
        for(int i=0;i<m;i++){
            cin>>t[i];
        }
        int score=0;
        for(int i=0;i<m;i++){
            if(w[i]==t[i])score++;
            else score--;
            if(score<0){
                break;
            }
        }
        if(score>=0){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int res = n;
        while (n -- > 0) {
            int len = sc.nextInt();
            sc.nextLine();
            String[] s1 = sc.nextLine().split(" ");
            String[] s2 = sc.nextLine().split(" ");
            int count = 0;
            for (int i = 0; i < len; i++) {
                if (s1[i].equals(s2[i])) {
                    count++;
                } else {
                    count--;
                }
                if (count < 0) {
                    res--;
                    break;
                }
            }
        }
        System.out.println(res);
    }
}

Python

t = eval(input())
final = 0
for _ in range(t):
    num = int(input())
    s1 = input().split()
    s2 = input().split()
    score = 0
    for j in range(num):
        if s1[j] == s2[j]:
            score +=1
        else:
            score -=1
        if score < 0:
            break
    if score >= 0:
        final += 1
print(final)

2.希尔割草

题目描述

希尔最近沉迷于一款割草游戏。所谓割草游戏，并不是割草模拟器，而是指一款击杀敌人快，很容易一次性就击杀大量敌人的游戏。

希尔每放一个大范围aoe技能下去，就能看见屏幕上一大片的敌人消失，非常解压。

这天，希尔又在玩这款割草游戏了，他看着面前的n*个敌人，每个敌人都有 $a_i$ 的血，但是突然发现他的技能只能给一个敌人造成1点伤害了。但好在希尔所使用的角色点了天赋，开局时给所有敌人添加debuff，当一名敌人血量降到一半及以下时，就会给所有敌人造成1点伤害(这个debuff触发一次后消失)。希尔想知道，他最少需要多少次攻击才能击杀所有敌人。

输入描述

第一行输入一个正整数 $n$ ，代表敌人的最大数量

第二行输入 $n$ 个正整数 $a_i$ ，代表每个敌人的血量

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

输出描述

一个正整数，代表希尔攻击的最小次数。

样例

输入

2
6 8

输出

样例说明

希尔打第一个敌人3次，触发天赋，每个敌人剩余2，7血。接下来，希尔打第二个敌人3次，触发天赋，每个敌人剩余1，3血。希尔无法再触发天赋了，因此还要攻击4次，总共是10次。

题解：贪心+排序

为了尽可能减少攻击次数，我们肯定是想把天赋效果尽可能发挥满，也就是说，能被天赋aoe效果击败的怪物，我们就不主动攻击他。

什么怪物必须要攻击呢，显然，天赋最多只能触发 $n$ 次，如果一个怪物的血量 $\ge n$ ，那么一定是要对他进行攻击的。

此外，对于血量更多的一些怪物，即使我们把它留到最后再去攻击（触发完其他所有怪物的aoe效果之后），它本身还是不会触发aoe效果，因此，我们需要将他们的aoe优先触发，这个血量阈值是2n。

剩余的怪物，先触发血量少的怪物的aoe肯定会优于先触发血量多的情况，因为先触发血量多的可能会把血量少的打死，导致aoe伤害浪费，进而导致总攻击次数增多。

所以我们先将怪物按血量排序，然后计算血量大于2n的怪物的需要手动攻击的攻击次数，同时记录aoe的触发次数cnt，再依次从小到大依次处理

当我们判断第 $i$ 个敌人时，如果该敌人被天赋攻击cnt次后不能触发天赋，我们就要打到他触发天赋(血量少的要比血量多的先触发天赋，所以这里一定要打)，如果可以触发就省去这一步，之后还要减去后面n-cnt个敌人天赋触发扣的血，敌人剩余的血量就是我们额外要攻击的次数，进行累加即可。

复杂度分析

时间复杂度： $O(nlogn)$

空间复杂度： $O(n)$

C++

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

int main() {
    int n;
    cin >> n; // 输入n
    vector<int> msters;
    for (int i = 0; i < n; i++) {
        int mster;
        cin >> mster; // 输入怪物的血量
        msters.push_back(mster);
    }
    sort(msters.begin(), msters.end()); // 对怪物血量进行排序
    
    int cnt = 0; // 记录已经触发的aoe次数
    int ans = 0; // 记录攻击总次数
    while (!msters.empty() && msters.back() >= 2 * n) {
        ans += msters.back() - n; // 实际攻击时将接受剩余aoe的血量预留下来
        cnt++; // 触发的aoe次数+1
        msters.pop_back(); // 移除血量大于等于2n的怪物
    }
    
    for (int i = 0; i < msters.size(); i++) {
        int msterhp = msters[i];
        int nowhp = msterhp - cnt; // 当前怪物接受完之前的aoe后的剩余血量
        
        if (nowhp > msterhp / 2) {
            ans += nowhp - msterhp / 2; // 如果当前敌人没有触发aoe，攻击他直到触发他的aoe
            nowhp = msterhp / 2;
        }
        
        if (nowhp - (n - cnt) > 0) {
            ans += nowhp - (n - cnt); // 计算当前敌人需要的额外攻击次数
        }
        
        cnt++; // 触发的aoe次数+1
    }
    
    cout << ans << endl; // 输出攻击总次数
    return 0;
}

Java

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 输入n
        int[] msters = new int[n];
        for (int i = 0; i < n; i++) {
            msters[i] = scanner.nextInt(); // 输入怪物的血量
        }
        Arrays.sort(msters); // 对怪物血量进行排序
        
        int cnt = 0; // 记录已经触发的aoe次数
        int ans = 0; // 记录攻击总次数
        while (msters.length > 0 && msters[msters.length - 1] >= 2 * n) {
            ans += msters[msters.length - 1] - n; // 实际攻击时将接受剩余aoe的血量预留下来
            cnt++; // 触发的aoe次数+1
            msters = Arrays.copyOf(msters, msters.length - 1); // 移除血量大于等于2n的怪物
        }
        
        for (int msterhp : msters) {
            int nowhp = msterhp - cnt; // 当前怪物接受完之前的aoe后的剩余血量
            
            if (nowhp > msterhp / 2) {
                ans += nowhp - msterhp / 2; // 如果当前敌人没有触发aoe，攻击他直到触发他的aoe
                nowhp = msterhp / 2;
            }
            
            if (nowhp - (n - cnt) > 0) {
                ans += nowhp - (n - cnt); // 计算当前敌人需要的额外攻击次数
            }
            
            cnt++; // 触发的aoe次数+1
        }
        
        System.out.println(ans); // 输出攻击总次数
    }
}

Python

n = int(input())
msters = list(map(int, input().split()))
msters.sort()
cnt = 0
ans = 0
while msters and msters[-1] >= 2*n:        #先处理血量大于2*n的怪物
    ans += msters.pop() - n            #实际攻击时将接受剩余aoe的血量预留下来，实际攻击次数就相当于接受完n次aoe后的血量
    cnt += 1                    #记录已经触发的aoe次数
for msterhp in msters:        #再依次从小到大取数
    nowhp = msterhp - cnt            #当前怪物接受完之前的aoe后的剩余血量
    if nowhp > msterhp // 2:        #如果当前敌人没有触发aoe，就攻击他直到触发他的aoe
        ans += nowhp - msterhp//2
        nowhp = msterhp//2
    if nowhp - (n-cnt) > 0:    #再计算当前敌人需要的攻击次数
        ans += nowhp - (n-cnt)
    cnt += 1        #记录的aoe次数+1
print(ans)

3.莫娜施法

题目描述

莫娜是一名远近闻名的魔法师。

这天他受邀来到了一个国家，来帮这个国家的国王解决一个问题。这个国家的国王年轻时曾有一颗非常美丽的树，但是国王却不小心惹怒了一个十分邪恶的黑魔法师，于是黑魔法师施法，让这棵树变得十分丑陋。现在，这棵树一共有 $n$ 个节点，根节点为1号节点，其深度为1。每个节点都被黑魔法师随机施加了一个丑陋值，丑陋值越大，越影响这棵树的美观度，影响值为该节点的深度乘其丑陋值。

国王苦苦寻找了半辈子解决方案，让无数魔法师尝试过，但都没办法将树变回原样。长时间受黑魔法影响，这棵树再也无法变为原样了。终于，国王找到了莫娜，希望莫娜能尽可能地将树的丑陋值减少，并承诺，减少了多少丑陋值，就给莫娜多少钱。

莫娜看了看树，发现受黑魔法影响，只能裁剪树的一部分将其嫁接到另一个节点上。莫娜想挣尽可能多的钱，因此他想知道能将树的丑陋值降到的最小值是多少？

注：只能裁剪一次。

输入描述

第一行输入一个整数 $n(1\le n \le 10^5)$ 表示的大小

第二行输入 $n$ 个整数 $a(1\le a_i\le 10^8)$ 表示每个节点的丑陋值

接下来 $n-1$ 行，每行输入两个整数 $u,v(1\le u,v \le n)$ ，表示树上的边

输出描述

输出一个整数表示最小的丑陋值

样例

输入

输出

题解：树形DP

定义 $sum[i]$ 为以 $i$ 为根节点的子树的权值和， $d[i]$ 为 $i$ 节点的深度， $f[i]$ 为以 $i$ 为根节点的子树的丑陋值和，我们可以从根节点1开始，跑一遍DFS，来计算上述的值。

然后我们可以考虑裁剪第 $i(2\le i \le n)$ 个节点，贪心的考虑，一定是把当前的节点，嫁接到根节点的位置上，那么，其实改变的丑陋值其实就是以 $i$ 为根节点的子树的丑陋值对应的部分。

没裁剪之前这一部分的值为 $d[i]*sum[i]$

裁剪并嫁接后的这一部分的值为 $2*sum[i]$

对应的差值 $diff=(d[i]-2)*sum[i]$

复杂度分析

时间复杂度： $O(n)$

空间复杂度： $O(n)$

C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
#define x first
#define y second
typedef long long ll;
const int N=2E5+10,mod=1e9+7;
int n,m;
ll f[N],w[N],d[N],sum[N];
vector<int>g[N];
vector<ll> dfs(int u,int fa,int depth){
    d[u]=depth;
    sum[u]=w[u];
    f[u]+=1ll*w[u]*d[u];
    for(int &x:g[u]){
        if(x==fa)continue;
        auto t=dfs(x,u,depth+1);
        f[u]+=t[0];sum[u]+=t[1];
    }
    return {f[u],sum[u]};
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,0,1);
    ll res=f[1];
    for(int i=2;i<=n;i++){  //考虑替换第i个节点
        if(d[i]<=2)continue;
        ll down=1ll*(d[i]-2)*sum[i];
        res=min(res,f[1]-down);
    }
    cout<<res<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    static final int N = 200010;
    static final int mod = (int)1e9 + 7;
    static int n;
    static long[] f = new long[N], w = new long[N], d = new long[N], sum = new long[N];
    static List<Integer>[] g = new ArrayList[N];

    static long[] dfs(int u, int fa, int depth) {
        d[u] = depth;
        sum[u] = w[u];
        f[u] += 1L * w[u] * d[u];
        for (int x : g[u]) {
            if (x == fa) continue;
            long[] t = dfs(x, u, depth + 1);
            f[u] += t[0];
            sum[u] += t[1];
        }
        return new long[]{f[u], sum[u]};
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextLong();
            g[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            g[a].add(b);
            g[b].add(a);
        }
        dfs(1, 0, 1);
        long res = f[1];
        for (int i = 2; i <= n; i++) {
            if (d[i] <= 2) continue;
            long down = 1L * (d[i] - 2) * sum[i];
            res = Math.min(res, f[1] - down);
        }
        System.out.println(res);
    }
}

Python

from collections import defaultdict

N = 200010
mod = int(1e9) + 7
n = 0
f = [0] * N
w = [0] * N
d = [0] * N
sum = [0] * N
g = defaultdict(list)

def dfs(u, fa, depth):
    d[u] = depth
    sum[u] = w[u]
    f[u] += 1 * w[u] * d[u]
    for x in g[u]:
        if x == fa:
            continue
        t = dfs(x, u, depth + 1)
        f[u] += t[0]
        sum[u] += t[1]
    return f[u], sum[u]

n = int(input())
w=[0]+list(map(int,input().split()))
for i in range(1, n):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
dfs(1, 0, 1)
res = f[1]
for i in range(2, n + 1):
    if d[i] <= 2:
        continue
    down = 1 * (d[i] - 2) * sum[i]
    res = min(res, f[1] - down)
print(res)

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

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

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

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