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

?? 學習建議：

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

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

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

春秋招合集 -> 互聯網必備刷題寶典??

淘天

題目一：字符交換智慧

1??：將字符按ASCII碼奇偶性分組

2??：對每組字符分別排序

3??：按照原字符串中字符的奇偶性填回排序后的字符

難度：中等

這道題目的關鍵在于理解ASCII碼奇偶性相同的字符才能相互交換的性質。通過將字符分組排序，可以在O(n log n)的時間復雜度內得到字典序最小的字符串。

題目二：秒殺順子查找

1??：利用動態(tài)規(guī)劃統(tǒng)計不同長度的順子子序列

2??：使用哈希表存儲狀態(tài)

3??：從長度1到5逐步構建順子子序列

難度：中等

這道題目結合了子序列和順子的概念，通過巧妙的動態(tài)規(guī)劃狀態(tài)設計，可以高效統(tǒng)計滿足條件的子序列數量，避免了暴力枚舉所有可能的組合。

題目三：數值平衡之道

1??：確定目標值為原始值的中位數

2??：利用樹形動態(tài)規(guī)劃計算最優(yōu)連通子圖

3??：通過后序和前序遍歷，計算最小操作成本

難度：中等偏難

這道題目需要綜合應用數學推導和樹形動態(tài)規(guī)劃，關鍵思路是將最小化成本問題轉化為尋找最大權連通子圖問題。通過巧妙的狀態(tài)設計，可以在O(n)的時間復雜度內解決問題。

01. 字符交換智慧

問題描述

小柯有一個長度為 的字符串 ，該字符串僅由大小寫字母構成。

她發(fā)現了一種神奇的交換規(guī)則：當兩個字符的 ASCII 碼差值為偶數時，它們可以被交換。具體來說，她可以進行任意次如下操作：

• 選擇兩個不同的位置 和 ，要求按照 ASCII 表， 為偶數。
• 交換 與 的值。

小柯想知道，經過任意次操作后，能得到的字典序最小的字符串是什么。

【字典序比較】：從字符串的第一個字符開始逐個比較，直到找到第一個不同的位置，通過比較這個位置字符的 ASCII 碼大小得到字符串的大小，稱為字典序比較。

輸入格式

第一行輸入一個正整數 ，表示字符串的長度。

第二行輸入一個字符串 ，保證僅由大小寫字母構成。

輸出格式

輸出一個字符串，表示可以經過操作得到的字典序最小的字符串。

樣例輸入

4
cfae

樣例輸出

afce

數據范圍

• 
• 字符串 僅由大小寫字母構成

樣例 解釋說明

樣例1	將 'c' 和 'a' 交換，'c'(99) 和 'a'(97) 的ASCII碼差為2（偶數），所以可以交換。交換后字符串變?yōu)?"afce"，這是可以得到的字典序最小的字符串。

題解

這道題目要求我們通過交換字符得到字典序最小的字符串，關鍵是理解交換的限制條件：只有ASCII碼差值為偶數的字符才能交換。

仔細分析可以發(fā)現一個重要性質：ASCII碼為奇數的字符只能與ASCII碼為奇數的字符交換，ASCII碼為偶數的字符只能與ASCII碼為偶數的字符交換。這是因為兩個奇數或兩個偶數的差值一定是偶數，而一個奇數和一個偶數的差值一定是奇數。

根據這個性質，我們可以將字符串中的字符分成兩組：

1. ASCII碼為奇數的字符組
2. ASCII碼為偶數的字符組

在每組內，字符可以任意交換位置。因此，為了得到字典序最小的字符串，我們應該：

1. 將奇數組的字符按升序排序
2. 將偶數組的字符按升序排序
3. 按照原字符串中字符的奇偶性，依次填入排序后的奇數或偶數字符

例如對于示例"cfae"：

• 'c'的ASCII碼是99（奇數）
• 'f'的ASCII碼是102（偶數）
• 'a'的ASCII碼是97（奇數）
• 'e'的ASCII碼是101（奇數）

奇數組：['c', 'a', 'e'] → 排序后變成 ['a', 'c', 'e'] 偶數組：['f'] → 排序后還是 ['f']

然后按照原字符串中字符的奇偶性重構：

• 第1個位置原來是'c'（奇數），填入'a'
• 第2個位置原來是'f'（偶數），填入'f'
• 第3個位置原來是'a'（奇數），填入'c'
• 第4個位置原來是'e'（奇數），填入'e'

得到結果："afce"，這就是字典序最小的字符串。

算法的時間復雜度是 O(n log n)，主要來自對兩組字符的排序，空間復雜度是 O(n)。

參考代碼

• Python

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

# 讀取輸入
n = int(input())
s = input()

# 將字符分為ASCII碼奇數和偶數兩組
odd = []
even = []
for c in s:
    if ord(c) % 2 == 0:
        even.append(c)
    else:
        odd.append(c)

# 對兩組字符分別排序
odd.sort()
even.sort()

# 構建結果字符串
res = ""
oi, ei = 0, 0
for c in s:
    if ord(c) % 2 == 0:
        # ASCII碼為偶數的位置
        res += even[ei]
        ei += 1
    else:
        # ASCII碼為奇數的位置
        res += odd[oi]
        oi += 1

print(res)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 讀取輸入
    int n;
    string s;
    cin >> n >> s;
    
    // 分離奇偶ASCII碼字符
    vector<char> odd, even;
    for (char ch : s) {
        if (ch % 2 == 0) {
            even.push_back(ch);
        } else {
            odd.push_back(ch);
        }
    }
    
    // 排序
    sort(odd.begin(), odd.end());
    sort(even.begin(), even.end());
    
    // 構建結果
    string ans = "";
    int o = 0, e = 0;
    for (char ch : s) {
        if (ch % 2 == 0) {
            ans += even[e++];
        } else {
            ans += odd[o++];
        }
    }
    
    cout << ans << endl;
    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();
        sc.nextLine(); // 消耗換行符
        String s = sc.nextLine();
        
        // 分離奇偶ASCII碼字符
        List<Character> odd = new ArrayList<>();
        List<Character> even = new ArrayList<>();
        
        for (char c : s.toCharArray()) {
            if (c % 2 == 0) {
                even.add(c);
            } else {
                odd.add(c);
            }
        }
        
        // 排序
        Collections.sort(odd);
        Collections.sort(even);
        
        // 構建結果
        StringBuilder res = new StringBuilder();
        int oddIdx = 0, evenIdx = 0;
        
        for (char c : s.toCharArray()) {
            if (c % 2 == 0) {
                res.append(even.get(evenIdx++));
            } else {
                res.append(odd.get(oddIdx++));
            }
        }
        
        System.out.println(res.toString());
    }
}

02. 秒殺順子查找

問題描述

小蘭是一名熱愛撲克牌的玩家。她定義一個數列是"順子"，當且僅當將該數列排序后，每個元素恰好比前一個元素大 。比如， 排序后是 ，相鄰元素之差為 ，所以這是一個"順子"。而 排序后是 ，包含重復元素，不滿足條件，所以不是"順子"。

現在，小蘭拿到了一個長度為 的數列，她想知道這個數列中有多少個長度恰好為 的子序列可以構成"順子"。由于答案可能很大，請將結果對 取模后輸出。

【子序列定義】：從原數列中選取部分元素并保持它們在原數列中的相對順序組成的新數列，稱為原數列的子序列。例如，對于數列 ， 是其子序列，而 不是，因為不滿足相對順序。

輸入格式

第一行輸入一個正整數 ，代表數列的長度。

第二行輸入 個正整數 ，代表數列的元素。

輸出格式

一個整數，代表順子的數量對 取模的值。

樣例輸入

6
1 2 3 4 5 6

樣例輸出

2

樣例輸入

10
1 2 3 4 5 1 2 3 4 5

樣例輸出

32

數據范圍

• 
• 

樣例 解釋說明

樣例1	數列 [1,2,3,4,5,6] 中，可以構成順子的長度為5的子序列有 [1,2,3,4,5] 和 [2,3,4,5,6]，共2個
樣例2	數列 [1,2,3,4,5,1,2,3,4,5] 中，有多種方式可以選取元素組成長度為5的順子，例如可以從數列前半部分選擇5個連續(xù)數，也可以從后半部分選擇，還可以混合選擇。計算得到共有32個滿足條件的子序列

題解

這道題目要求我們計算長度為5的順子子序列的數量。首先明確一下，順子是指排序后相鄰元素之差為1的數列，長度為5的順子實際上就是連續(xù)的5個整數。

關鍵是理解：無論這5個數的初始順序如何，只要它們組成連續(xù)的5個整數，就構成一個順子。

一個巧妙的解法是使用動態(tài)規(guī)劃，定義狀態(tài)：

• dp[1][v]：以值v結尾的長度為1的子序列個數
• dp[2][v]：以值v結尾的長度為2的子序列個數，且這些子序列滿足條件（即v前面的數等于v-1）
• dp[3][v]：以值v結尾的長度為3的子序列個數，且滿足順子條件
• dp[4][v]：以值v結尾的長度為4的子序列個數，且滿足順子條件
• dp[5][v]：以值v結尾的長度為5的子序列個數，且滿足順子條件

狀態(tài)轉移方程為：

1. dp[1][v] += 1（每次遇到值v，長度為1的子序列增加1個）
2. dp[2][v] += dp[1][v-1]（以v-1結尾的長度為1的子序列后面接上v，構成長度為2的子序列）
3. dp[3][v] += dp[2][v-1]（以v-1結尾的長度為2的子序列后面接上v，構成長度為3的子序列）
4. dp[4][v] += dp[3][v-1]（以此類推）
5. dp[5][v] += dp[4][v-1]（以此類推）

最終答案是所有dp[5][v]的總和。

由于數據范圍較大（a_i可達10^9），我們可以使用哈希表而不是數組來存儲狀態(tài)，以節(jié)省空間。

例如，對于樣例1 [1,2,3,4,5,6]：

• 處理1：dp[1][1]=1
• 處理2：dp[1][2]=1, dp[2][2]=dp[1][1]=1
• 處理3：dp[1][3]=1, dp[2][3]=dp[1][2]=1, dp[3][3]=dp[2][2]=1
• 處理4：dp[1][4]=1, dp[2][4]=dp[1][3]=1, dp[3][4]=dp[2][3]=1, dp[4][4]=dp[3][3]=1
• 處理5：dp[1][5]=1, dp[2][5]=dp[1][4]=1, dp[3][5]=dp[2][4]=1, dp[4][5]=dp[3][4]=1, dp[5][5]=dp[4][4]=1
• 處理6：dp[1][6]=1, dp[2][6]=dp[1][5]=1, dp[3][6]=dp[2][5]=1, dp[4][6]=dp[3][5]=1, dp[5][6]=dp[4][5]=1

最終答案為dp[5][5]+dp[5][6]=1+1=2。

算法的時間復雜度是O(n)，空間復雜度也是O(n)，可以高效處理給定的數據范圍。

參考代碼

• Python

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

# 讀取輸入
n = int(input())
arr = list(map(int, input().split()))

# 初始化哈希表
MOD = 10**9 + 7
dp1 = {}  # 長度為1的子序列
dp2 = {}  # 長度為2的順子子序列
dp3 = {}  # 長度為3的順子子序列
dp4 = {}  # 長度為4的順子子序列

# 動態(tài)規(guī)劃過程
ans = 0
for val in arr:
    # 獲取前一個值的各長度順子數量
    c4 = dp4.get(val-1, 0)
    c3 = dp3.get(val-1, 0)
    c2 = dp2.get(val-1, 0)
    c1 = dp1.get(val-1, 0)
    
    # 累加長度為5的順子數量
    ans = (ans + c4) % MOD
    
    # 更新狀態(tài)
    dp4[val] = (dp4.get(val, 0) + c3) % MOD
    dp3[val] = (dp3.get(val, 0) + c2) % MOD
    dp2[val] = (dp2.g