✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

淘天

题目一：字符交换智慧

1️⃣：将字符按ASCII码奇偶性分组

2️⃣：对每组字符分别排序

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

难度：中等

这道题目的关键在于理解ASCII码奇偶性相同的字符才能相互交换的性质。通过将字符分组排序，可以在O(n log n)的时间复杂度内得到字典序最小的字符串。

题目二：秒杀顺子查找

1️⃣：利用动态规划统计不同长度的顺子子序列

2️⃣：使用哈希表存储状态

3️⃣：从长度1到5逐步构建顺子子序列

难度：中等

这道题目结合了子序列和顺子的概念，通过巧妙的动态规划状态设计，可以高效统计满足条件的子序列数量，避免了暴力枚举所有可能的组合。

题目三：数值平衡之道

1️⃣：确定目标值为原始值的中位数

2️⃣：利用树形动态规划计算最优连通子图

3️⃣：通过后序和前序遍历，计算最小操作成本

难度：中等偏难

这道题目需要综合应用数学推导和树形动态规划，关键思路是将最小化成本问题转化为寻找最大权连通子图问题。通过巧妙的状态设计，可以在O(n)的时间复杂度内解决问题。

01. 字符交换智慧

问题描述

小柯有一个长度为 的字符串 ，该字符串仅由大小写字母构成。

她发现了一种神奇的交换规则：当两个字符的 ASCII 码差值为偶数时，它们可以被交换。具体来说，她可以进行任意次如下操作：

• 选择两个不同的位置 和 ，要求按照 ASCII 表， 为偶数。
• 交换 与 的值。

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

【字典序比较】：从字符串的第一个字符开始逐个比较，直到找到第一个不同的位置，通过比较这个位置字符的 ASCII 码大小得到字符串的大小，称为字典序比较。

输入格式

第一行输入一个正整数 ，表示字符串的长度。

第二行输入一个字符串 ，保证仅由大小写字母构成。

输出格式

输出一个字符串，表示可以经过操作得到的字典序最小的字符串。

样例输入

4
cfae

样例输出

afce

数据范围

• 
• 字符串 仅由大小写字母构成

题解

这道题目要求我们通过交换字符得到字典序最小的字符串，关键是理解交换的限制条件：只有ASCII码差值为偶数的字符才能交换。

仔细分析可以发现一个重要性质：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

数据范围

题解

这道题目要求我们计算长度为5的顺子子序列的数量。首先明确一下，顺子是指排序后相邻元素之差为1的数列，长度为5的顺子实际上就是连续的5个整数。

关键是理解：无论这5个数的初始顺序如何，只要它们组成连续的5个整数，就构成一个顺子。

一个巧妙的解法是使用动态规划，定义状态：

• 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的子序列个数，且满足顺子条件

状态转移方程为：

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），我们可以使用哈希表而不是数组来存储状态，以节省空间。

例如，对于样例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的顺子子序列

# 动态规划过程
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
    
    # 更新状态
    dp4[val] = (dp4.get(val, 0) + c3) % MOD
    dp3[val] = (dp3.get(val, 0) + c2) % MOD
    dp2[val] = (dp2.get