✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

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

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

钉钉

题目一：小兰的窗景设计

1️⃣：理解屏幕与画作的比例关系，判断缩放策略

2️⃣：计算透明区域比例并化简为最简分数形式

难度：中等

这道题目的核心在于理解比例匹配和缩放策略。通过比较 和 的大小关系，确定是按宽度还是按高度缩放，从而计算出透明区域的占比。使用最大公约数进行分数化简，实现 的高效解法。

题目二：小毛的智能监控系统

1️⃣：预处理每个位置在四个方向上的员工检测状态

2️⃣：通过四次线性扫描避免对每个摄像头单独搜索

难度：中等

这道题目结合了矩阵处理和预处理优化技巧。关键在于避免对每个摄像头进行四方向搜索的暴力做法，而是通过预处理得到每个位置在各方向的检测结果。时间复杂度从 优化到 。

题目三：小柯的学习讨论分析

1️⃣：实现字符串中用户名的精确匹配检测

2️⃣：使用动态规划思想计算最长对话序列长度

难度：中等偏难

这道题目涉及字符串处理和动态规划。难点在于正确实现提及检测的边界条件判断，以及理解对话序列的递推关系。通过状态转移 dp[i] = mention(i, i-1) ? dp[i-1]+1 : 1 来维护最长序列长度。

01. 小兰的窗景设计

问题描述

小兰是一位著名的室内设计师，她正在为一位客户设计房间的落地窗。客户希望在落地窗上安装一幅定制的艺术玻璃画，这幅画需要完整地展示在窗户上，不能被裁剪或变形。

落地窗的尺寸比例为 （宽度与高度的比例），而艺术玻璃画的尺寸比例为 。为了保持画作的完整性和美观，小兰只能等比例缩放画作，不能旋转或裁剪。

当画作的比例与窗户比例不完全匹配时，窗户的部分区域将保持透明（无法被画作覆盖）。小兰需要计算：在最佳缩放方案下，透明区域占整个窗户的比例是多少？

输入格式

第一行包含四个正整数 ，其中：

• 表示落地窗的宽高比例为

• 表示艺术玻璃画的宽高比例为

输出格式

一个最简分数 ，表示透明区域占整个窗户的比例。

如果画作完全填充窗户（无透明区域），输出 。

样例输入

1 1 3 2

1 1 1 1

样例输出

1/3

0/1

样例	解释说明
样例1	正方形窗户（）安装 的画作，按高度缩放后宽度不足，透明区域比例为
样例2	正方形窗户安装正方形画作，完全匹配，无透明区域

数据范围

题解

这道题的核心在于理解缩放策略和比例计算。

设窗户的宽高比为 ，画作的宽高比为 。为了保持画作完整，我们需要选择合适的缩放策略：

1. 比例匹配判断：比较 和 的大小关系

   • 如果 ，说明两个比例完全相同，画作可以完全填充窗户
   • 否则，需要选择适当的缩放策略

2. 缩放策略选择：

   • 如果 ，说明窗户相对"更宽"，应该按窗户的高度来缩放画作
   • 如果 ，说明窗户相对"更窄"，应该按窗户的宽度来缩放画作

3. 透明区域计算：

   • 情况1：按高度缩放时，透明区域比例为
   • 情况2：按宽度缩放时，透明区域比例为

4. 分数化简：使用最大公约数对分子分母进行约分

时间复杂度 ，主要耗时在计算最大公约数。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

def gcd(a, b):
    """计算最大公约数"""
    while b:
        a, b = b, a % b
    return a

def solve():
    w, h, p, q = map(int, input().split())
    
    # 计算关键值用于比较
    left = w * q   # 窗户宽度 * 画作高度
    right = h * p  # 窗户高度 * 画作宽度
    
    # 完全匹配的情况
    if left == right:
        print("0/1")
        return
    
    # 计算透明区域的分子分母
    if left > right:
        # 窗户相对更宽，按高度缩放
        num = left - right
        den = left
    else:
        # 窗户相对更窄，按宽度缩放
        num = right - left  
        den = right
    
    # 约分到最简形式
    g = gcd(num, den)
    print(f"{num // g}/{den // g}")

solve()

• Cpp

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

ll gcd_func(ll a, ll b) {
    // 计算最大公约数
    return b ? gcd_func(b, a % b) : a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll w, h, p, q;
    cin >> w >> h >> p >> q;
    
    // 计算比较用的关键值
    ll val1 = w * q;  // 窗户宽 * 画作高
    ll val2 = h * p;  // 窗户高 * 画作宽
    
    if (val1 == val2) {
        // 比例完全匹配
        cout << "0/1\n";
        return 0;
    }
    
    ll num, den;
    if (val1 > val2) {
        // 窗户更宽，按高度适配
        num = val1 - val2;
        den = val1;
    } else {
        // 窗户更窄，按宽度适配  
        num = val2 - val1;
        den = val2;
    }
    
    // 化简分数
    ll g = gcd_func(num, den);
    cout << num / g << "/" << den / g << "\n";
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    // 计算最大公约数
    static long gcdCalc(long a, long b) {
        return b == 0 ? a : gcdCalc(b, a % b);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        long w = sc.nextLong();  // 窗户宽度比例
        long h = sc.nextLong();  // 窗户高度比例  
        long p = sc.nextLong();  // 画作宽度比例
        long q = sc.nextLong();  // 画作高度比例
        
        // 计算关键判断值
        long leftVal = w * q;   // 窗户宽 * 画作高
        long rightVal = h * p;  // 窗户高 * 画作宽
        
        if (leftVal == rightVal) {
            // 比例完全相同，无透明区域
            System.out.println("0/1");
            return;
        }
        
        long numerator, denominator;
        if (leftVal > rightVal) {
            // 窗户相对更宽
            numerator = leftVal - rightVal;
            denominator = leftVal;
        } else {
            // 窗户相对更窄
            numerator = rightVal - leftVal;
            denominator = rightVal;
        }
        
        // 约分处理
        long gcdVal = gcdCalc(numerator, denominator);
        System.out.println((numerator / gcdVal) + "/" + (denominator / gcdVal));
        
        sc.close();
    }
}

02. 小毛的智能监控系统

问题描述

小毛负责管理一座现代化办公楼的智能监控系统。这座办公楼被划分为一个矩形网格，每个网格位置要么安装了监控摄像头，要么是员工的工作区域。

监控摄像头具有特殊的智能识别功能：每个摄像头可以向上、下、左、右四个方向进行人员检测。如果某个方向上存在至少一名员工，该摄像头在这个方向上就会获得 个检测积分。

作为系统管理员，小毛需要评估当前监控布局的效果。他想知道：所有摄像头的检测积分总和是多少？

输入格式

第一行包含两个正整数 （），分别表示办公楼网格的行数和列数。

接下来 行，每行包含 个整数 ，表示网格的布局：

• 表示该位置安装了监控摄像头

• 表示该位置是员工工作区域

输出格式

一个正整数，表示所有监控摄像头的检测积分总和。

样例输入

2 4
0 1 0 0
1 0 1 0

样例输出

9

样例	解释说明
样例1	位置 的摄像头：向右、向下检测到员工，得 分 位置 的摄像头：向左、向下检测到员工，得 分 位置 的摄像头：向左检测到员工，得 分 位置 的摄像头：向左、向右、向上检测到员工，得 分 位置 的摄像头：向左检测到员工，得 分 总计： 分

数据范围

题解

这道题需要为每个摄像头统计四个方向上是否存在员工。直接的想法是对每个摄像头向四个方向搜索，但这样时间复杂度会达到 ，可能会超时。

更高效的做法是预处理每个位置在四个方向上是否存在员工：

1. 从左到右扫描：对于每一行，记录到当前位置左侧是否出现过员工
2. 从右到左扫描：对于每一行，记录到当前位置右侧是否出现过员工
3. 从上到下扫描：对于每一列，记录到当前位置上方是否出现过员工
4. 从下到上扫描：对于每一列，记录到当前位置下方是否出现过员工

通过四次遍历，我们可以得到四个布尔矩阵，分别表示每个位置在对应方向是否能检测到员工。

最后遍历所有摄像头位置，累加其四个方向的检测积分即可。

时间复杂度：，空间复杂度：。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

def solve():
    n, m = map(int, input().split())
    grid = []
    for _ in range(n):
        row = list(map(int, input().split()))
        grid.append(row)
    
    # 预处理四个方向的员工检测结果
    left = [[False] * m for _ in range(n)]   # 左侧是否有员工
    right = [[False] * m for _ in range(n)]  # 右侧是否有员工
    up = [[False] * m for _ in range(n)]     # 上方是否有员工
    down = [[False] * m for _ in range(n)]   # 下方是否有员工
    
    # 处理左右方向
    for i in range(n):
        # 从左到右：检查左侧是否有员工
        has_emp = False
        for j in range(m):
            left[i][j] = has_emp
            if grid[i][j] == 1:
                has_emp = True
        
        # 从右到左：检查右侧是否有员工  
        has_emp = False
        for j in range(m-1, -1, -1):
            right[i][j] = has_emp
            if grid[i][j] == 1:
                has_emp = True
    
    # 处理上下方向
    for j in range(m):
        # 从上到下：检查上方是否有员工
        has_emp = False
        for i in range(n):
            up[i][j] = has_emp
            if grid[i][j] == 1:
                has_emp = True
        
        # 从下到上：检查下方是否有员工
        has_emp = False
        for i in range(n-1, -1, -1):
            down[i][j] = has_emp
            if grid[i][j] == 1:
                has_emp = True
    
    # 统计所有摄像头的积分
    total = 0
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 0:  # 摄像头位置
                score = int(left[i][j]) + int(right[i][j]) + int(up[i][j]) + int(down[i][j])
                total += score
    
    print(total)

solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n