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

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

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

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

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

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

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

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

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

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

🍥 本次前四题较为简单，最后一题很容易想，但要注意细节

1️⃣ 打卡题，距离/速度=时间

2️⃣ 字符串模拟题，判断首字母是否大写

3️⃣ 二分，但要注意先排序

4️⃣ 非常经典的计数类dp

5️⃣ 区间查询最值，可以用 rmq/线段树，

🚙 01.赛车追逐

问题描述

LYA 是一位赛车爱好者，她正在观看一场精彩的赛车比赛。比赛中有两辆赛车，分别由 K 小姐和 A 先生驾驶。两辆赛车起初并排站在起跑线上，但它们的赛道长度不同。K 小姐的赛道长度为 ，A 先生的赛道长度为 ，且 。两辆赛车的速度分别为 和 。

比赛开始后，两辆赛车同时出发。LYA 想知道，当两辆赛车再次并排（即车头对齐）时，比赛已经进行了多长时间。

输入格式

第一行输入一个整数 （），表示测试数据的组数。

接下来的 行，每行包含四个整数 、、、（，），分别表示两条赛道的长度和两辆赛车的速度。

输出格式

对于每组测试数据，输出一行，包含一个实数，表示两辆赛车再次并排时所经过的时间。

输出的实数与标准答案的相对误差或绝对误差不超过 时，视为正确。

样例输入

1
4 2 1 2

样例输出

2.00

数据范围

题解

1. 计算两条赛道的长度差：
2. 计算两辆赛车的速度差：
3. 使用距离除以速度得到时间：

参考代码

• Python

# 读取测试用例数量
T = int(input())

# 处理每个测试用例
for _ in range(T):
    # 读取输入数据
    d1, d2, v1, v2 = map(int, input().split())
    
    # 计算赛道长度差
    d = d1 - d2
    
    # 计算速度差的绝对值
    v = abs(v1 - v2)
    
    # 计算时间并输出结果
    result = d / v
    print(f"{result:.6f}")

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取测试用例数量
        int T = scanner.nextInt();
        
        // 处理每个测试用例
        for (int i = 0; i < T; i++) {
            // 读取输入数据
            int d1 = scanner.nextInt();
            int d2 = scanner.nextInt();
            int v1 = scanner.nextInt();
            int v2 = scanner.nextInt();
            
            // 计算赛道长度差
            int d = d1 - d2;
            
            // 计算速度差的绝对值
            int v = Math.abs(v1 - v2);
            
            // 计算时间并输出结果
            double result = (double) d / v;
            System.out.printf("%.6f\n", result);
        }
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

int main() {
    int T;
    cin >> T;  // 读取测试用例数量
    
    while (T--) {
        int d1, d2, v1, v2;
        cin >> d1 >> d2 >> v1 >> v2;  // 读取输入数据
        
        int d = d1 - d2;  // 计算赛道长度差
        int v = abs(v1 - v2);  // 计算速度差的绝对值
        
        double result = static_cast<double>(d) / v;  // 计算时间
        
        cout << fixed << setprecision(6) << result << endl;  // 输出结果，保留6位小数
    }
    
    return 0;
}

📝 02.LYA的奇特书写习惯

问题描述

LYA是一位热爱文学的高中生，她有一个独特的习惯：喜欢将人名横向排列书写。最近，她在整理一份同学名单时，不小心将一些无关的词语混入其中。现在，她需要你的帮助来统计出实际的人名数量。

在LYA的记录中，一个有效的人名应该以大写字母开头。你的任务是编写一个程序，帮助LYA准确计算出名单中真正的人名数量。

输入格式

输入为一行，包含一个长度为 （）的字符串 。该字符串由大小写字母和空格组成，表示LYA记录的所有单词。每个单词之间用一个空格分隔。

保证字符串的开头和结尾都不是空格。

输出格式

输出一个整数，表示符合条件的人名数量。

样例输入

ABC abc Abc

样例输出

2

样例输入

A A c

样例输出

2

数据范围

• 
• 字符串 仅包含大小写英文字母和空格

题解

检查每个字母串开头是否大写

参考代码

• Python

# 读取输入字符串
s = input().strip()

# 初始化计数器
count = 0

# 遍历每个单词
for word in s.split():
    # 检查单词是否以大写字母开头
    if word[0].isupper():
        count += 1

# 输出结果
print(count)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入字符串
        String s = scanner.nextLine().trim();
        
        // 初始化计数器
        int count = 0;
        
        // 分割字符串并遍历每个单词
        for (String word : s.split("\\s+")) {
            // 检查单词是否以大写字母开头
            if (!word.isEmpty() && Character.isUpperCase(word.charAt(0))) {
                count++;
            }
        }
        
        // 输出结果
        System.out.println(count);
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int main() {
    string s;
    int count = 0;
    
    // 读取整行输入
    getline(cin, s);
    
    istringstream iss(s);
    string word;
    
    // 遍历每个单词
    while (iss >> word) {
        // 检查单词是否以大写字母开头
        if (!word.empty() && isupper(word[0])) {
            count++;
        }
    }
    
    // 输出结果
    cout << count << endl;
    
    return 0;
}

🌲 03.LYA的环保种树计划

问题描述

LYA是一位热心的环保志愿者，她计划在一条笔直的公路旁种植树木。这条公路理论上可以无限延伸，LYA招募了 位志愿者来帮助她完成这项工作。每个志愿者都站在公路旁的某个位置，并负责在自己右侧的一段区域内种树。

为了保证种植的均匀性，LYA要求每位志愿者负责的种植区域长度相同。同时，考虑到树木生长需要足够的空间，每个位置最多只能种植一棵树。LYA希望至少种植 棵树，但她也想尽可能地节约资源。

你的任务是帮助LYA计算出每位志愿者最少需要负责多长的种植区域，才能确保整个公路上至少种植 棵树。

输入格式

第一行包含两个正整数 和 （），分别表示志愿者的数量和需要种植的最少树木数量。

第二行包含 个正整数 （），表示每位志愿者在公路上的位置。

输出格式

输出一个整数，表示每位志愿者需要负责的最短种植区域长度。

样例输入

3 6
1 2 5

样例输出

3

样例解释

如果每位志愿者负责的种植区域长度为 3，那么：

• 第一位志愿者会在位置 1、2、3 种树。
• 第二位志愿者会在位置 2、3、4 种树。
• 第三位志愿者会在位置 5、6、7 种树。

由于每个位置最多种一棵树，最终在位置 1、2、3、4、5、6、7 上共有 7 棵树，满足至少种植 6 棵树的要求。

数据范围

题解

二分，注意需要先排序

a. 对志愿者的位置进行排序。 b. 设置二分查找的范围，左边界为 0，右边界为最大可能的长度（如 ）。 c. 在二分查找的每一步中：

• 计算中间值 mid。
• 检查长度为 mid 时是否能种植至少 棵树。
• 根据检查结果调整二分查找的范围。

参考代码

• Python

def check(mid, a, k, n):
    """
    检查给定的种植区域长度是否满足条件
    :param mid: 当前尝试的种植区域长度
    :param a: 志愿者的位置列表
    :param k: 需要种植的最少树木数量
    :param n: 志愿者数量
    :return: 是否满足条件
    """
    trees = 0
    for i in range(n):
        if i == 0:
            trees += mid
        else:
            trees += max(0, mid - (a[i] - a[i-1]))
        if trees >= k:
            return True
    return False

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()  # 对志愿者位置进行排序

left, right = 0, 10**6
while left < right:
    mid = (left + right) // 2
    if check(mid, a, k, n):
        right = mid
    else:
        left = mid + 1

print(left)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextLong();
        }
        Arrays.sort(a);

        long left = 0, right = 1000000;
        while (left < right) {
            long mid = (left + right) / 2;
            if (check(mid, a, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(left);
    }

    // 检查给定的种植区域长度是否满足条件
    private static boolean check(long mid, long[] a, int k, int n) {
        long trees = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                trees += mid;
            } else {
                trees += Math.max(0, mid - (a[i] - a[i-1]));
            }
            if (trees >= k) return true;
        }
        return false;
    }
}

• Cpp

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

using namespace std;

typedef long long LL;

// 检查给定的种植区域长度是否满足条件
bool check(LL mid, const vector<LL>& a, LL k, int n) {
    LL trees = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            trees += mid;
        } else {
            trees += max(0LL, mid - (a[i] - a[i-1]));
        }
        if (trees >= k) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    LL k;
    cin >> n >> k;

    vector<LL> a(n);
    for (LL& x : a) cin >> x;
    sort(a.begin(), a.end());

    LL left = 0, right = 1e6;
    while (left < right) {
        LL mid = left + (right - left) / 2;
        if (check(mid, a, k, n)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
✨
    cout << left << "\n";
    return 0;
}

✨ 04.LYA的字符串魔法

问题描述

LYA 是一位热爱魔法的少女。她最近学会了一种神奇的字符串魔法，可以从一个字符串中提取出特殊的魔法序列。这个魔法序列由字母 'r'、'e' 和 'd' 按顺序组成，被称为"红魔法"。

LYA 想知道在她的魔法字符串的所有连续子串中，一共能提取出多少个"红魔法"序列。她需要你的帮助来计算这个数量。

输入格式

输入一行，包含一个长度不超过 的字符串 ，仅由小写字母组成，代表 LYA 的魔法字符串。

输出格式

输出一个整数，表示所有子串中"红魔法"序列的总数。由于这个数可能非常大，请将结果对 取模后输出。

样例输入

redd

样例输出

3

数据范围

• 字符串长度不超过 。
• 字符串仅由小写字母组成。

题解

计数DP

定义一个数组 dp，其中 dp[i] 表示以当前字符结尾的子串中，匹配到 r、re、red 的个数。

初始化 dp[0] 为 1，表示匹配空字符串的数量。

遍历字符串中的每一个字符：

• 如果字符为 r，那么将 dp[1] 加上 dp[0]。
• 如果字符为 e，那么将 dp[2] 加上 dp[1]。
• 如果字符为 d，那么将 dp[3] 加上 dp[2]。

每次更新完 dp 后，将 dp[3] 加到结果中，表示当前可以形成的 red 的数量。

tips 注意每次 dp[0] 要 + 1

参考代码

• Python

# 读取输入的魔法字符串
s = input().strip()

# 初始化动态规划数组
dp = [1, 0, 0, 0]

# 定义模数
MOD = 10**9 + 7

# 初始化结果变量
ans = 0

# 遍历魔法字符串中的每个字符
for c in s:
    # 如果是 'd'，更新 dp[3] 和结果
    if c == 'd':
        dp[3] = (dp[3] + dp[2]) % MOD
        ans = (ans + dp[3]) % MOD
    # 如果是 'e'，更新 dp[2]
    elif c == 'e':
        dp[2] = (dp[2] + dp[1]) % MOD
    # 如果是 'r'，更新 dp[1]
    elif c == 'r':
        dp[1] = (dp[1] + dp[0]) % MOD
    
    # 增加空序列的数量
    dp[0] += 1

# 输出结果
print(ans)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入的魔法字符串
        String s = scanner.nextLine();
        
        // 初始化动态规划数组
        long[] dp = new long[4];
        dp[0] = 1;
        
        // 定义模数
        final int MOD = 1000000007;
        
        // 初始化结果变量
        long ans = 0;
        
        // 遍历魔法字符串中的每个字符
        for (char c : s.toCharArray()) {
            // 根据字符更新 dp 数组和结果
            if (c == 'd') {
                dp[3] = (dp[3] + dp[2]) % MOD;
                ans = (ans + dp[3]) % MOD;
            } else if (c == 'e') {
                dp[2] = (dp[2] + dp[1]) % MOD;
            } else if (c == 'r') {
                dp[1] = (dp[1] + dp[0]) % MOD;
            }
            
            // 增加空序列的数量
            dp[0]++;
        }
        
        // 输出结果
        System.out.println(ans);
    }
}

• Cpp

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

const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    st