2024-01-02 16:49 门头沟学院 golang

关注

24暑期实习(2023.3.5)米哈游笔试真题解析

T1 玫瑰鸭

塔子哥是一名厨艺达人，最近特别喜欢做玫瑰鸭，因为这种菜式的口感鲜美且具有一定的艺术性。

塔子哥的厨房里，堆满了新鲜的食材，其中包括大量的鸭肉和玫瑰花。

然而，当他想要烹制一些玫瑰鸭时，他发现他的材料可能不够用。他有 $a$ 个玫瑰花， $b$ 个鸭肉，以及 $c$ 个神秘的魔法食材，可以当作玫瑰花或者鸭肉使用。

塔子哥知道做一只玫瑰鸭需要 $2$ 个玫瑰花和 $2$ 个鸭肉。他希望尽可能多地制作玫瑰鸭，而不浪费任何食材。

现在他需要你的帮助，来计算他最多能制作多少只玫瑰鸭。

输入描述

输入三个整数 $a,b,c$ ，用空格隔开。 $0\le a,b,c\le 10^9$

输出描述

一个整数，代表可以制作的玫瑰鸭的最大数量。

样例

输入

3 3 3

输出

样例解释

可以将两个万能食材当作一个玫瑰花和一个鸭肉，所以是 4 4 1 可以制作两个玫瑰鸭。

题解：贪心

由于是选用等量的食材，因此一定是希望最大化 $min(a,b)$

假设 $a<b$ ，则首先尽可能让 $a=b$ ，然后在平分剩下的 $c$

代码

C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll a , b , c;
    cin >> a >> b >> c;
    if (a > b) swap(a , b);
    ll f = min(b - a , c);
    c -= f;
    a += f;
    a += c / 2;
    cout << a / 2 << endl;
    return 0;
}

Java

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            int result = 0;
            if(Math.abs(a-b) >= c){
                result = (Math.min(a,b)+c)/2;
            }else{
                result = ((c - Math.abs(a-b))/2+Math.max(a,b))/2;
            }
            System.out.print(result);
        }
    }
}

Python

a, b, c = map(int, input().split())
if c <= abs(a - b):
    print((min(a, b) + c) // 2)
else:
    print((max(a, b) + (c - abs(a - b)) // 2) // 2)

T2 N皇后

塔子哥是一个热衷于国际象棋的棋手，他最近在研究 $n$ 皇后问题。在国际象棋中，皇后是一种强大的棋子，能够沿着横、竖、斜线攻击其他棋子。

而在 $n$ 皇后问题中，皇后也是一种强大的棋子，它能攻击同一行、同一列以及同一 $45$ 度角斜线和 $135$ 度角斜线上的其他皇后。

塔子哥手上拿着一个 $n\times n$ 的棋盘，上面已经放置了一些皇后。他希望再放置一个皇后，使得所有的皇后不会互相攻击。

对于一个 $n\times n$ 的棋盘，有多种不同的摆放皇后的方式，而有些摆法可能会导致皇后之间发生攻击，有些摆法则不会。

因此，塔子哥需要找到所有满足条件的摆法，以便让他更好地研究 $n$ 皇后问题，你能帮塔子哥求出有多少种放置方案吗？

输入描述

第一行输入一个正整数 $n$ ，代表棋盘大小。

接下来的 $n$ 行，每行输入一个仅由 $.$ 和 $*$ 组成的字符串，其中 $*$ 代表放置了一个皇后， $.$ 代表未放置皇后。

保证输入的棋盘中没有两个皇后会互相攻击。

$1\le n\le 1000$

输出描述

输出塔子哥有多少种放置方案。

样例

输入

3
.*.
...
...

输出

题解：模拟

我们可以根据当前棋盘已经放置的皇后位置，来对棋盘的任意一个位置 $(i,j)$ 是否可以放置皇后来做一个标记，如果 $(x,y)$ 点已经放置了皇后，那么第 $x$ 行，第 $y$ 列，以及 $(x,y)$ 的两个对角线都不可放置皇后，对于行和列我们可以使用两个数组来标记，对于两个对角线，我们可以使用 $dig[x-y]$ 和 $idig[x+y]$ 这两个标记数组来判断是否可以放置，这样模拟一遍，最终我们再枚举每一个位置是否可以放置皇后，输出对应的合法数量即可。

C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1005;
int a[maxn][maxn];
// 记录行，列，正负对角线的皇后个数
int c[maxn] , r[maxn] , x[maxn * 2] , y[maxn * 2];
int main()
{
    int n;
    cin >> n;
    bool ok = true;
    for (int i = 1 ; i <= n ; i++){
        string t;
        cin >> t;
        t = '#' + t;
        for (int j = 1 ; j <= n ; j++){
            if (t[j] == '*'){
                a[i][j] = 1;
                if (r[i] || c[j] || x[i - j + n] || y[i + j]){
                    ok = false;
                }
                r[i]++;
                c[j]++;
                x[i - j + n]++;
                y[i + j]++;
            }
        }
    }
    if (!ok){
        cout << "0" << endl;
        return 0;
    }
    int cnt = 0;
    for (int i = 1 ; i <= n ; i++){
        for (int j = 1 ; j <= n ; j++){
            if (a[i][j] == 1) continue;
            if (r[i] || c[j] || x[i - j + n] || y[i + j]) continue;
            cnt ++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Java

import java.util.*;
public class Main{
    public static void main(String args[]){
        queen();
    }
    public static void queen(){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        scanner.nextLine();
        HashSet<Integer> row=new HashSet<>();
        HashSet<Integer> col=new HashSet<>();
        HashSet<Integer> dia1=new HashSet<>();
        HashSet<Integer> dia2=new HashSet<>();
        int c;
        for(int i=0;i<n;i++){
            String s=scanner.nextLine();
            c=s.indexOf("*");
            if(c!=-1){
                row.add(i);
                col.add(c);
                dia1.add(i+c);
                dia2.add(i-c);
            }
        }
        int count=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(row.contains(i)||col.contains(j)||dia1.contains(i+j)||dia2.contains(i-j)){
                    continue;
                }
                count++;
            }
        }
        System.out.println(count);
    }
    
}

Python

import sys
def dataProcess():
    n = int(input())
    grid = []
    for i in range(n):
        temp = input()
        grid.append(list(temp))
    return n,grid

# I only add one queen for next backtracing operation
def nQueen(n, grid):
    c = [0] * n
    r = [0] * n
    x = [0] * 2 * n
    y = [0] * 2 * n
    a = [[0 for i in range(n)] for j in range(n)]
    ans = 0
    for i in range(n):
        for j in range(n):
            if grid[i][j] == "*":
                a[i][j] = 1
                r[j] += 1
                c[i] += 1
                x[i-j+n] += 1
                y[i+j] += 1
    for i in range(n):
        for j in range(n):
            if a[i][j] == 1:
                continue
            if c[i]!=0 or r[j]!=0 or x[i-j+n]!=0 or y[i+j]!=0:
                continue
            ans += 1        
    return ans


if __name__ == "__main__":
    n,grid = dataProcess()
    ans = nQueen(n, grid)
    print(ans)

T3 最长的通讯路径

塔子哥是一位研究者，他在研究网络传输时遇到了一个问题。

他拿到了一张通讯网络的拓扑结构图，其中每条通讯线路被染成了红色或者蓝色。

他想找到一条长度最长的通讯路径，使得路径上相邻的两条线路颜色不同。

输入描述

第一行输入一个正整数 $n$ ，代表节点数量。

接下来的 $n-1$ 行，每行输入两个正整数 $u,v$ 和一个字符 $chr$ ，代表节点 $u$ 和节点 $v$ 有一条边连接。

若为 $'R'$ 代表这条边是红色， $'B'$ 代表这条边是蓝色。

$1\le n \le 10^5$

$1\le u,v\le n$

保证输入的是一颗树。

输出描述

一个正整数，代表塔子哥可以选择的路径最大长度。

样例

输入

输出

样例解释

选择 $1-2-3$ 的路径即可。

题解：树形DP

默认以1为根节点进行DFS遍历。

$dp[i][0]$ 表示在以 $i$ 为根节点的子树中，且与 $i$ 的连边为蓝色所有路径中最长的。 $dp[i][1]$ 表示以 $i$ 为根节点的子树中，与 $i$ 的连边为红色的所有路径中最长的。那从前面两个dp我们可以知道以 $i$ 为根节点，且选择了节点 $i$ 的最长路径肯定是 $dp[i][0]+dp[i][1]$ 。那假如我们讨论了所有子树，那么最长路径也肯定知道了。

现在问题在于如何得到所有节点的dp值呢。我们发现假如我们知道了一个节点 $u$ 的所有子节点 $v$ 的 $dp$ 值，那么 $u$ 的 $dp$ 值也就知道了。因为节点 $u$ 的 $dp[u][x]=max(dp[u][x],dp[v][x\oplus 1]+1)$ 所以我们需要先知道所有子节点的值 $dp$ 值，再用子节点的 $dp$ 值去更新父节点。这个我们用dfs处理

C++

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef pair<int, int>pii;
int n;
vector<pii>edge[MAXN];
int dp[MAXN][2];
int maxn = 0;
void dfs(int u, int fa){
	if(edge[u].size() == 1 && edge[u][0].first == fa)return;//叶子节点直接return，因为叶子节点的两个dp值肯定是0
	for(int i = 0; i < edge[u].size(); i++){
		pii now = edge[u][i];
		int v = now.first;
		if(v == fa)continue;//如果是父节点，continue，因为我们讨论的是以u为根节点的子树，而u的父节点肯定不属于这颗子树的
		dfs(v, u);//得到子节点答案
		int col = now.second;
		dp[u][col] = max(dp[u][col], dp[v][col ^ 1] + 1);//dp状态转移，用子节点v更新u
		maxn = max(maxn, dp[u][0] + dp[u][1]);//记录答案
	}
}
int main(){
	cin >> n;
	int u, v;
	char ch;
	memset(dp, 0, sizeof dp);//dp初始化
	for(int i = 1; i <= n - 1; i++){
		scanf("%d%d", &u, &v);
		cin >> ch;
		edge[u].push_back({v, ch == 'R'?1:0});
		edge[v].push_back({u, ch == 'R'?1:0});//建图
	}
	dfs(1, 0);
	cout << maxn << endl;
}

Java

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

class TreeNode{
    List<TreeNode> friends;
    List<Character> colors;

    public TreeNode(){
        friends = new ArrayList<TreeNode>();
        colors = new ArrayList<Character>();
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        TreeNode[] tree = new TreeNode[n];
        for(int i = 0; i < n; i++) tree[i] = new TreeNode();
        for(int i=0;i<n-1;i++){
            String[] s = in.nextLine().split(" ");
            int x = Integer.parseInt(s[0])-1;
            int y = Integer.parseInt(s[1])-1;
            char c = s[2].charAt(0);
            if(x>y){
                int temp = x;
                x = y;
                y = temp;
            }
            tree[x].friends.add(tree[y]);
            tree[x].colors.add(c);
            tree[y].friends.add(tree[x]);
            tree[y].colors.add(c);
        }
        int result = 0;
        for(int i=0;i<n;i++){
            result = Math.max(result, dfs(tree[i], null, 'B'));
            result = Math.max(result, dfs(tree[i], null, 'R'));

        }
        System.out.println(result);

    }

    public static int dfs(TreeNode tree, TreeNode parent, char color){
        if(tree==null) return 0;
        int res = 0;
        for(int i=0;i<tree.friends.size();i++){
            if(tree.friends.get(i)==parent) continue;
            if(tree.colors.get(i)==color) {
                if(color=='R')
                    res = Math.max(res,dfs(tree.friends.get(i),tree,'B')+1);
                else
                    res = Math.max(res,dfs(tree.friends.get(i),tree,'R')+1);
            }
        }
        return res;
    }

}

Python

from collections import defaultdict

MAXN = 200005
n = 0
edge = defaultdict(list)
dp = [[0] * 2 for _ in range(MAXN)]
maxn = 0


def dfs(u, fa):
    global maxn
    if len(edge[u]) == 1 and edge[u][0][0] == fa:
        return

    for now in edge[u]:
        v = now[0]
        if v == fa:
            continue
        dfs(v, u)
        col = now[1]
        dp[u][col] = max(dp[u][col], dp[v][col ^ 1] + 1)
        maxn = max(maxn, dp[u][0] + dp[u][1])


def main():
    global n
    n = int(input())
    for _ in range(n - 1):
        u, v, ch = input().split()
        u, v = int(u), int(v)
        edge[u].append((v, 1 if ch == 'R' else 0))
        edge[v].append((u, 1 if ch == 'R' else 0))

    dfs(1, 0)
    print(maxn)


if __name__ == "__main__":
    main()

**************

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

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

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