✅ 春招备战指南 ✅

💡 学习建议：

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

互联网必备刷题宝典🔗

题目一：收藏家的序列价值

1️⃣：识别排列子序列的核心性质——必须包含从 1 到长度 k 的连续整数

2️⃣：构建动态规划解法，递推形成长度为 k 的排列子序列数量

3️⃣：通过加权求和计算最终价值总和

整体难度：中等

这道题目要求统计一个数组中满足特定条件的所有子序列价值之和。关键观察是：有价值的子序列必须严格递增且恰好包含 1 到某个 k 的所有整数。通过动态规划，定义 表示能形成序列 的方案数，在遇到元素 1 时初始化子序列，遇到 k>1 时将其接在已有的 子序列后面。最终价值等于每种长度 k 的子序列数量乘以 k 的总和。时间和空间复杂度均为 。

题目二：优雅字符串的探索

1️⃣：利用去重后字典序递增的关键特性定义优雅字符串

2️⃣：逆序遍历字符串，处理每个可能的子串左端点

3️⃣：维护字符的最新出现位置，从字典序最大的字符开始检查确保递增性

整体难度：中等

本题引入了"优雅字符串"的新概念：去重后字符按原顺序排列时字典序递增。关键挑战在于快速判断从每个位置开始的所有子串中哪些满足优雅条件。采用逆序遍历的巧妙策略，对每个位置作为左端点，通过维护字符最后出现位置和从大到小检查字符字典序，可以确定能够形成优雅子串的最远右边界。算法时间复杂度为 ，空间复杂度为 ，非常适合处理长度不超过 的字符串。

题目三：艺术展览的最优摆放

1️⃣：分解交换操作带来的得分增益，得到简化公式

2️⃣：利用 值范围有限的特性进行分组优化

3️⃣：根据 与 大小关系选择最优的 值组合

整体难度：中等偏难

这道题目探讨了如何通过最多一次交换操作最大化艺术展览的评分。通过数学推导，发现交换元素 和 带来的评分变化可简化为 。基于此洞察，不需要考虑所有可能的交换对，而是可以按 值分组记录 的最大值和最小值，然后枚举所有可能的 组合。这种方法将时间复杂度从朴素的 优化到 ，其中 是 的最大值 1000，非常适合处理数据规模达到 的情况。

01. 收藏家的序列价值

题目内容

小基是一位收藏家，非常喜欢收集各种序列。他特别关注序列的"价值"，并制定了一套独特的价值评估体系：

• 如果一个序列不是严格递增的，它的价值为 。
• 如果一个序列是严格递增的，并且恰好包含从 到序列长度的所有整数（即形成一个排列），那么它的价值就等于序列的长度。

现在，小基有一个长度为 的整数序列 ，他想知道这个序列中所有可能的"排列子序列"（即满足上述条件的子序列）的价值总和是多少。请你帮他计算这个总和。

输入描述

每个测试文件包含多组测试数据。

第一行一个正整数 ，表示测试数据的组数。

对于每组测试数据，输入包含两行。

第一行一个正整数 ，表示序列 的长度。

第二行 个整数 ，表示序列 的各个元素。

保证所有测试数据中 的总和不超过 。

输出描述

输出 行，每行一个整数表示当前测试用例的答案，即所有"排列子序列"的价值总和。

由于答案可能很大，因此你只需要输出答案对 取模的结果。

样例1

输入：

1
3
1 1 2

输出：

6

题解

这道题目要求计算一个数组中所有"排列子序列"的价值总和。所谓的"排列子序列"，指的是严格递增且恰好包含从 1 到 k 的所有整数的子序列，其价值就是长度 k。

仔细思考这个问题，可以发现，一个子序列要想成为有效的"排列子序列"，必须是形如 的形式，也就是说，它必须从 1 开始，然后依次包含 ，不能有遗漏，也不能有重复。

基于这个理解，可以通过动态规划来解决问题。定义 表示数组中能形成的子序列 的个数。那么：

• 当遇到数组中的元素 时，可以开始一个新的子序列，所以 增加 1。
• 当遇到 时，如果已经存在子序列 ，可以把 v 接在这些子序列后面，形成新的子序列 ，所以 增加 。

最终，子序列 的总价值是 乘以 ，需要计算所有 k 的总和。

这种算法的时间复杂度是 ，其中 n 是数组的长度。空间复杂度也是 ，用于存储 dp 数组。

对于较大的输入，由于结果可能很大，题目要求对 1000000007 取模，这也是常见的做法。

三语言参考代码

• Cpp

#include <bits/stdc++.h>
using namespace std;

const int MAD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int test;
    cin >> test;  // 测试用例数量
    
    while (test--) {
        int size;
        cin >> size;  // 序列长度
        
        vector<int> dat(size);
        for (int i = 0; i < size; ++i) {
            cin >> dat[i];  // 输入序列
        }
        
        // dp[i]表示子序列[1,2,...,i]的数量
        vector<long long> memo(size + 1, 0);
        
        for (int i = 0; i < size; ++i) {
            int val = dat[i];
            if (val == 1) {
                // 可以新建一个只含1的子序列
                memo[1] = (memo[1] + 1) % MAD;
            } else {
                // 可以将val接到现有的子序列[1,2,...,val-1]后面
                memo[val] = (memo[val] + memo[val - 1]) % MAD;
            }
        }
        
        // 计算所有子序列的价值和
        long long ans = 0;
        for (int i = 1; i <= size; ++i) {
            ans = (ans + i * memo[i]) % MAD;
        }
        
        cout << ans << endl;
    }
    
    return 0;
}

• Python

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

MAD = 10**9 + 7

def calc_value():
    T = int(input())  # 测试用例数量
    
    for _ in range(T):
        size = int(input())  # 序列长度
        seq = list(map(int, input().split()))  # 输入序列
        
        # memo[i] 表示子序列 [1,2,...,i] 的数量
        memo = [0] * (size + 1)
        
        for val in seq:
            if val == 1:
                # 可以新建一个只含1的子序列
                memo[1] = (memo[1] + 1) % MAD
            else:
                # 可以将val接到现有的子序列[1,2,...,val-1]后面
                memo[val] = (memo[val] + memo[val-1]) % MAD
        
        # 计算所有子序列的价值和
        total = 0
        for i in range(1, size + 1):
            total = (total + i * memo[i]) % MAD
            
        print(total)

if __name__ == "__main__":
    calc_value()

• Java

import java.util.Scanner;

public class Main {
    static final int MAD = 1000000007;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int test = scan.nextInt();  // 测试用例数量
        
        while (test-- > 0) {
            int size = scan.nextInt();  // 序列长度
            int[] seq = new int[size];
            
            for (int i = 0; i < size; i++) {
                seq[i] = scan.nextInt();  // 输入序列
            }
            
            // memo[i]表示子序列[1,2,...,i]的数量
            long[] memo = new long[size + 1];
            
            for (int i = 0; i < size; i++) {
                int val = seq[i];
                if (val == 1) {
                    // 可以新建一个只含1的子序列
                    memo[1] = (memo[1] + 1) % MAD;
                } else if (val <= size) {
                    // 可以将val接到现有的子序列[1,2,...,val-1]后面
                    memo[val] = (memo[val] + memo[val - 1]) % MAD;
                }
            }
            
            // 计算所有子序列的价值和
            long res = 0;
            for (int i = 1; i <= size; i++) {
                res = (res + i * memo[i]) % MAD;
            }
            
            System.out.println(res);
        }
    }
}

02. 优雅字符串的探索

题目内容

小柯是一位语言学家，她对字符串有着独特的研究。她定义了一种"优雅字符串"的概念：当一个字符串去重后（保留每个字符首次出现的位置，删除后续重复出现），按照原始相对顺序排列的字符是字典序单调递增的，则称这个字符串为"优雅字符串"。

例如，字符串 aabca 去重后为 abc，而 abc 在字典序上是单调递增的，因此 aabca 是一个"优雅字符串"。

现在，小柯有一个长度为 的字符串 ，她想知道这个字符串中有多少个非空子串是"优雅字符串"。请你帮她计算这个数量。

输入描述

第一行一个整数 ，表示字符串长度。

第二行一个长度为 的字符串 ，保证输入只含小写字母。

输出描述

一个整数，表示 中有多少个子串是"优雅字符串"。

样例1

输入：

5
aabca

输出：

13

题解

这道题目要求统计一个字符串中所有"优雅字符串"的数量。什么是"优雅字符串"呢？就是当一个字符串去重后（只保留每个字符首次出现的位置），剩下的字符按原来的相对顺序排列，在字典序上是单调递增的。

首先，需要明确一点：如果一个字符串的去重后结果是字典序递增的，那么它所有的子串也肯定是"优雅字符串"吗？不一定。因为当取子串时，某些字符的首次出现位置可能会改变，从而影响去重后的结果。

因此，需要对每一个可能的子串都进行检查。一种直观的思路是，对于每个可能的左端点 left，找出它右边能扩展到的最远位置 right，使得从 left 到 right 的子串都是"优雅字符串"。

可以通过逆序遍历字符串来实现这个思路：

1. 从右向左遍历字符串，对于每个位置 left，计算以它为左端点的"优雅子串"的数量。
2. 维护一个数组 mark，记录每个字符最后一次出现的位置。
3. 对于当前位置 left，设定一个初始的右边界 right 和一个限制值 limit（初始都设为 n，即字符串长度）。
4. 然后从字典序最大的字符'z'开始向前遍历到'a'，更新右边界和限制值。
5. 如果某个字符 c 出现过，且右边界 right 小于 c 最后出现的位置，那么需要更新 limit 为 min(limit, mark[c])。这是为了确保去重后的结果保持字典序递增。
6. 计算以 left 为左端点的"优雅子串"数量，即(limit - left)，累加到结果中。

这个算法的时间复杂度是 ，其中 n 是字符串长度，因为对于每个位置，都需要遍历 26 个小写字母。空间复杂度是 ，因为只需要一个固定大小的数组来记录每个字符最后出现的位置。

三语言参考代码

• Cpp

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

int main() {
    int len;
    string data;
    cin >> len >> data;
    
    long long cnt = 0;  // 记录优雅子串的总数
    vector<int> mark(26, -1)