✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

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

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

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

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

题目一：魔法数字重组

1️⃣：拆分所有数字为独立数位，计算每个位置的权重

2️⃣：使用贪心策略，将最大数位分配给最大权重位置

3️⃣：对数位和权重分别降序排序，一一对应相乘求和

难度：中等

这道题目的关键在于理解数字重组的本质，将问题转化为数位与权重的匹配。通过贪心策略，我们可以用 O(D log D) 的时间复杂度得到最优解，其中 D 是总数位数。

题目二：小柯的珠宝收藏

1️⃣：理解问题本质：在前缀中选择固定数量的元素，最小化代价

2️⃣：使用动态规划，dp[m][i] 表示选择m个元素且最后选在位置i的最小珠宝价值

3️⃣：利用前缀最小值优化状态转移，使用滚动数组节省空间

难度：中等

这道题目结合了动态规划和贪心思想，需要理解如何在保持顺序的前提下选择元素。通过巧妙的状态设计和优化，实现了 O(n²) 的时间复杂度。

题目三：小毛的古籍修复

1️⃣：将问题分解为多个独立区间的填补问题

2️⃣：每个区间使用多重组合数学公式 C(D+c, c) 计算方案数

3️⃣：处理大数组合数计算，使用逆元和阶乘预处理优化

难度：中等偏难

这道题目考查组合数学和数论知识，需要理解非严格递增序列的性质。通过将大数组合数分解和逆元计算，实现了 O(n) 的高效解法。

01. 魔法数字重组

问题描述

小基 是一位热爱数字魔法的魔法师。她发现了一种神奇的魔法，可以将手中的 张数字卡片重新组合来获得最大的魔法能量。

每张卡片上都写着一个正整数，小基 现在手中有 张卡片，第 张卡片上的数字为 。

小基 的魔法规则如下：

1. 首先，将所有卡片上的数字按十进制拆分，得到所有的单个数位
2. 然后，重新分配这些数位给每张卡片，但每张卡片的位数必须保持原来的位数不变
3. 最后，计算所有卡片上新数字的总和，这就是魔法能量值

小基 想要通过合理安排数位分配，使得魔法能量值达到最大。请帮助她计算出最大的魔法能量值。

输入格式

第一行包含一个正整数 （），表示卡片的数量。

第二行包含 个正整数 （），表示每张卡片上的初始数字。题目保证每个数字的十进制表示中不含字符 。

输出格式

输出一个整数，表示通过魔法重组后能获得的最大魔法能量值。

样例输入

2
36 15

样例输出

114

数据范围

• 
• 
• 所有数字不含字符

题解

这道题本质上是一个贪心问题。关键观察是：要让总和最大，应该让较大的数位占据权重更高的位置。

具体思路如下：

1. 拆分数位：将所有数字拆分成单独的数位，比如 36 拆分为 3 和 6。

2. 计算权重：每个数位在最终数字中的权重取决于它所在的位置。比如一个两位数，十位的权重是 10，个位的权重是 1。

3. 贪心分配：为了让总和最大，应该将最大的数位分配给权重最高的位置。

4. 排序匹配：将所有数位按降序排列，将所有权重按降序排列，然后一一对应相乘求和。

例如样例中：

• 数位：[6, 5, 3, 1]（降序）
• 权重：[10, 10, 1, 1]（降序，两个十位和两个个位）
• 结果：6×10 + 5×10 + 3×1 + 1×1 = 60 + 50 + 3 + 1 = 114

算法时间复杂度为 ，其中 是总数位数。空间复杂度为 。

参考代码

• Python

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

n = int(input())
nums = list(map(int, input().split()))

# 提取所有数位和计算权重
def solve():
    digs = []  # 存储所有数位
    wgts = []  # 存储对应权重
    
    # 预计算10的幂次
    pow10 = [1]
    for i in range(1, 10):
        pow10.append(pow10[-1] * 10)
    
    # 处理每个数字
    for num in nums:
        s = str(num)
        ln = len(s)
        
        # 提取数位
        for ch in s:
            digs.append(int(ch))
        
        # 计算权重
        for pos in range(ln):
            exp = ln - 1 - pos
            wgts.append(pow10[exp])
    
    # 贪心：大数位配大权重
    digs.sort(reverse=True)
    wgts.sort(reverse=True)
    
    # 计算结果
    res = 0
    for i in range(len(digs)):
        res += digs[i] * wgts[i]
    
    return res

print(solve())

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> digs, lens;
    digs.reserve(n * 10);
    
    // 读取并拆分数位
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        lens.push_back(s.size());
        for (char c : s) {
            digs.push_back(c - '0');
        }
    }
    
    // 生成权重数组
    vector<ll> wgts;
    wgts.reserve(digs.size());
    ll pw = 1;
    vector<ll> pow10(10);
    for (int i = 0; i < 10; i++) {
        pow10[i] = pw;
        pw *= 10;
    }
    
    for (int ln : lens) {
        for (int p = 0; p < ln; p++) {
            int exp = ln - 1 - p;
            wgts.push_back(pow10[exp]);
        }
    }
    
    // 降序排序
    sort(digs.rbegin(), digs.rend());
    sort(wgts.rbegin(), wgts.rend());
    
    // 计算答案
    ll ans = 0;
    for (size_t i = 0; i < digs.size(); i++) {
        ans += (ll)digs[i] * wgts[i];
    }
    
    cout << ans << "\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());
        String[] nums = br.readLine().split(" ");
        
        List<Integer> digs = new ArrayList<>();
        List<Long> wgts = new ArrayList<>();
        
        // 预计算10的幂次
        long[] pow10 = new long[10];
        pow10[0] = 1;
        for (int i = 1; i < 10; i++) {
            pow10[i] = pow10[i-1] * 10;
        }
        
        // 处理每个数字
        for (String numStr : nums) {
            int ln = numStr.length();
            
            // 提取数位
            for (char c : numStr.toCharArray()) {
                digs.add(c - '0');
            }
            
            // 计算权重
            for (int pos = 0; pos < ln; pos++) {
                int exp = ln - 1 - pos;
                wgts.add(pow10[exp]);
            }
        }
        
        // 降序排序
        Collections.sort(digs, Collections.reverseOrder());
        Collections.sort(wgts, Collections.reverseOrder());
        
        // 计算答案
        long ans = 0;
        for (int i = 0; i < digs.size(); i++) {
            ans += (long)digs.get(i) * wgts.get(i);
        }
        
        System.out.println(ans);
    }
}

02. 小柯的珠宝收藏

问题描述

小柯是一位珠宝收藏家，她拥有一条由 颗珠宝组成的项链。每颗珠宝都有一个价值 ，按照在项链上的顺序排列为 。

最近，小柯想要重新设计这条项链。她的设计方案是：对于每个长度 （），她可以选择保留项链前 颗珠宝，但为了保持设计的美观性，她可能需要移除一些中间的珠宝。

具体规则如下：

• 移除每颗珠宝需要支付 的加工费用
• 最终保留的 颗珠宝必须是项链中最前面的 颗（按原始顺序）
• 设计的总成本 = 移除次数 保留珠宝的价值总和

小柯想知道，对于每个可能的长度 ，设计成本的最小值是多少。

输入格式

第一行包含一个正整数 （），表示测试用例的数量。

对于每个测试用例：

• 第一行包含两个正整数 （），分别表示珠宝数量和移除费用。
• 第二行包含 个正整数 （），表示每颗珠宝的价值。

保证单个测试文件中所有 的总和不超过 。

输出格式

对于每个测试用例，输出一行包含 个整数，第 个整数表示保留 颗珠宝时的最小设计成本，用空格分隔。

样例输入

1
3 1
4 2 3

样例输出

3 6 9

样例编号	解释说明
样例1	对于 ：可以保留第3颗珠宝（价值3），移除前2颗，成本=2×1+3=5；或保留第2颗珠宝（价值2），移除第1颗，成本=1×1+2=3；或保留第1颗珠宝（价值4），成本=0×1+4=4。最小值为3。对于 ：保留第2、3颗珠宝，移除第1颗，成本=1×1+2+3=6。对于 ：保留全部，成本=0×1+4+2+3=9。

数据范围

题解

这是一个动态规划问题。关键观察是：要保留前 颗珠宝，实际上是要在原项链的某个前缀中选择 颗珠宝，使得总成本最小。

设 表示选择 颗珠宝且最后一颗选在位置 时，珠宝价值总和的最小值。

状态转移方程：

• （选择第 颗作为唯一珠宝）
• （在位置 放第 颗珠宝）

对于每个 ，答案是：

其中 表示在前 个位置中移除了多少颗珠宝。

算法使用滚动数组优化空间，时间复杂度 ，空间复杂度 。

参考代码

• Python

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

def solve():
    n, k = map(int, input().split())
    a = [0] + list(map(int, input().split()))  # 1-indexed
    
    INF = float('inf')
    prev = [INF] * (n + 1)
    curr = [INF] * (n + 1)
    ans = [INF] * (n + 1)
    
    # 初始化 m=1 的情况
    for i in range(1, n + 1):
        prev[i] = a[i]
    
    # 计算 m=1 的答案
    for i in range(1, n + 1):
        ans[1] = min(ans[1], prev[i] + k * (i - 1))
    
    # 动态规划计算 m=2 到 n
    for m in range(2, n + 1):
        best = INF  # 前缀最小值
        for i in range(m, n + 1):
            if i > m:
                best = min(best, prev[i - 1])
            if i == m:
                best = prev[m - 1] if m > 1 else INF
            curr[i] = a[i] + best
        
        # 计算当前 m 的答案
        res = INF
        for i in range(m, n + 1):
            res = min(res, curr[i] + k * (i - m))
        ans[m] = res
        
        # 滚动数组
        prev, curr = curr, prev
        for i in range(n + 1):
            curr[i] = INF
    
    return ' '.join(map(str, ans[1:n+1]))

T = int(input())
for _ in range(T):
    print(solve())

• Cpp

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

const ll INF = 4e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        ll k;
        cin >> n >> k;