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

关注

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

1.棋盘

题目内容

塔子哥有一个n*m的棋盘，一次移动可以选择上下左右四个方向移动一次，不同于普通棋盘，这个棋盘是循环的。

即 $(x,m)$ 和 $(x,1)$ 两个点可以一步到达，其中 $1\le x \le n$ 。同样的， $(n,y)$ 和 $(1,y)$ 两个点也可以一步到达，其中 $1\le y \le m$ 。

现在塔子哥需要从 A先走到 B 点，再从 B 点走到 C点，问最小移动次数是多少。

输入描述

第一行两个整数， $n$ 和 $m$ 。

接下来三行，第一行是点 A 的坐标 $(x_A,y_A)$ ，第二行是点B 的坐标 $(x_B,y_B)$ ，第三行是点 C 的坐标 $(x_C,y_C)$

$1\le n,m \le 10^9,1\le x_A,x_B,x_C\le n,1\le y_A,y_B,y_C\le m$

输出描述

输出从 A 到 B ，再从 B到 C 的最小移动次数

样例

输入

输出

题解：模拟

考虑任意点 $(a,b)$ 到 $(c,d)$ 的最小移动距离

首先，我们可以考虑从 $a$ 到 $c$ 的移动距离

方式1：直接到达： $dist=abs(a-c)$
方式2：先走到 $n$ ，再由 $n$ 走到1，再由1走到 $c$ ， $dist=n-abs(a-c)$

两种方式的移动取最小值， $dist=min(abs(a-c),n-abs(a-c))$

因此 $(a,b)$ 到 $(c,d)$ 的最小移动距离 $dist=min(abs(a-c),n-abs(a-c))+min(abs(b-d),m-abs(b-d))$

按照上述公式模拟即可

复杂度分析

时间复杂度：O(1)

空间复杂度：O(1)

C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

int main()
{
    int n, m;
    cin >> n >> m;

    PII a, b, c;
    cin >> a.first >> a.second;
    cin >> b.first >> b.second;
    cin >> c.first >> c.second;

    long long ans = 0;
    // 从 a 到 b 的 x 轴
    ans += min(abs(a.first - b.first), n - abs(a.first - b.first));
    // 从 a 到 b 的 y 轴
    ans += min(abs(a.second - b.second), m - abs(a.second - b.second));
    // 从 b 到 c 的 x 轴
    ans += min(abs(b.first - c.first), n - abs(b.first - c.first));
    // 从 b 到 c 的 y 轴
    ans += min(abs(b.second - c.second), m - abs(b.second - c.second));

    cout << ans << "\n";
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[][] points = new int[3][2];
        for (int i = 0; i < 3; i++) {
            points[i][0] = scanner.nextInt();
            points[i][1] = scanner.nextInt();
        }

        long ans = 0;
        // 从 a 到 b 的 x 轴
        ans += Math.min(Math.abs(points[0][0] - points[1][0]), n - Math.abs(points[0][0] - points[1][0]));
        // 从 a 到 b 的 y 轴
        ans += Math.min(Math.abs(points[0][1] - points[1][1]), m - Math.abs(points[0][1] - points[1][1]));
        // 从 b 到 c 的 x 轴
        ans += Math.min(Math.abs(points[1][0] - points[2][0]), n - Math.abs(points[1][0] - points[2][0]));
        // 从 b 到 c 的 y 轴
        ans += Math.min(Math.abs(points[1][1] - points[2][1]), m - Math.abs(points[1][1] - points[2][1]));

        System.out.println(ans);
    }
}

Python

n, m = map(int, input().split())

points = []
for _ in range(3):
    x, y = map(int, input().split())
    points.append((x, y))

ans = 0
# 从 a 到 b 的 x 轴
ans += min(abs(points[0][0] - points[1][0]), n - abs(points[0][0] - points[1][0]))
# 从 a 到 b 的 y 轴
ans += min(abs(points[0][1] - points[1][1]), m - abs(points[0][1] - points[1][1]))
# 从 b 到 c 的 x 轴
ans += min(abs(points[1][0] - points[2][0]), n - abs(points[1][0] - points[2][0]))
# 从 b 到 c 的 y 轴
ans += min(abs(points[1][1] - points[2][1]), m - abs(points[1][1] - points[2][1]))

print(ans)

2.有根树的节点个数

题目内容

塔子哥有一个 n 个节点的树，树根编号为 1 。

塔子哥可以在叶子节点上添加一个新的儿子节点，添加后，添加的节点变成了新的叶子节点。

若干次操作后，塔子哥想问你距离树根不超过k 的节点最多可以有多少个。

输入描述

第一行，一个正整数n 表示树中节点个数，k 表示不超过树根的距离，

接下来 n-1行，每行输入两个整数 u和v ，表示节点u和v之间有一条边

$1\le n \le 10^5,1\le k \le 10^9,1\le u,v \le n$

输出描述

一个整数，表示若干次操作后距离树根不超过k的节点最大数量。

样例

输入

输出

样例解释

本身有4个节点到根节点的距离不超过k(1,2,3,4)
叶子节点是(2,3,4) 还可以再添加一个节点
因此总共的数量为4+3=7

题解：DFS+贡献法计数

考虑每一个节点对答案的贡献：如果当前节点距离根节点的距离d有 $d \le k$ ，则答案+1

此外，如果当前节点还是叶子节点，则说明还可以再叶子结点下添加 $k-d$ 个点，这些点可以构成一条链。

根据上述方式统计计数即可，注意本题题目给的是无向边，需要建两条有向边。

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;   
    // 建图
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    const int INF = 0x3f3f3f3f;
    long long ans = 0;
    vector<int> dist(n, INF);
    // 计算1号点到每个点的距离，1号点到自己的距离为 0
    dist[0] = 0;
    function<void(int,int)> dfs = [&](int u, int fa) {
        // 如果1号点到u+1点的距离 <= k，则答案加1
        if (dist[u] <= k) {
            ans += 1;
        }

        // 如果1号点到叶子的距离 < k，则还可以再这个叶子下加 k - dist[u] 个
        if (u != 0 && g[u].size() == 1 && dist[u] < k) {
            ans += k - dist[u];
        }

        // 继续遍历子树 v 
        for (int v: g[u]) {
            if (v == fa) continue;
            dist[v] = dist[u] + 1;
            dfs(v, u);
        }
    };
    
    dfs(0, -1);

    cout << ans << "\n";

    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static List<List<Integer>> g;
    static int[] dist;
    static int n, k;
    static long ans;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        
        // 建图
        g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }

        for (int i = 1; i < n; i++) {
            int u = scanner.nextInt() - 1;
            int v = scanner.nextInt() - 1;
            g.get(u).add(v);
            g.get(v).add(u);
        }

        final int INF = 0x3f3f3f3f;

        ans = 0;
        dist = new int[n];
        for (int i = 0; i < n; i++) {
            dist[i] = INF;
        }
        // 计算1号点到每个点的距离，1号点到自己的距离为 0
        dist[0] = 0;

        dfs(0, -1);

        System.out.println(ans);
    }

    static void dfs(int u, int fa) {
        // 如果1号点到u+1点的距离 <= k，则答案加1
        if (dist[u] <= k) {
            ans++;
        }
        // 如果1号点到叶子的距离 < k，则还可以再这个叶子下加 k - dist[u] 个
        if (u != 0 && g.get(u).size() == 1 && dist[u] < k) {
            ans += k - dist[u];
        }
        // 继续遍历子树 v 
        for (int v : g.get(u)) {
            if (v == fa) {
                continue;
            }
            dist[v] = dist[u] + 1;
            dfs(v, u);
        }
    }
}

Python3

def dfs(u, fa):
    global ans
    # 如果1号点到u+1点的距离 <= k，则答案加1
    if dist[u] <= k:
        ans += 1
    # 如果1号点到叶子的距离 < k，则还可以再这个叶子下加 k - dist[u] 个
    if u != 0 and len(g[u]) == 1 and dist[u] < k:
        ans += k - dist[u]
    # 继续遍历子树 v 
    for v in g[u]:
        if v == fa:
            continue
        dist[v] = dist[u] + 1
        dfs(v, u)


n, k = map(int, input().split())

# 建图
g = [[] for _ in range(n)]
for _ in range(1, n):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

INF = int(1e9)

ans = 0
dist = [INF] * n
# 计算1号点到每个点的距离，1号点到自己的距离为 0
dist[0] = 0

dfs(0, -1)

print(ans)

3.原神抽卡

小米很喜欢在原神中抽卡，而且他只抽活动池。

活动池的抽卡有三种结果：非五星角色，五星限定角色，五星常驻角色。

抽到五星常驻角色和五星限定角色的概率均为 $\frac{p}{2}$ ，抽到非五星角色的概率为 $1-p$

如果抽到了五星常驻角色，则之后的抽卡结果将发生变化，变为 $p$ 的概率抽到五星限定角色， $1-p$ 的概率抽到非五星卡。

如果连续89抽都没有抽到五星角色，则第90抽必定抽到一个五星限定角色或者五星常驻角色

给定一个概率 $p$ ，请你求出小米抽到五星限定角色的期望次数是多少？

输入格式

一个小数 $p$ 表示抽卡概率， $0<p<1$

输出格式

一个小数，表示抽到五星限定角色的抽卡次数期望。你的答案和正确答案的误差不超过 $10^{-6}$ 即视为正确

样例

输入

0.001

输出

129.1649522

题解：期望DP

我们可以发现，抽到第一次五星角色有50%的概率是限定五星角色，抽到第二次五星角色（如果第一次歪了）100%概率是限定五星角色，那么我们设第一次抽到五星角色为 $P$ ,第二次同理可得，也为 $P$ ，那么整体的抽到五星限定角色的概率就是 $P*0.5+P*1=1.5P$

定义 $dp[i]$ 为第 $i$ 次抽到五星角色的概率，第 $i$ 次抽中，说明前 $i-1$ 次均没有抽中，因此状态转移方程为 $dp[i]=(1- \sum_{j=1}^{i-1}dp[j] )*p$

期望就是概率乘权值 $E=\sum i*dp[i]$

代码中可以使用前缀和优化，即可把 $dp[i]$ 变为 $\sum_{j=1}^{i}dp[j]$

C++

#include <iostream>
using namespace std;
double dp[91];

int main() {
    double p;
    cin >> p;

    double cnt = 0; //记录总期望次数

    for (int i = 1; i < 90; i++) {
        dp[i] = (1 - dp[i - 1]) * p;
        cnt += dp[i] * i;
        dp[i] += dp[i - 1]; // 前缀和
    }

    cnt += 90 * (1 - dp[89]); // i = 90时特殊处理
    cout << fixed;
    cout.precision(7);
    cout << cnt * 1.5 << "\n";

    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double p = sc.nextDouble();
        double[] dp = new double[91];
        double cnt = 0;		//记录总期望次数
        for(int i = 1 ; i < 90 ; i++) {
            dp[i] = (1-dp[i-1]) * p;
            cnt += dp[i] * i;
            dp[i] += dp[i-1];		//前缀和
        }
        cnt += 90 * (1-dp[89]);		//i=90时特殊处理
        System.out.printf("%.7f\n", cnt *1.5);
    }
}

Python

p = float(input())

dp = [0] * 91
cnt = 0 # 记录总期望次数

for i in range(1, 90):
    dp[i] = (1 - dp[i - 1]) * p
    cnt += dp[i] * i
    dp[i] += dp[i - 1]  # 前缀和

cnt += 90 * (1 - dp[89])  # i=90时特殊处理

print(f"{cnt * 1.5:.7f}")

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

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

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

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