? 春招備戰(zhàn)指南 ?

?? 學習建議：

• 先嘗試獨立解題（建議用時：90分鐘/套）
• 對照解析查漏補缺

?? 題面描述背景等均已深度改編，做法和題目本質(zhì)基本保持一致。

?? 感謝各位朋友們的訂閱，你們的支持是我們創(chuàng)作的最大動力

?? 目前本專欄已經(jīng)上線60+套真題改編解析，后續(xù)會持續(xù)更新的

春秋招合集 -> 互聯(lián)網(wǎng)必備刷題寶典??

題目一：禮貌隊列門通過問題

1??：使用雙端隊列存儲隊列元素，維護翻轉(zhuǎn)標志

2??：根據(jù)門的類型和翻轉(zhuǎn)狀態(tài)，更新隊列或翻轉(zhuǎn)標志

3??：根據(jù)最終翻轉(zhuǎn)標志決定正序或逆序輸出

難度：中等

這道題目的關鍵在于理解隊列在不同類型門下的變化規(guī)則，并找到一種高效方法避免頻繁的實際隊列反轉(zhuǎn)操作。通過使用一個翻轉(zhuǎn)標志和雙端隊列，可以實現(xiàn)O(n+m)的時間復雜度。

題目二：數(shù)字魔術分割

1??：將數(shù)字按從大到小排序

2??：計算第一段需要的數(shù)字個數(shù)（L-b+1）

3??：將最大的L-b+1個數(shù)字組成一個大數(shù)，剩余數(shù)字作為單獨的數(shù)

難度：中等

這道題目的關鍵是找到數(shù)學上的貪心策略：要使若干數(shù)字之和最大，應該組成盡可能多的小位數(shù)的數(shù)。題目要求必須分成b段，因此需要精確計算第一段的大小，再將剩余數(shù)字單獨成段。

題目三：方塊消除大師

1??：模擬消除過程，標記連續(xù)相同的方塊

2??：消除標記的方塊并更新分數(shù)

3??：處理方塊下落，重復檢查直到?jīng)]有可消除的方塊

難度：中等偏難

這道題目需要完全模擬游戲過程，包括方塊的消除和下落。關鍵是正確處理方塊下落的邏輯和高效識別可消除的方塊組。通過仔細實現(xiàn)消除和重力下落機制，可以實現(xiàn)O((H×5)2)的時間復雜度解法。

01. 禮貌隊列門通過問題

問題描述

小基博物館每天接待大量游客。博物館內(nèi)有一系列特殊設計的門，每個門有不同的通行規(guī)則。博物館管理員想知道，當一隊游客（初始編號為1到n）依次通過這些門后，他們的最終順序會是怎樣的。

博物館內(nèi)有兩種特殊的門：

• "禮讓門"（A型）：走到這種門前，第一位游客會禮貌地為其他人開門，等所有人都通過后，自己最后通過。隊列中其余人的順序不變。
• "謙讓門"（B型）：走到這種門前，每個人都會謙讓給后面的人先進，結(jié)果是隊列完全翻轉(zhuǎn) - 第一個人變成最后一個，最后一個人變成第一個。

請編寫程序計算游客通過所有門后的最終順序。

輸入格式

第一行輸入一個正整數(shù) ，表示游客的數(shù)量。

第二行輸入一個非負整數(shù) ，表示門的數(shù)量。

接下來 行，每行輸入一個字符 或者 ，表示第 扇門的類型。

輸出格式

在 行中輸出通過所有門后游客的最終編號，每行一個數(shù)字。

樣例輸入

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

數(shù)據(jù)范圍

題解

這道題目本質(zhì)上是要模擬一個隊列在不同操作下的變化過程。通過分析題目，我們發(fā)現(xiàn)：

A型門操作：隊首元素移到隊尾 B型門操作：整個隊列反轉(zhuǎn)

一個直接的思路是用數(shù)組或鏈表模擬整個過程，但每次反轉(zhuǎn)隊列的操作可能效率不高。這里可以使用一個巧妙的方法：用一個布爾變量標記當前隊列是否被反轉(zhuǎn)，然后根據(jù)這個標記調(diào)整我們的操作方式。

具體來說：

1. 使用雙端隊列存儲所有元素
2. 維護一個表示隊列是否被反轉(zhuǎn)的布爾變量
3. 如果遇到A型門：
   • 若隊列未反轉(zhuǎn)：彈出隊首并加入隊尾
   • 若隊列已反轉(zhuǎn)：彈出隊尾并加入隊首（這相當于在反轉(zhuǎn)狀態(tài)下模擬了隊首到隊尾的移動）
4. 如果遇到B型門：只需將反轉(zhuǎn)標志取反，而不實際反轉(zhuǎn)隊列
5. 最后根據(jù)反轉(zhuǎn)標志決定正向還是反向輸出隊列

這種方法避免了大量的實際元素移動操作，時間復雜度是O(n+m)，其中n是人數(shù)，m是門數(shù)。對于題目給定的數(shù)據(jù)范圍（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  # 翻轉(zhuǎn)標志

# 處理每個門
for _ in range(m):
    door = input()
    if door == 'A':
        # A型門：第一個人讓給其他人，自己最后通過
        if not flip:
            # 未翻轉(zhuǎn)狀態(tài)：隊首元素移到隊尾
            x = que.popleft()
            que.append(x)
        else:
            # 已翻轉(zhuǎn)狀態(tài)：隊尾元素移到隊首
            x = que.pop()
            que.appendleft(x)
    else:  # door == 'B'
        # B型門：隊列完全翻轉(zhuǎn)，只需改變翻轉(zhuǎn)標志
        flip = not flip

# 根據(jù)翻轉(zhuǎn)標志決定輸出順序
if not flip:
    # 未翻轉(zhuǎn)狀態(tài)：正序輸出
    for num in que:
        print(num)
else:
    # 已翻轉(zhuǎn)狀態(tài)：逆序輸出
    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;
    
    // 初始化隊列和翻轉(zhuǎn)標志
    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) {
                // 未翻轉(zhuǎn)：隊首元素移到隊尾
                int tmp = dq.front();
                dq.pop_front();
                dq.push_back(tmp);
            } else {
                // 已翻轉(zhuǎn)：隊尾元素移到隊首
                int tmp = dq.back();
                dq.pop_back();
                dq.push_front(tmp);
            }
        } else {
            // B型門處理：翻轉(zhuǎn)標志取反
            rev = !rev;
        }
    }
    
    // 根據(jù)翻轉(zhuǎn)標志決定輸出順序
    if (!rev) {
        // 未翻轉(zhuǎn)：正序輸出
        for (int x : dq) 
            cout << x << '\n';
    } else {
        // 已翻轉(zhuǎn)：逆序輸出
        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);
        }
        
        // 翻轉(zhuǎn)標志
        boolean isRev = false;
        
        // 處理每個門
        for (int i = 0; i < m; i++) {
            String door = br.readLine();
            if (door.equals("A")) {
                // A型門處理
                if (!isRev) {
                    // 未翻轉(zhuǎn)：隊首元素移到隊尾
                    int tmp = dq.pollFirst();
                    dq.offerLast(tmp);
                } else {
                    // 已翻轉(zhuǎn)：隊尾元素移到隊首
                    int tmp = dq.pollLast();
                    dq.offerFirst(tmp);
                }
            } else {
                // B型門處理：翻轉(zhuǎn)標志取反
                isRev = !isRev;
            }
        }
        
        // 根據(jù)翻轉(zhuǎn)標志決定輸出順序
        if (!isRev) {
            // 未翻轉(zhuǎn)：正序輸出
            for (int x : dq) {
                System.out.println(x);
            }
        } else {
            // 已翻轉(zhuǎn)：逆序輸出
            Iterator<Integer> it = dq.descendingIterator();
            while (it.hasNext()) {
                System.out.println(it.next());
            }
        }
    }
}

02. 數(shù)字魔術分割

問題描述

小基是一位數(shù)字魔術師，他有一個特殊的技能可以對任意一個正整數(shù)的數(shù)字進行重新排列，然后將排列后的數(shù)字序列分割成若干段，每段組成一個新的數(shù)字，最后計算這些數(shù)字的總和。

小基的表演規(guī)則如下：

• 他會選擇一個正整數(shù) 并決定要將其分成 段
• 他可以任意重新排列這個數(shù)字的所有數(shù)位
• 每一段必須是排列后數(shù)字序列中的連續(xù)子串，連起來恰好能完整還原排列后的數(shù)字
• 每一段至少包含1位數(shù)字（不能出現(xiàn)空段）
• 允許某段組成的數(shù)字為0，但不允許出現(xiàn)多余的前導零

觀眾想知道，在滿足以上規(guī)則的情況下，小基能夠得到的所有段的數(shù)字之和的最大可能值是多少？

輸入格式

在一行中輸入兩個整數(shù) 和 ，分別表示原始整數(shù)與分段數(shù)。

其中 保證不超過整數(shù) 的十進制位數(shù)。

輸出格式

輸出一個整數(shù)，表示將整數(shù) 的數(shù)字打亂順序后分為 段所得各子數(shù)之和的最大值。

樣例輸入

13 1

122 2

樣例輸出

31

23

數(shù)據(jù)范圍

• 
• 整數(shù) 的十進制位數(shù)

題解

這道題目要求我們將一個整數(shù)的數(shù)字重排后分段，使得分段數(shù)字之和最大。通過分析，可以找到以下關鍵性質(zhì)：

當我們要使若干個數(shù)字組成的數(shù)的和最大時，最有效的方式是讓這些數(shù)字組成盡可能多的小數(shù)位數(shù)的數(shù)。例如，數(shù)字1和2可以組成12或1+2=3，顯然后者更大。

但有一個限制條件：我們必須恰好分成b段。結(jié)合上述性質(zhì)，最優(yōu)的分法應該是：

1. 將所有數(shù)字從大到小排序
2. 用最大的那些數(shù)字組成一個較大的數(shù)（第一段）
3. 剩下的每個數(shù)字單獨成為一段

這樣，我們就能用b段表示原數(shù)字，并使總和最大。具體來說，如果原數(shù)字有L位，要分成b段，那么第一段應該包含L-b+1個最大的數(shù)字，剩下的b-1個數(shù)字每個單獨成一段。

舉例說明：對于數(shù)字122分成2段，重排后是221，最優(yōu)方案是22和1，總和為23。

實現(xiàn)時，我們需要注意前導零的問題，但由于我們是從大到小排序，只要第一段的第一個數(shù)字不是0（一定是最大的數(shù)字），就不會有前導零問題。

時間復雜度為O(L log L)，其中L是輸入數(shù)字的位數(shù)，主要來自排序操作。對于本題的數(shù)據(jù)范圍（a ≤ 10^9），L最大為10，所以排序時間幾乎可以忽略不計。

參考代碼

• Python

import sys

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

# 讀取輸入
a, b = input().split()
b = int(b)

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

# 計算第一段要用的數(shù)字個數(shù)
k = l - b + 1

# 計算答案
ans = 0

# 構(gòu)造第一段數(shù)字(較大的段)
first = 0
for i in range(k):
    first = first * 10 + digs[i]

# 加上第一段
ans += first

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

# 輸出結(jié)果
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;
    
    // 提取數(shù)字并排序
    vector<int> digs;
    for (char c : a) {
        digs.push_back(c - '0');
    }
    sort(digs.begin(), digs.end(), greater<int>());
    
    int l = digs.size();
    // 計算第一段數(shù)字個數(shù)
    int k = l - b + 1;
    
    // 計算答案
    long long ans = 0;