✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

携程

题目一：密码编辑器

1️⃣：解析指令格式，提取操作类型和位置参数

2️⃣：按顺序执行字符大小写转换操作

难度：简单

这道题目主要考查字符串处理和指令解析。关键在于正确解析输入的指令格式，通过字符串操作提取操作类型和位置参数，然后按顺序执行大小写转换。时间复杂度为 O(n+m)，实现简单直接。

题目二：财务比例计算器

1️⃣：计算两个分数的和，得到新的分数

2️⃣：将分数化简为最简形式

3️⃣：判断分母是否只含质因子2和5

难度：中等

这道题目结合了分数运算和数论知识，需要理解有限小数的数学性质。通过最大公约数化简分数，然后检查分母的质因子分解，可以有效判断分数是否为有限小数。体现了数学理论在编程中的应用。

题目三：班级分组优化

1️⃣：按学号模m将学生分成m列

2️⃣：对每列内的能力值进行排序

3️⃣：按行重新组合，使每组最大值最小

难度：中等

这道题目考查贪心算法和数据结构运用。通过观察约束条件，发现可以将问题转化为列排序问题。关键洞察是将每列排序后按行组合，可以使每组的最大值达到全局最优，体现了贪心思想的巧妙应用。

题目四：紧急救援站布置

1️⃣：找到重点区域中距离最远的两个点（直径端点）

2️⃣：使用两次最短路算法确定重点区域直径

3️⃣：最优答案为直径长度的一半向上取整

难度：中等偏难

这道题目是经典的树上设施选址问题，需要理解树的直径概念和最短路算法。通过两次Dijkstra算法找到重点区域的直径，然后利用数学性质得出最优解。算法复杂度为 O(n log n)，是树形结构和图论算法的综合应用。

01. 密码编辑器

问题描述

小兰在开发一款智能密码编辑器，用于帮助用户调整密码格式。编辑器支持对密码中的特定字符进行大小写转换操作。

给定一个长度为 的密码字符串 （下标为 ~ ），仅由大小写字母组成。用户会进行 次编辑操作，每次操作都会立即生效：

• 指令 ""：将位置 的字符转换为对应的小写字母（如果已经是小写则保持不变）

• 指令 ""：将位置 的字符转换为对应的大写字母（如果已经是大写则保持不变）

请输出执行完所有操作后的最终密码字符串。

输入格式

第一行输入两个正整数 （），分别表示密码字符串的长度和编辑操作的次数。

第二行输入一个长度为 的字符串 ，仅由大小写字母组成，表示初始密码。

接下来 行，每行输入一个编辑指令，格式为 "" 或 ""，其中 。

输出格式

输出一行字符串，表示执行完所有编辑操作后的最终密码。

样例输入

5 4
aBcDe
toLowerCase(1)
toUpperCase(4)
toUpperCase(0)
toLowerCase(2)

样例输出

AbcDE

数据范围

• 
• 

样例编号	解释说明
样例1	初始密码为"aBcDe"。执行toLowerCase(1)后变为"abcDe"；执行toUpperCase(4)后变为"abcDE"；执行toUpperCase(0)后变为"AbcDE"；执行toLowerCase(2)后字符c本就是小写，密码保持"AbcDE"

题解

这道题目的核心是字符串操作和指令解析。每次操作都是独立的，只需要按照给定的操作顺序逐一执行即可。

关键点在于正确解析输入的指令格式：

• 通过检查指令中的第2个字符来判断操作类型：'L'表示转小写，'U'表示转大写
• 提取括号中的数字作为操作位置，可以使用字符串截取的方式

具体步骤：

1. 读入初始字符串
2. 对于每个操作指令，解析出操作类型和位置
3. 根据操作类型调用相应的大小写转换函数
4. 输出最终结果

时间复杂度为 ，其中 是字符串长度， 是操作次数。由于 ，这个复杂度完全可以接受。

参考代码

• Python

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

n, m = map(int, input().split())
pwd = list(input())  # 转为字符数组便于修改

for _ in range(m):
    cmd = input()
    # 判断操作类型：第3个字符决定是L还是U
    is_lower = cmd[2] == 'L'
    # 提取括号内的数字
    start = cmd.find('(')
    end = cmd.find(')')
    pos = int(cmd[start+1:end])
    
    if is_lower:
        pwd[pos] = pwd[pos].lower()
    else:
        pwd[pos] = pwd[pos].upper()

print(''.join(pwd))

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    string pwd;
    cin >> pwd;
    
    string dummy;
    getline(cin, dummy);  // 消费换行符
    
    for (int i = 0; i < m; ++i) {
        string cmd;
        getline(cin, cmd);
        
        // 判断操作类型
        bool to_low = cmd[2] == 'L';
        // 提取位置参数
        int start = cmd.find('(');
        int end = cmd.find(')');
        int pos = stoi(cmd.substr(start + 1, end - start - 1));
        
        if (to_low) {
            pwd[pos] = tolower(pwd[pos]);
        } else {
            pwd[pos] = toupper(pwd[pos]);
        }
    }
    
    cout << pwd << "\n";
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        char[] pwd = br.readLine().toCharArray();
        
        for (int i = 0; i < m; i++) {
            String cmd = br.readLine();
            
            // 判断操作类型
            boolean toLow = cmd.charAt(2) == 'L';
            // 提取位置参数
            int start = cmd.indexOf('(');
            int end = cmd.indexOf(')');
            int pos = Integer.parseInt(cmd.substring(start + 1, end));
            
            if (toLow) {
                pwd[pos] = Character.toLowerCase(pwd[pos]);
            } else {
                pwd[pos] = Character.toUpperCase(pwd[pos]);
            }
        }
        
        System.out.println(new String(pwd));
    }
}

02. 财务比例计算器

问题描述

小基在一家财务公司负责开发比例计算器。公司经常需要计算两个比例的和，并判断结果是否可以精确表示为小数形式（而不是无限循环小数）。

给定四个正整数 ，需要计算比例 的和，并判断这个结果是否为十进制下的整数或有限小数。

有限小数定义：一个有理数被称作是十进制下的有限小数，当且仅当将其在十进制下以小数形式写出后，小数点后的位数是有限的。换句话说，存在正整数 、整数 和整数数组 （），使得该数可以表示为：

输入格式

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

接下来 行，每行输入四个正整数 （）。

输出格式

对于每组测试数据，输出一行结果。

如果 是十进制下的整数或有限小数，输出 ""，否则输出 ""。

样例输入

3
2 3 1 3
3 7 1 13
1 9 73 316

样例输出

YES
NO
YES

数据范围

• 
• 

样例编号	解释说明
样例1	，为整数，输出YES
样例2	，分母91含有质因子7和13，无法化为有限小数，输出NO
样例3	，化简后分母只含质因子2和5，可化为有限小数，输出YES

题解

这道题目的关键在于理解有限小数的数学性质。一个分数能表示为有限小数的充分必要条件是：将分数化为最简形式后，分母的质因数分解只包含2和5。

具体步骤：

1. 计算两个分数的和：
2. 将结果分数化为最简形式：设分子为 ，分母为 ，计算 ，得到最简分数
3. 检查最简分母是否只含质因子2和5：不断除以2和5，如果最终结果为1，则答案为YES；否则为NO

数学原理：十进制系统的底数是10 = 2 × 5，因此只有分母的质因子都是10的因子时，该分数才能表示为有限小数。

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

参考代码

• Python

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

T = int(input())
for _ in range(T):
    a, b, c, d = map(int, input().split())
    
    # 计算分数和
    num = a * d + b * c
    den = b * d
    
    # 化为最简分数
    g = math.gcd(num, den)
    den //= g
    
    # 检查分母是否只含质因子2和5
    while den % 2 == 0:
        den //= 2
    while den % 5 == 0:
        den //= 5
        
    if den == 1:
        print("YES")
    else:
        print("NO")

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        
        // 计算分数和
        ll num = a * d + b * c;
        ll den = b * d;
        
        // 化为最简分数
        ll g = __gcd(num, den);
        den /= g;
        
        // 检查分母是否只含质因子2和5
        while (den % 2 == 0) den /= 2;
        while (den % 5 == 0) den /= 5;
        
        cout << (den == 1 ? "YES" : "NO") << "\n";
    }
    
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            long c = Long.parseLong(st.nextToken());
            long d = Long.parseLong(st.nextToken());
            
            // 计算分数和
            long num = a * d + b * c;
            long den = b * d;
            
            // 化为最简分数
            long g = gcd(num, den);
            den /= g;
            
            // 检查分母是否只含质因子2和5
            while (den % 2 == 0) den /= 2;
            while (den % 5 == 0) den /= 5;
            
            System.out.println(den == 1 ? "YES" : "NO");
        }
    }
    
    private static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

03. 班级分组优化

问题描述

小毛是一位班主任，需要将班级里的 名学生按照学号顺序分成若干个小组进行项目合作。每个学生都有一个能力值，用正整数表示。

现在需要将学生按学号顺序分成 个小组，每组恰好包含 名连续学号的学生（保证 是 的因子）。为了公平起见，小毛决定可以在分组前重新安排学生的座位顺序，但有一个限制：只能交换那些学号对 取模结果相同的学生。

每个小组的"实力值"定义为该组内学生能力值的最大值。小毛希望通过合理安排座位，使得所有小组的实力值之和尽可能小。

请输出一种最优的座位安排方案，使得实力值之和达到最小。

输入格式

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

对于每组测试数据：

第一行输入两个正整数 （，，），分别表示学生总数和每组学生数。

第二行输入 个正整数 （），表示每名学生的能力值。

保证单个测试文件中所有测试数据的 之和不超过 。

输出格式

对于每组测试数据，输出一行包含 个正整数，表示最优安排后的学生能力值序列。

如果存在多种最优方案，可以输出任意一种。

样例输入

2
6 3
4 1 5 2 3 6
8 2
7 1 6 2 5 3 4 8

样例输出

2 1 5 4 3 6
4 1 5 2 6 3 7 8