✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：密码验证器

1️⃣：检查字符串长度是否为3的倍数

2️⃣：按3个字符分组，检查每组是否为"abc"或"bca"（大小写不敏感）

3️⃣：所有分组都满足条件则输出Yes，否则输出No

难度：简单

这道题考查字符串处理和模式匹配。关键在于理解密码的构成规则：只能由特定的3字符模式组成。通过简单的遍历和字符串比较即可解决，时间复杂度为O(n)。

题目二：商店评分系统

1️⃣：理解题目要求：求所有子序列平均值（向下取整）的最大值

2️⃣：关键观察：子序列平均值不会超过其最大元素

3️⃣：答案就是整个数组的最大值

难度：中等

这道题目表面上需要枚举所有子序列，但通过数学分析可以发现一个重要性质：任意子序列的平均值（向下取整）都不会超过该子序列的最大元素。因此答案就是数组中的最大值，实现了O(n)的优雅解法。

题目三：魔法传送网络

1️⃣：对每种魔法属性使用多源最短路算法预处理可达范围

2️⃣：构建辅助图，将瞬移关系转化为权重为1的边

3️⃣：在辅助图上使用BFS求解最短路径

难度：中等偏难

这道题结合了图论中的最短路径和状态转换。核心思想是将复杂的瞬移规则转化为简单的图论问题。通过多源Dijkstra预处理 + BFS求解的两阶段方法，实现了O(c·m log n)的时间复杂度，在给定数据范围下完全可行。

01. 密码验证器

问题描述

小兰正在开发一个安全系统，该系统使用特殊的密码验证机制。系统只接受由两种特定模式组成的密码："abc" 和 "bca"（大小写不敏感）。

给定一个仅由英文字母组成的字符串 ，请判断它是否是一个有效的密码，即是否可以完全由 "abc" 和 "bca" 的组合拼接而成。

输入格式

第一行包含一个正整数 （），表示测试用例的数量。

接下来对于每个测试用例：

• 第一行包含一个正整数 （），表示密码字符串的长度。
• 第二行包含一个长度为 的字符串 ，仅包含大小写英文字母。

保证所有测试用例中 的总和不超过 。

输出格式

对于每个测试用例，输出一行：

• 如果字符串 可以由若干个 "abc" 或 "bca" 拼接而成，输出 Yes。
• 否则输出 No。

样例输入

2
6
AbCbCa
3
aBd

样例输出

Yes
No

样例	解释说明
样例1	AbCbCa → abc + bca，满足条件
样例2	aBd 无法拆分为有效的模式组合

数据范围

• 
• 
• 所有测试用例中 的总和不超过

题解

这道题的关键在于理解密码的构成规则。每个有效的密码段都是长度为 3 的字符串，要么是 "abc"，要么是 "bca"，并且大小写不敏感。

首先，如果字符串的长度不是 3 的倍数，那么肯定无法拼接成有效密码。

接下来，只需要将字符串按照长度 3 进行分割，检查每个分割出来的子串（转为小写后）是否等于 "abc" 或 "bca"。如果所有子串都满足条件，则为有效密码；否则为无效密码。

算法步骤：

1. 检查字符串长度是否为 3 的倍数
2. 以步长 3 遍历字符串，每次取出 3 个字符
3. 将这 3 个字符转换为小写并组成子串
4. 判断子串是否为 "abc" 或 "bca"
5. 如果所有子串都符合要求，返回 "Yes"，否则返回 "No"

时间复杂度：，其中 是字符串长度。 空间复杂度：。

参考代码

• Python

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

def check_pwd(s):
    # 检查长度是否为3的倍数
    if len(s) % 3 != 0:
        return False
    
    # 每3个字符检查一次
    for i in range(0, len(s), 3):
        sub = s[i:i+3].lower()  # 转为小写
        if sub != "abc" and sub != "bca":
            return False
    return True

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    if check_pwd(s):
        print("Yes")
    else:
        print("No")

• Cpp

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

// 字符转小写函数
char to_low(char c) {
    if (c >= 'A' && c <= 'Z') 
        return c - 'A' + 'a';
    return c;
}

bool valid_pwd(const string& s) {
    int n = s.size();
    if (n % 3) return false;  // 长度必须是3的倍数
    
    for (int i = 0; i < n; i += 3) {
        string seg = "";
        // 提取3个字符并转小写
        for (int j = 0; j < 3; j++) {
            seg += to_low(s[i + j]);
        }
        // 检查是否为有效模式
        if (seg != "abc" && seg != "bca") {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        cout << (valid_pwd(s) ? "Yes" : "No") << "\n";
    }
    return 0;
}

• Java

import java.util.*;

public class Main {
    // 检查密码是否有效
    static boolean checkValid(String s) {
        int len = s.length();
        if (len % 3 != 0) return false;  // 长度检查
        
        for (int i = 0; i < len; i += 3) {
            String part = s.substring(i, i + 3).toLowerCase();
            if (!part.equals("abc") && !part.equals("bca")) {
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        while (t-- > 0) {
            int n = sc.nextInt();
            String pwd = sc.next();
            
            if (checkValid(pwd)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
        sc.close();
    }
}

02. 商店评分系统

问题描述

小基 经营着一家在线商店，她需要设计一个评分系统来评估不同商品组合的满意度。对于包含 个商品的清单，每个商品都有一个满意度评分 。

对于任意一个连续的商品子序列 （），其综合评分定义为该序列中所有商品满意度的平均值向下取整：

小基 想要知道所有可能的连续商品子序列中，综合评分的最大值是多少。

输入格式

第一行包含一个正整数 （），表示商品的数量。

第二行包含 个非负整数 （），表示每个商品的满意度评分。

输出格式

输出一个整数，表示所有连续商品子序列综合评分的最大值。

样例输入

1
3

5
2 8 6 1 4

样例输出

3

8

样例	解释说明
样例1	只有一个商品，综合评分为
样例2	单个商品中最高满意度为 ，因此最大综合评分为

数据范围

• 
• 

题解

这道题乍一看需要枚举所有可能的子序列并计算它们的平均值，但实际上有一个非常巧妙的数学性质可以利用。

关键观察：对于任意一个子序列，其平均值（向下取整）永远不会超过该子序列中的最大元素。这是因为平均值的上限就是最大值。

更进一步，如果我们选择只包含一个元素的子序列，那么这个子序列的综合评分就等于该元素本身的值。

因此，所有子序列中综合评分的最大值，实际上就等于整个数组中的最大元素。

证明：

• 设数组中的最大元素为
• 对于任意子序列 ，有
• 而包含最大元素的单元素子序列的综合评分恰好等于
• 因此答案就是

算法非常简单：遍历一遍数组，找到最大值即可。

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

参考代码

• Python

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

n = int(input())
nums = list(map(int, input().split()))

# 找到数组中的最大值
max_val = max(nums)
print(max_val)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    long long ans = 0;  // 使用long long防止溢出
    for (int i = 0; i < n; i++) {
        long long val;
        cin >> val;
        ans = max(ans, val);  // 更新最大值
    }
    
    cout << ans << "\n";
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long maxScore = 0;  // 记录最大评分
        for (int i = 0; i < n; i++) {
            long score = sc.nextLong();
            maxScore = Math.max(maxScore, score);
        }
        
        System.out.println(maxScore);
        sc.close();
    }
}

03. 魔法传送网络

问题描述

小柯是一位魔法师，她需要在一个复杂的魔法传送网络中旅行。这个网络由 个魔法节点组成，节点之间通过 条单向魔法通道连接。

网络的特殊之处在于：

• 每个魔法节点都被赋予了一种魔法属性，用颜色 （）来表示
• 每条魔法通道 表示可以从节点 直接传送到节点 ，消耗 单位的魔法能量
• 对于第 种颜色的魔法属性，小柯掌握了相应的瞬移法术，最大瞬移距离为

小柯的瞬移法术规则如下：

当她位于颜色为 的节点 时，如果存在从 到某个节点