🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 编程一对一辅导

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🌰 明晚又有米哈游的笔试题啦，我们来看看去年校招米哈游真题卷的难度怎么样

💡

🥇 第一题比较打卡，进行简单的分类讨论就好

🥈 第二题是一个模拟题，对每个位置标记后枚举，也不难

🥉 第三题是笔试常驻嘉宾，树形DP，建议大家好好掌握

✈️ 01.花店老板LYA

问题描述

LYA 是一位热爱园艺的花店老板。她的花店里有 盆红玫瑰、 盆白玫瑰和 盆神奇的变色玫瑰。LYA 想要制作情侣花束，每个花束需要 2 朵红玫瑰和 2 朵白玫瑰。神奇的变色玫瑰可以变成红玫瑰或白玫瑰。LYA 希望能制作尽可能多的情侣花束，请帮她计算最多能制作多少个花束。

输入格式

输入包含三个用空格隔开的整数 ，分别表示红玫瑰、白玫瑰和变色玫瑰的数量。

输出格式

输出一个整数，表示 LYA 最多能制作的情侣花束数量。

样例输入

3 3 3

样例输出

2

数据范围

对于所有测试数据，保证 。

题解

本题的关键在于理解变色玫瑰的作用和如何最优地分配资源。可以按以下步骤思考：

1. 首先，我们应该尽可能使用已有的红玫瑰和白玫瑰。
2. 如果红玫瑰和白玫瑰数量相等，那么我们可以直接用它们制作花束，然后用变色玫瑰补充。
3. 如果红玫瑰和白玫瑰数量不相等，我们需要用变色玫瑰来平衡它们的差异。

具体算法如下：

1. 计算红玫瑰和白玫瑰数量的差值的绝对值 。
2. 如果 ，说明变色玫瑰不足以平衡差异，此时最多能制作的花束数量为 。
3. 如果 ，说明变色玫瑰足够平衡差异并有剩余，此时最多能制作的花束数量为 。

时间复杂度： 空间复杂度：

参考代码

• Python

# 读取输入
a, b, c = map(int, input().split())

# 计算红玫瑰和白玫瑰的数量差
diff = abs(a - b)

# 计算最多能制作的花束数量
if diff >= c:
    # 变色玫瑰不足以平衡差异
    count = (min(a, b) + c) // 2
else:
    # 变色玫瑰足够平衡差异并有剩余
    count = ((c - diff) // 2 + max(a, b)) // 2

# 输出结果
print(count)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建Scanner对象读取输入
        Scanner scanner = new Scanner(System.in);
        
        // 读取红玫瑰、白玫瑰和变色玫瑰的数量
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();
        
        // 计算红玫瑰和白玫瑰的数量差
        int diff = Math.abs(a - b);
        
        // 计算最多能制作的花束数量
        int count;
        if (diff >= c) {
            // 变色玫瑰不足以平衡差异
            count = (Math.min(a, b) + c) / 2;
        } else {
            // 变色玫瑰足够平衡差异并有剩余
            count = ((c - diff) / 2 + Math.max(a, b)) / 2;
        }
        
        // 输出结果
        System.out.println(count);
    }
}

• Cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    // 声明变量存储红玫瑰、白玫瑰和变色玫瑰的数量
    int a, b, c;
    
    // 读取输入
    cin >> a >> b >> c;
    
    // 计算红玫瑰和白玫瑰的数量差
    int diff = abs(a - b);
    
    // 计算最多能制作的花束数量
    int count;
    if (diff >= c) {
        // 变色玫瑰不足以平衡差异
        count = (min(a, b) + c) / 2;
    } else {
        // 变色玫瑰足够平衡差异并有剩余
        count = ((c - diff) / 2 + max(a, b)) / 2;
    }
    
    // 输出结果
    cout << count << endl;
    
    return 0;
}

🛫 02.特殊的网格

问题描述

K小姐是一位园艺爱好者，她正在设计一个方形花园。这个花园被划分为 的网格，每个格子可以种植一朵花或保持空置。K小姐已经在某些格子里种下了一些珍稀的花朵，现在她想再种一朵特殊的花，但需要确保这朵花与已种植的花朵之间不会相互影响。

两朵花会相互影响，如果它们在同一行、同一列，或者在同一条对角线上。K小姐想知道，在不影响已有花朵的前提下，还有多少个位置可以种植这朵特殊的花。

输入格式

第一行包含一个正整数 ，表示花园的大小。

接下来 行，每行包含一个长度为 的字符串，由字符 . 和 * 组成，* 表示已种植的花朵，. 表示空置的格子。

输出格式

输出一个整数，表示可以种植特殊花朵的位置数量。

样例输入

3
.*.
...
...

样例输出

2

数据范围

对于所有测试数据，保证已种植的花朵之间不会相互影响，且 。

题解

解题步骤如下：

1. 使用四个数组或集合来标记已被占用的行、列和两个方向的对角线。

2. 遍历整个花园，对于每朵已种植的花：

   • 标记其所在的行和列
   • 标记其所在的两条对角线（可以用 和 来表示）

3. 再次遍历整个花园，统计既没有被行标记，也没有被列标记，同时两个对角线也没有被标记的位置数量。

时间复杂度分析：需要遍历两次花园，每次遍历的时间复杂度为 ，因此总的时间复杂度为 。

空间复杂度分析：使用了四个长度为 或 的数组或集合来存储标记，因此空间复杂度为 。

参考代码

• Python

def count_planting_positions(n, garden):
    # 初始化标记数组
    row = [False] * n
    col = [False] * n
    diag1 = [False] * (2 * n - 1)
    diag2 = [False] * (2 * n - 1)

    # 标记已种植花朵的位置
    for i in range(n):
        for j in range(n):
            if garden[i][j] == '*':
                row[i] = True
                col[j] = True
                diag1[i + j] = True
                diag2[i - j + n - 1] = True

    # 统计可种植位置
    count = 0
    for i in range(n):
        for j in range(n):
            if not (row[i] or col[j] or diag1[i + j] or diag2[i - j + n - 1]):
                count += 1

    return count

# 读取输入
n = int(input())
garden = [input() for _ in range(n)]

# 计算并输出结果
result = count_planting_positions(n, garden)
print(result)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符

        char[][] garden = new char[n][n];
        for (int i = 0; i < n; i++) {
            garden[i] = scanner.nextLine().toCharArray();
        }

        System.out.println(countPlantingPositions(n, garden));
    }

    public static int countPlantingPositions(int n, char[][] garden) {
        boolean[] row = new boolean[n];
        boolean[] col = new boolean[n];
        boolean[] diag1 = new