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

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

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

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

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

🍒 本专栏已收集 70+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🧩 备战秋招还没订阅的朋友们可以冲一下啦，当试题收集至 100 套后，价格会进行一波调整~

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🪔美团秋招第三场莱拉！！！

🍥 本次后两题难度较大，对数据结构的要求较高

1️⃣ 打卡题，原题的描述有点问题

2️⃣ 枚举+贪心，难度不大

3️⃣ 小学数学题，分情况讨论即可

4️⃣ LCA + st表，难度较大

5️⃣ 线段树处理区间最值+单点修改

🍥 01.视频分辨率评级系统

问题描述

LYA 是一家视频网站的技术负责人，她正在开发一个视频分辨率评级系统。该系统根据视频的长度和宽度（以像素为单位）来确定视频的清晰度等级。具体的评级标准如下：

• 如果长和宽低于 360 像素，视频被认为是损坏的，系统应输出 "break"。
• 长和宽不低于 360 像素，视频被评为 "360P"。
• 长和宽不低于 480 像素，视频被评为 "480P"。
• 长和宽不低于 720 像素，视频被评为 "720P"。
• 长和宽不低于 1080 像素，视频被评为 "1080P"。
• 长和宽不低于 2160 像素，视频被评为 "4K"。

LYA 需要你帮忙编写一个程序，快速判断给定视频的最高分辨率等级。

输入格式

第一行输入一个整数 ，表示需要评级的视频数量。

接下来的 行，每行包含两个整数 和 ，分别表示视频的高度和宽度（以像素为单位）。

输出格式

对于每个视频，输出一行字符串，表示该视频能够达到的最高分辨率等级。

样例输入

2
1080 1960
500 2170

样例输出

1080P
480P

样例解释

对于第一个视频，其高度为 1080 像素，宽度为 1960 像素。根据评级标准，这个视频可以达到 1080P 的分辨率等级。

对于第二个视频，虽然其宽度达到了 2170 像素，但高度只有 500 像素。根据评级标准，我们需要考虑较小的那个维度，因此这个视频的最高分辨率等级为 480P。

数据范围

题解

签到题，原题的题意说的或有点问题，实际要写与的逻辑才是对的，这点看样例能看出里

按照题意模拟就可以了

参考代码

• Python

import sys

def get_resolution(h: int, w: int) -> str:
    """
    根据屏幕高度和宽度判断清晰度等级
    :param h: 屏幕高度
    :param w: 屏幕宽度
    :return: 清晰度等级
    """
    if h >= 2160 and w >= 2160:
        return "4K"
    elif h >= 1080 and w >= 1080:
        return "1080P"
    elif h >= 720 and w >= 720:
        return "720P"
    elif h >= 480 and w >= 480:
        return "480P"
    elif h >= 360 and w >= 360:
        return "360P"
    else:
        return "break"

def main():
    """
    主函数：处理输入输出
    """
    input = sys.stdin.read
    data = input().split()
    
    T = int(data[0])  # 读取放映厅数量
    index = 1
    results = []
    
    for _ in range(T):
        h = int(data[index])
        w = int(data[index + 1])
        index += 2
        result = get_resolution(h, w)
        results.append(result)
    
    print("\n".join(results))  # 输出结果

if __name__ == "__main__":
    main()

• Java

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

public class Main {
    
    /**
     * 判断视频分辨率等级
     * @param h 视频高度
     * @param w 视频宽度
     * @return 分辨率等级
     */
    public static String getResolution(int h, int w) {
        if (h >= 2160 && w >= 2160) {
            return "4K";
        } else if (h >= 1080 && w >= 1080) {
            return "1080P";
        } else if (h >= 720 && w >= 720) {
            return "720P";
        } else if (h >= 480 && w >= 480) {
            return "480P";
        } else if (h >= 360 && w >= 360) {
            return "360P";
        } else {
            return "break";
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 读取测试用例数量
        
        ArrayList<String> results = new ArrayList<>();
        
        for (int i = 0; i < T; i++) {
            int h = scanner.nextInt(); // 读取视频高度
            int w = scanner.nextInt(); // 读取视频宽度
            String result = getResolution(h, w);
            results.add(result);
        }
        
        // 输出结果
        for (String result : results) {
            System.out.println(result);
        }
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

/**
 * 判断视频分辨率等级
 * @param h 视频高度
 * @param w 视频宽度
 * @return 分辨率等级
 */
string getResolution(int h, int w) {
    if (h >= 2160 && w >= 2160) {
        return "4K";
    } else if (h >= 1080 && w >= 1080) {
        return "1080P";
    } else if (h >= 720 && w >= 720) {
        return "720P";
    } else if (h >= 480 && w >= 480) {
        return "480P";
    } else if (h >= 360 && w >= 360) {
        return "360P";
    } else {
        return "break";
    }
}

int main() {
    int T;
    cin >> T; // 读取测试用例数量
    
    vector<string> results;
    
    for (int i = 0; i < T; i++) {
        int h, w;
        cin >> h >> w; // 读取视频高度和宽度
        string result = getResolution(h, w);
        results.push_back(result);
    }
    
    // 输出结果
    for (const string& result : results) {
        cout << result << endl;
    }
    
    return 0;
}

🪣 02.K小姐的快递配送

问题描述

K小姐是一名快递配送员，她每天都需要在城市中穿梭，将包裹送到指定地点。城市可以看作是一个二维平面，K小姐的初始位置为 ，而公司的仓库位置为 。

今天，K小姐需要配送 个包裹，每个包裹的位置为 。K小姐每次可以向上、下、左、右移动一个单位距离，每次移动的体力消耗为1。她每次只能携带一个包裹，必须先移动到包裹所在位置，然后将包裹送到仓库 。

K小姐想知道，要将所有包裹送到仓库，她最少需要消耗多少体力？

输入格式

第一行：四个整数 ，表示K小姐的初始位置和仓库位置。

第二行：一个整数 ，表示包裹的数量。

接下来 行：每行两个整数 ，表示第 个包裹的位置。

输出格式

输出一个整数，表示K小姐最少需要消耗的体力值。

样例输入

0 0 1 1
2
1 0
2 2

样例输出

6

样例解释

K小姐的最优配送路线如下：

1. 从 (0,0) 移动到 (1,0)，拿起包裹，移动到 (1,1)，放下包裹。体力消耗为2。
2. 从 (1,1) 移动到 (2,2)，拿起包裹，移动到 (1,1)，放下包裹。体力消耗为4。 总体力消耗：2 + 4 = 6。

数据范围

题解

贪心，找出第一个包裹该拿哪个

对于每个包裹，我们计算两个值：

1. 直接配送的成本
2. 顺路配送的额外成本。

直接配送成本是从当前位置到包裹位置再到仓库的距离。

顺路配送的额外成本是直接配送成本减去从初始位置到包裹位置的距离。

参考代码

• Python

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

res = 0  # 总体力消耗
z = 0    # 最大节省量

# 遍历每个包裹
for _ in range(n):
    x, y = map(int, input().split())
    
    # 计算直接配送成本
    k = (abs(c - x) + abs(d - y)) * 2
    
    # 计算并更新最大节省量
    z = max(z, k - (abs(a - x) + abs(b - y) + abs(c - x) + abs(d - y)))
    
    res += k  # 累加直接配送成本

# 输出结果
print(res - z)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取初始位置和仓库位置
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        long c = scanner.nextLong();
        long d = scanner.nextLong();
        
        int n = scanner.nextInt();
        long res = 0;  // 总体力消耗
        long z = 0;    // 最大节省量
        
        // 遍历每个包裹
        for (int i = 0; i < n; i++) {
            long x = scanner.nextLong();
            long y = scanner.nextLong();
            
            // 计算直接配送成本
            long k = (Math.abs(c - x) + Math.abs(d - y)) * 2;
            
            // 计算并更新最大节省量
            z = Math.max(z, k - (Math.abs(a - x) + Math.abs(b - y) + Math.abs(c - x) + Math.abs(d - y)));
            
            res += k;  // 累加直接配送成本
        }
        
        // 输出结果
        System.out.println(res - z);
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    LL a, b, c, d;
    cin >> a >> b >> c >> d;
    
    int n;
    cin >> n;
    
    LL res = 0;  // 总体力消耗
    LL z = 0;    // 最大节省量
    
    // 遍历每个包裹
    for (int i = 0; i < n; i++) {
        LL x, y;
        cin >> x >> y;
        
        // 计算直接配送成本
        LL k = (llabs(c - x) + llabs(d - y)) * 2;
        
        // 计算并更新最大节省量
        z = max(z, k - (llabs(a - x) + llabs(b - y) + llabs(c - x) + llabs(d - y)));
        
        res += k;  // 累加直接配送成本
    }
    
    // 输出结果
    cout << res - z << "\n";
    
    return 0;
}

📫 03.魔法花园的最佳收成

问题描述

K小姐是一位魔法园丁，她的花园里有三种神奇的魔法植物，分别记为 、 和 。这些植物每天都会产生魔法能量。K小姐每天可以对其中一株植物施加特殊的魔法肥料，使其魔法能量增加1点。她最多可以使用 次魔法肥料。

K小姐想知道，在最多使用 次魔法肥料的情况下，她能获得的最大魔法能量乘积（即 ）是多少？

输入格式

一行四个正整数 、、 和 （），分别表示三种魔法植物的初始能量值和可使用的魔法肥料次数。

输出格式

输出一个整数，表示K小姐能获得的最大魔法能量乘积。

样例输入

1 2 3 1

样例输出

12

样例解释

K小姐选择对初始能量为1的植物使用一次魔法肥料，使其能量变为2。此时三株植物的能量为 [2, 2, 3]，乘积为12，这是最大可能的乘积。

数据范围

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

题解

贪心

应该优先提升能量较低的植物，使三株植物的能量尽可能接近。

具体步骤如下：

1. 首先将三个数排序。
2. 尝试将最小的数提升到第二小的数的水平。
3. 如果还有剩余操作次数，尝试将两个较小的数提升到最大数的水平。
4. 如果仍有剩余操作次数，平均分配给三株植物。

参考代码

• Python

# 读取输入
a, b, c, k = map(int, input().split())
MOD = 10**9 + 7

# 将三个数排序
nums = sorted([a, b, c])

# 计算最大乘积
def max_product(nums, k):
    # 尝试将最小的数提升到第二小的数的水平
    diff = nums[1] - nums[0]
    if k >= diff:
        nums[0] = nums[1]
        k -= diff
        
        # 尝试将两个较小的数提升到最大数的水平
        diff = nums[2] - nums[1]
        if k >= 2 * diff:
            k -= 2 * diff
            nums[0] = nums[1] = nums[2]
            
            # 平均分配剩余的操作次数
            inc = k // 3
            k %= 3
            for i in range(3):
                nums[i] += inc
                if i < k:
                    nums[i] += 1
        else:
            # 平均分配剩余的操作次数给两个较小的数
            inc = k // 2
            k %= 2
            for i in range(2):
                nums[i] += inc
                if i < k:
                    nums[i] += 1
    else:
        # 所有操作都用于提升最小的数
        nums[0] += k
    
    # 计算乘积并取模
    result = 1
    for num in nums:
        result = (result * num) % MOD
    
    return result

# 输出结果
print(max_product(nums, k))

• Java

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

public class Main {
    private static final long MOD = 1000000007;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        long c = scanner.nextLong();
        long k = scanner.nextLong();
        scanner.close();

        long[] nums = {a, b, c};
        Arrays.sort(nums);

        System.out.println(maxProduct(nums, k));
    }

    private static long maxProduct(long[] nums, long k) {
        // 尝试将最小的数提升到第二小的数的水平
        long diff = nums[1] - nums[0];
        if (k >= diff) {
            nums[0] = nums[1];
            k -= diff;

            // 尝试将两个较小的数提升到最大数的水平
            diff = nums[2] - nums[1];
            if (k >= 2 * diff) {
                k -= 2 * diff;
                nums[0] = nums[1] = nums[2];

                // 平均分配剩余的操作次数
                long inc = k / 3;
                k %= 3;
                for (int i = 0; i < 3; i++) {
                    nums[i] += inc;
                    if (i < k) nums[i]++;
                }
            } else {
                // 平均分配剩余的操作次数给两个较小的数
                long inc = k / 2;
                k %= 2;
                for (int i = 0; i < 2; i++) {
                    nums[i] += inc;
                    if (i < k) nums[i]++;
                }
            }
        } else {
            // 所有操作都用于提升最小的数
            nums[0] += k;
        }

        // 计算乘积并取模
        long result = 1;
        for (long num : nums) {
            result = (result * num) % MOD;
        }

        return result;
    }
}

• Cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const long long MOD = 1e9 + 7;

// 计算最大乘积
long long maxProduct(vector<long long>& nums, long long k) {
    // 尝试将最小的数提升到第二小的数的水平
    long long diff = nums[1] - nums[0];
    if (k >= diff) {
        nums[0] = nums[1];
        k -= diff;
        
        // 尝试将两个较小的数提升到最大数的水平
        diff = nums[2] - nums[1];
        if (k >= 2 * diff) {
            k -= 2 * diff;
            nums[0] = nums[1] = nums[2];
            
            // 平均分配剩余的操作次数
            long long inc = k / 3;
            k %= 3;
            for (int i = 0; i < 3; ++i) {
                nums[i] += inc;
                if (i < k) ++nums[i];
            }
        } else {
            // 平均分配剩余的操作次数给两个较小的数
            long long inc = k / 2;
            k %= 2;
            for (int i = 0; i < 2; ++i) {
                nums[i] += inc;
                if (i < k) ++nums[i];
            }
        }
    } else {
        // 所有操作都用于提升最小的数
        nums[0] += k;
    }
    
    // 计算乘积并取模
    long long result = 1;
    for (int i = 0; i < 3; ++i) {
        result = (result * nums[i]) % MOD;
    }
    
    return result;
}

int main() {
    long long a, b, c, k;
    cin >> a >> b >> c >> k;
    
    vector<long long> nums = {a, b, c};
    sort(nums.begin(), nums.end());
    
    cout << maxProduct(nums, k) << endl;
    
    return 0;
}

🥦 04.魔法森林的秘密通道

问题描述

K小姐是一位魔法森林的守护者。她负责管理一片由 棵魔法树组成的森林，这些树通过魔法藤蔓相连，形成了一个树状结构,根节点为1号树。每棵树都有一个独特的魔法等级，用 表示， 数组由 组成,且任意两棵树的魔法等级都不同。

K小姐获得了一次使用"秘密通道"魔法的机会。她可以选择任意两棵不同的树 和 ，在它们之间创建一条秘密通道(即使它们之间已经存在魔法藤蔓连接)。

创建秘密通道后,森林中会形成一个唯一的魔法环。这个魔法环的能量值定义为

其中 表示环中所有树的魔法等级中未出现的最小非负整数。K小姐的目标是最大化这个魔法环的能量值。

输入格式

第一行一个整数 ，表示魔法森林中树的数量。

第二行 个整数,第 个数为 ，表示每棵树的魔法等级。

接下来 行,每行 2 个数 ，表示树 和树 之间存在一条魔法藤蔓连接。

数据保证输入的是一个树状结构。

输出格式

输出一个整数,表示K小姐能创造的魔法环的最大能量值。

样例输入

6
0 3 2 1 4 5
1 2
1 3
2 4
2 5
5 6

样例输出

4

样例解释

初始的魔法森林结构如下：

    0
   / \
  3   2
 / \
1   4
   /
  5

       0 (1号节点)
      /         \
 3 (2号节点)   2 (3号节点)
    /     \
1 (4号节点) 4 (5号节点)
              /
         5 (6号节点)

K小姐可以在树3和树4之间创建秘密通道,形成魔法环 {0, 2, 1, 3}。这个魔法环的能量值为 ,这是可能获得的最大能量值。

数据范围

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

题解

显然可以发现，我们可以选择一条链把它两端相连作为环，而这条链上必须又有值为 0 的点。

我们将值为 0 的点作为根，可以发现，一条合法的链，一定是从 0 节点连出来的两条链或一条链合起来作为答案。

使用 LCA 判断新的 值的点是否在两条链上并动态维护两条链即可。

复杂度

参考代码

• Python

import sys
sys.setrecursionlimit(10**6)

class LCA:
    def __init__(self, n):
        self.n = n
        self.log = 20
        self.depth = [0] * (n + 1)
        self.parent = [[0] * (n + 1) for _ in range(self.log)]
        self.tin = [0] * (n + 1)
        self.tout = [0] * (n + 1)
        self.timer = 0

    def dfs(self, v, p, adj):
        # DFS遍历,记录每个节点的访问时间和父节点
        self.tin[v] = self.timer
        self.timer += 1
        self.parent[0][v] = p
        for i in range(1, self.log):
            self.parent[i][v] = self.parent[i-1][self.parent[i-1][v]]
        for u in adj[v]:
            if u != p:
                self.depth[u] = self.depth[v] + 1
                self.dfs(u, v, adj)
        self.tout[v] = self.timer
        self.timer += 1

    def is_ancestor(self, u, v):
        # 判断u是否是v的祖先
        return self.tin[u] <= self.tin[v] and self.tout[u] >= self.tout[v]

    def lca(self, u, v):
        # 查找u和v的最近公共祖先
        if self.is_ancestor(u, v):
            return u
        if self.is_ancestor(v, u):
            return v
        for i in range(self.log - 1,