✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺
• 配套练习题库

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

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

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

美团

题目一：珍宝寻踪队列

1️⃣：按照宝石价值对索引排序

2️⃣：遍历相邻索引，统计前进和后退传送次数

难度：中等

这道题目的关键在于理解题意，通过排序得到正确的宝石鉴定顺序。算法实现简单，时间复杂度为 O(n log n)，主要来自于排序操作。

题目二：花园整理者

1️⃣：对字符串排序得到目标有序字符串

2️⃣：找出原字符串与目标字符串不同的位置

3️⃣：检查是否能通过一次交换实现有序排列

难度：中等

这道题目需要理解字符串排序和比较的基本操作，关键在于判断通过一次交换是否能达到目标状态。实现比较直观，时间复杂度为 O(n log n)。

题目三：魔法数字识别系统

1️⃣：使用AC自动机识别多模式匹配

2️⃣：使用数位DP统计魔力值恰好为1的数字数量

3️⃣：注意处理大数范围和模运算

难度：中等偏难

这道题目结合了AC自动机和数位DP两种高级算法，需要理解自动机的构建和多状态的DP转移。对于大数范围的处理也是一个考点，整体实现较为复杂。

01. 珍宝寻踪队列

问题描述

小柯是一名资深的珠宝鉴定师，最近她收到了一批编号从1开始的珍贵宝石。每颗宝石都有一个独特的价值，所有宝石的价值各不相同。

小柯设计了一种特殊的宝石鉴定顺序：她总是从价值最低的宝石开始鉴定，然后每次都会选择第一颗价值高于当前宝石的宝石进行下一次鉴定，直到所有宝石都被鉴定完毕。

例如，假设宝石的价值数组为 ，小柯会先选择编号为 的宝石（价值为 ），接着找到第一颗价值高于 的宝石即编号为 的宝石（价值为 ），然后再找到第一颗价值高于 的宝石即编号为 的宝石（价值为 ）。整个鉴定顺序为： → → 。

在这个过程中，如果小柯从较小编号的宝石移动到较大编号的宝石（即 ），我们称之为"前进传送"；如果从较大编号的宝石移动到较小编号的宝石（即 ），则称之为"后退传送"。

请你帮助小柯计算在整个鉴定过程中，她需要进行多少次前进传送和多少次后退传送。

输入格式

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

对于每组测试数据：

• 第一行输入一个整数 （），表示宝石的数量。
• 第二行输入 个整数，第 个数为 （），表示第 颗宝石的价值。

保证所有测试数据中 。

输出格式

对于每组测试数据，输出一行，包含两个整数，分别表示前进传送和后退传送的次数，中间用空格隔开。

样例输入

2
3
1 2 3
3
3 2 1

样例输出

2 0
0 2

数据范围

• 
• 
• 
• 

样例 解释说明

样例1	第一组数据：宝石价值为 [1,2,3]，鉴定顺序为：，所有移动都是从小编号到大编号，因此有2次前进传送，0次后退传送。 第二组数据：宝石价值为 [3,2,1]，鉴定顺序为：，所有移动都是从大编号到小编号，因此有0次前进传送，2次后退传送。

题解

这道题的核心是跟踪小柯按照宝石价值从小到大鉴定时的移动方向。

首先，我们需要知道宝石鉴定的顺序，这其实就是宝石价值从小到大的排序顺序。通过排序，我们可以得到小柯实际访问宝石的索引序列。

例如，对于样例1中的第一组数据 [1,2,3]，按价值排序后的访问顺序就是索引 1→2→3。当从索引1移动到索引2，再从索引2移动到索引3时，都是从小索引到大索引，所以有2次前进传送，0次后退传送。

对于第二组数据 [3,2,1]，按价值排序后的访问顺序是索引 3→2→1。从索引3移动到索引2，再从索引2移动到索引1，都是从大索引到小索引，所以有0次前进传送，2次后退传送。

实现时，我们可以将宝石的价值和索引组成一个对，然后按照价值排序。接着遍历排序后的数组，比较相邻两个元素的索引大小关系，来统计前进传送和后退传送的次数。

时间复杂度分析：

• 排序操作的时间复杂度为
• 遍历统计的时间复杂度为
• 总体时间复杂度为

对于本题的数据范围（），这个复杂度是完全可以接受的。

参考代码

• Python

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

def solve():
    n = int(input())
    gems = list(map(int, input().split()))
    
    # 将宝石价值和索引组成对
    arr = [(gems[i], i+1) for i in range(n)]
    # 按价值排序
    arr.sort()
    
    fwd = 0  # 前进传送计数
    bwd = 0  # 后退传送计数
    
    # 遍历排序后的数组，计算传送类型
    for i in range(1, n):
        if arr[i][1] > arr[i-1][1]:
            fwd += 1  # 从小索引到大索引
        else:
            bwd += 1  # 从大索引到小索引
    
    return fwd, bwd

t = int(input())
for _ in range(t):
    fwd, bwd = solve()
    print(f"{fwd} {bwd}")

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        // 存储宝石价值和索引
        vector<pair<int, int>> gems(n);
        for (int i = 0; i < n; i++) {
            cin >> gems[i].first;  // 宝石价值
            gems[i].second = i + 1;  // 宝石索引
        }
        
        // 按价值排序
        sort(gems.begin(), gems.end());
        
        int fwd = 0, bwd = 0;
        
        // 计算传送类型
        for (int i = 1; i < n; i++) {
            if (gems[i].second > gems[i-1].second) {
                fwd++;  // 前进传送
            } else {
                bwd++;  // 后退传送
            }
        }
        
        cout << fwd << " " << bwd << "\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;
        
        int t = Integer.parseInt(br.readLine());
        
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            
            // 存储宝石价值和索引
            Pair[] gems = new Pair[n];
            for (int i = 0; i < n; i++) {
                int val = Integer.parseInt(st.nextToken());
                gems[i] = new Pair(val, i + 1);
            }
            
            // 按价值排序
            Arrays.sort(gems);
            
            int fwd = 0, bwd = 0;
            
            // 计算传送类型
            for (int i = 1; i < n; i++) {
                if (gems[i].idx > gems[i-1].idx) {
                    fwd++;  // 前进传送
                } else {
                    bwd++;  // 后退传送
                }
            }
            
            System.out.println(fwd + " " + bwd);
        }
    }
    
    static class Pair implements Comparable<Pair> {
        int val, idx;
        
        Pair(int val, int idx) {
            this.val = val;
            this.idx = idx;
        }
        
        @Override
        public int compareTo(Pair other) {
            return Integer.compare(this.val, other.val);
        }
    }
}

02. 花园整理者

问题描述

小基 是一位热爱花卉的园艺师，她的花园里种植了一排花卉，每一株花卉都有一个独特的品种代号，用一个小写字母表示。小基 希望花园看起来更加有序，她想让这排花卉按照字母顺序从左到右排列（即 到 ）。

由于某些花卉已经生长多时，过度移动可能会损伤它们，因此 小基 决定只进行恰好一次操作：

• 选择两株不同位置的花卉，交换它们的位置。

小基 想知道，通过这一次交换操作，是否能让整排花卉按照字母顺序排列。你能帮助她吗？

输入格式

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

对于每组测试数据：

• 第一行输入一个整数 （），表示花卉的数量。
• 第二行输入一个长度为 的字符串 ，只包含小写字母，第 个字符 表示第 株花卉的品种代号。

保证所有测试数据中 。

输出格式

对于每组测试数据，如果可以通过一次交换操作使花卉按照字母顺序排列，则输出 YES，否则输出 NO。

样例输入

2
3
acb
3
bca

样例输出

YES
NO

数据范围

• 
• 
• 字符串 只包含小写字母
• 

样例 解释说明

样例1	第一组数据：字符串"acb"中，交换位置2和位置3的字符（'c'和'b'）可以得到"abc"，满足字母顺序，所以输出YES。 第二组数据：字符串"bca"无法通过一次交换操作变成按字母顺序排列的字符串，所以输出NO。

题解

这道题的核心是判断能否通过一次交换操作，使得字符串按照字母顺序排列。

解决这个问题，我们首先需要知道排序后的字符串是什么样子。我们可以将原字符串复制一份并对其进行排序，得到目标字符串。

然后，我们有几种情况需要考虑：

1. 如果原字符串已经有序（与排序后的字符串相同），那么不需要交换，直接输出YES。
2. 如果原字符串与排序后的字符串不同，我们需要找出所有不同的位置。
   • 如果不同的位置恰好有2个，我们可以尝试交换这两个位置的字符，看是否能得到排序后的字符串。
   • 如果不同的位置多于2个，那么一次交换操作是不够的，输出NO。

时间复杂度分析：

• 字符串排序的时间复杂度为
• 比较字符串和找不同位置的时间复杂度为
• 总体时间复杂度为

对于本题的数据范围（），这个复杂度是完全可以接受的。

参考代码

• Python

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

def solve():
    n = int(input())
    s = input()
    
    # 获取排序后的目标字符串
    t = ''.join(sorted(s))
    
    # 如果已经有序，直接返回YES
    if s == t:
        return "YES"
    
    # 找出所有不同的位置
    diff = []
    for i in range(n):
        if s[i] != t[i]:
            diff.append(i)
    
    # 如果不同的位置恰好有2个，尝试交换
    if len(diff) == 2:
        # 创建字符串的可变列表
        chars = list(s)
        chars[diff[0]], chars[diff[1]] = chars[diff[1]], chars[diff[0]]
        
        # 检查交换后是否与目标字符串相同
        if ''.join(chars) == t:
            return "YES"
    
    return "NO"

t = int(input())
for _ in range(t):
    print(solve())

• Cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        string s;
        cin >> s;
        
        // 获取排序后的目标字符串
        string t = s;
        sort(t.begin(), t.end());
        
        // 如果已经有序，直接输出YES
        if (s == t) {
            cout << "YES\n";
            continue;
        }
        
        // 找出所有不同的位置
        vector<int> diff;
        for (int i = 0; i < n; i++) {
            if (s[i] != t[i]) {
                diff.push_back(i);
            }
        }
        
        // 如果不同的位置恰好有2个，尝试交换
        bool can = false;
        if (diff.size() == 2) {
            swap(s[diff[0]], s[diff[1]]);
            if (s == t) {
                can = true;
            }
        }
        
        cout << (can ? "YES\n" : "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) {
            int n = Integer.parseInt(br.readLine());
            String s = br.readLine();
            
            // 获取排序后的目标字符串
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String t = new String(chars);
            
            // 如果已经有序，直接输出YES
            if (s.equals(t)) {
                System.out.println("YES");