✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：礼貌队列门通过问题

1️⃣：使用双端队列存储队列元素，维护翻转标志

2️⃣：根据门的类型和翻转状态，更新队列或翻转标志

3️⃣：根据最终翻转标志决定正序或逆序输出

难度：中等

这道题目的关键在于理解队列在不同类型门下的变化规则，并找到一种高效方法避免频繁的实际队列反转操作。通过使用一个翻转标志和双端队列，可以实现O(n+m)的时间复杂度。

题目二：数字魔术分割

1️⃣：将数字按从大到小排序

2️⃣：计算第一段需要的数字个数（L-b+1）

3️⃣：将最大的L-b+1个数字组成一个大数，剩余数字作为单独的数

难度：中等

这道题目的关键是找到数学上的贪心策略：要使若干数字之和最大，应该组成尽可能多的小位数的数。题目要求必须分成b段，因此需要精确计算第一段的大小，再将剩余数字单独成段。

题目三：方块消除大师

1️⃣：模拟消除过程，标记连续相同的方块

2️⃣：消除标记的方块并更新分数

3️⃣：处理方块下落，重复检查直到没有可消除的方块

难度：中等偏难

这道题目需要完全模拟游戏过程，包括方块的消除和下落。关键是正确处理方块下落的逻辑和高效识别可消除的方块组。通过仔细实现消除和重力下落机制，可以实现O((H×5)²)的时间复杂度解法。

01. 礼貌队列门通过问题

问题描述

小基博物馆每天接待大量游客。博物馆内有一系列特殊设计的门，每个门有不同的通行规则。博物馆管理员想知道，当一队游客（初始编号为1到n）依次通过这些门后，他们的最终顺序会是怎样的。

博物馆内有两种特殊的门：

• "礼让门"（A型）：走到这种门前，第一位游客会礼貌地为其他人开门，等所有人都通过后，自己最后通过。队列中其余人的顺序不变。
• "谦让门"（B型）：走到这种门前，每个人都会谦让给后面的人先进，结果是队列完全翻转 - 第一个人变成最后一个，最后一个人变成第一个。

请编写程序计算游客通过所有门后的最终顺序。

输入格式

第一行输入一个正整数 ，表示游客的数量。

第二行输入一个非负整数 ，表示门的数量。

接下来 行，每行输入一个字符 或者 ，表示第 扇门的类型。

输出格式

在 行中输出通过所有门后游客的最终编号，每行一个数字。

样例输入

5
4
A
A
B
A

9
3
B
B
B

样例输出

1
5
4
3
2

9
8
7
6
5
4
3
2
1

数据范围

题解

这道题目本质上是要模拟一个队列在不同操作下的变化过程。通过分析题目，我们发现：

A型门操作：队首元素移到队尾 B型门操作：整个队列反转

一个直接的思路是用数组或链表模拟整个过程，但每次反转队列的操作可能效率不高。这里可以使用一个巧妙的方法：用一个布尔变量标记当前队列是否被反转，然后根据这个标记调整我们的操作方式。

具体来说：

1. 使用双端队列存储所有元素
2. 维护一个表示队列是否被反转的布尔变量
3. 如果遇到A型门：
   • 若队列未反转：弹出队首并加入队尾
   • 若队列已反转：弹出队尾并加入队首（这相当于在反转状态下模拟了队首到队尾的移动）
4. 如果遇到B型门：只需将反转标志取反，而不实际反转队列
5. 最后根据反转标志决定正向还是反向输出队列

这种方法避免了大量的实际元素移动操作，时间复杂度是O(n+m)，其中n是人数，m是门数。对于题目给定的数据范围（n,m ≤ 10^5），这个解法非常高效。

参考代码

• Python

import sys
from collections import deque

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

# 读取输入
n = int(input())
m = int(input())

# 初始化队列
que = deque(range(1, n+1))
flip = False  # 翻转标志

# 处理每个门
for _ in range(m):
    door = input()
    if door == 'A':
        # A型门：第一个人让给其他人，自己最后通过
        if not flip:
            # 未翻转状态：队首元素移到队尾
            x = que.popleft()
            que.append(x)
        else:
            # 已翻转状态：队尾元素移到队首
            x = que.pop()
            que.appendleft(x)
    else:  # door == 'B'
        # B型门：队列完全翻转，只需改变翻转标志
        flip = not flip

# 根据翻转标志决定输出顺序
if not flip:
    # 未翻转状态：正序输出
    for num in que:
        print(num)
else:
    # 已翻转状态：逆序输出
    for num in reversed(que):
        print(num)

• Cpp

#include <iostream>
#include <deque>
using namespace std;

int main() {
    // 关闭同步流，加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    int n, m;
    cin >> n >> m;
    
    // 初始化队列和翻转标志
    deque<int> dq;
    for (int i = 1; i <= n; i++) 
        dq.push_back(i);
    bool rev = false;
    
    // 处理每个门
    char door;
    while (m--) {
        cin >> door;
        if (door == 'A') {
            // A型门处理
            if (!rev) {
                // 未翻转：队首元素移到队尾
                int tmp = dq.front();
                dq.pop_front();
                dq.push_back(tmp);
            } else {
                // 已翻转：队尾元素移到队首
                int tmp = dq.back();
                dq.pop_back();
                dq.push_front(tmp);
            }
        } else {
            // B型门处理：翻转标志取反
            rev = !rev;
        }
    }
    
    // 根据翻转标志决定输出顺序
    if (!rev) {
        // 未翻转：正序输出
        for (int x : dq) 
            cout << x << '\n';
    } else {
        // 已翻转：逆序输出
        for (auto it = dq.rbegin(); it != dq.rend(); ++it)
            cout << *it << '\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 n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        
        // 初始化双端队列
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            dq.offerLast(i);
        }
        
        // 翻转标志
        boolean isRev = false;
        
        // 处理每个门
        for (int i = 0; i < m; i++) {
            String door = br.readLine();
            if (door.equals("A")) {
                // A型门处理
                if (!isRev) {
                    // 未翻转：队首元素移到队尾
                    int tmp = dq.pollFirst();
                    dq.offerLast(tmp);
                } else {
                    // 已翻转：队尾元素移到队首
                    int tmp = dq.pollLast();
                    dq.offerFirst(tmp);
                }
            } else {
                // B型门处理：翻转标志取反
                isRev = !isRev;
            }
        }
        
        // 根据翻转标志决定输出顺序
        if (!isRev) {
            // 未翻转：正序输出
            for (int x : dq) {
                System.out.println(x);
            }
        } else {
            // 已翻转：逆序输出
            Iterator<Integer> it = dq.descendingIterator();
            while (it.hasNext()) {
                System.out.println(it.next());
            }
        }
    }
}

02. 数字魔术分割

问题描述

小基是一位数字魔术师，他有一个特殊的技能可以对任意一个正整数的数字进行重新排列，然后将排列后的数字序列分割成若干段，每段组成一个新的数字，最后计算这些数字的总和。

小基的表演规则如下：

• 他会选择一个正整数 并决定要将其分成 段
• 他可以任意重新排列这个数字的所有数位
• 每一段必须是排列后数字序列中的连续子串，连起来恰好能完整还原排列后的数字
• 每一段至少包含1位数字（不能出现空段）
• 允许某段组成的数字为0，但不允许出现多余的前导零

观众想知道，在满足以上规则的情况下，小基能够得到的所有段的数字之和的最大可能值是多少？

输入格式

在一行中输入两个整数 和 ，分别表示原始整数与分段数。

其中 保证不超过整数 的十进制位数。

输出格式

输出一个整数，表示将整数 的数字打乱顺序后分为 段所得各子数之和的最大值。

样例输入

13 1

122 2

样例输出

31

23

数据范围

• 
• 整数 的十进制位数

题解

这道题目要求我们将一个整数的数字重排后分段，使得分段数字之和最大。通过分析，可以找到以下关键性质：

当我们要使若干个数字组成的数的和最大时，最有效的方式是让这些数字组成尽可能多的小数位数的数。例如，数字1和2可以组成12或1+2=3，显然后者更大。

但有一个限制条件：我们必须恰好分成b段。结合上述性质，最优的分法应该是：

1. 将所有数字从大到小排序
2. 用最大的那些数字组成一个较大的数（第一段）
3. 剩下的每个数字单独成为一段

这样，我们就能用b段表示原数字，并使总和最大。具体来说，如果原数字有L位，要分成b段，那么第一段应该包含L-b+1个最大的数字，剩下的b-1个数字每个单独成一段。

举例说明：对于数字122分成2段，重排后是221，最优方案是22和1，总和为23。

实现时，我们需要注意前导零的问题，但由于我们是从大到小排序，只要第一段的第一个数字不是0（一定是最大的数字），就不会有前导零问题。

时间复杂度为O(L log L)，其中L是输入数字的位数，主要来自排序操作。对于本题的数据范围（a ≤ 10^9），L最大为10，所以排序时间几乎可以忽略不计。

参考代码

• Python

import sys

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

# 读取输入
a, b = input().split()
b = int(b)

# 提取数字并排序
digs = sorted([int(d) for d in a], reverse=True)
l = len(digs)

# 计算第一段要用的数字个数
k = l - b + 1

# 计算答案
ans = 0

# 构造第一段数字(较大的段)
first = 0
for i in range(k):
    first = first * 10 + digs[i]

# 加上第一段
ans += first

# 加上剩余的单数字段
for i in range(k, l):
    ans += digs[i]

# 输出结果
print(ans)

• Cpp

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

int main() {
    // 加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    string a;
    int b;
    cin >> a >> b;
    
    // 提取数字并排序
    vector<int> digs;
    for (char c : a) {
        digs.push_back(c - '0');
    }
    sort(digs.begin(), digs.end(), greater<int>());
    
    int l = digs.size();
    // 计算第一段数字个数
    int k = l - b + 1;
    
    // 计算答案
    long long ans = 0;