✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：优惠券组合策略

1️⃣：根据优惠券面值对3取模的结果进行分类讨论

2️⃣：使用动态规划维护以不同余数结尾的最优组合

3️⃣：状态转移时确保相邻优惠券面值之和为3的倍数

难度：中等

这道题目的关键在于理解相邻元素和为3倍数的条件，通过模运算将问题转化为状态转移。动态规划的状态设计巧妙，只需要维护三个状态就能解决问题，时间复杂度为 。

题目二：幸运数字计数系统

1️⃣：使用数位动态规划处理大数范围的计数问题

2️⃣：维护数字递增约束和数位和模数约束

3️⃣：通过记忆化搜索优化重复子问题的计算

难度：中等偏难

这道题目结合了数位DP和模运算，需要同时处理多个约束条件。关键在于正确设计状态转移，确保生成的数字满足非严格递增的要求，同时统计数位和的模数。记忆化的使用大大提高了算法效率。

01. 优惠券组合策略

问题描述

小基正在淘天商城的促销活动中设计一个优惠券组合策略。商城有 张不同面值的优惠券，编号为 到 ，第 张优惠券的面值为 元。

为了吸引顾客，商城推出了一种特殊的"黄金组合"优惠券使用规则：

• 单张优惠券可以单独使用

• 多张优惠券组合使用时，要求任意相邻两张优惠券的面值之和必须是 的倍数

小基希望从这 张优惠券中选择一些优惠券（保持原有顺序），组成一个"黄金组合"，使得优惠券面值的总和最大。

请帮助小基计算出最大的优惠券面值总和。

输入格式

第一行包含一个正整数 ()，表示优惠券的数量。

第二行包含 个正整数 ()，表示每张优惠券的面值。

输出格式

输出一个整数，表示最大的优惠券面值总和。

样例输入

6
1 1 4 5 1 4

样例输出

13

样例	解释说明
样例1	在面值为 的优惠券中，选择第3、4、6张优惠券（面值为 ），满足相邻面值之和都是3的倍数：（3的倍数），总面值为

数据范围

• 
• 

题解

这道题的关键在于理解"黄金组合"的规则：相邻两张优惠券面值之和必须是3的倍数。

首先分析什么时候两个数的和是3的倍数。对于任意两个整数 和 ，当且仅当 时，它们的和是3的倍数。这等价于：

• 如果 ，那么
• 如果 ，那么
• 如果 ，那么

因此，可以根据优惠券面值对3取模的结果，将其分为三类：余数为0、1、2。在一个合法的组合中，相邻优惠券的余数必须满足上述转移关系。

这是一个经典的动态规划问题。定义状态：

dp[r] 表示当前处理过的优惠券中，以余数为 （）结尾的合法组合的最大面值和。

对于每张新的优惠券 ，设其余数为 ：

1. 该优惠券可以单独组成一个组合，贡献为
2. 如果存在之前的合法组合能够与当前优惠券相接，则可以在该组合基础上追加当前优惠券

状态转移：

• 余数为0的优惠券只能接在余数为0的组合后面
• 余数为1的优惠券只能接在余数为2的组合后面
• 余数为2的优惠券只能接在余数为1的组合后面

最终答案为所有状态中的最大值。

时间复杂度：，空间复杂度：。

参考代码

• Python

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

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

# dp[r] 表示以余数r结尾的合法组合的最大面值和
# 使用负无穷表示不存在这样的组合
NEG_INF = float('-inf')
dp = [NEG_INF, NEG_INF, NEG_INF]
max_val = 0  # 至少可以选一张优惠券

for val in a:
    r = val % 3  # 当前优惠券面值的余数
    best = val   # 单独成组合
    
    # 尝试接在之前的组合后面
    if r == 0 and dp[0] != NEG_INF:
        best = max(best, dp[0] + val)
    elif r == 1 and dp[2] != NEG_INF:
        best = max(best, dp[2] + val)
    elif r == 2 and dp[1] != NEG_INF:
        best = max(best, dp[1] + val)
    
    # 更新状态
    dp[r] = max(dp[r], best)
    max_val = max(max_val, dp[r])

print(max_val)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // dp[r] 表示以余数r结尾的合法组合的最大面值和
    const long long NEG_INF = -1e18;
    long long dp[3] = {NEG_INF, NEG_INF, NEG_INF};
    long long maxVal = 0;  // 至少可以选一张优惠券
    
    for (int i = 0; i < n; i++) {
        long long val;
        cin >> val;
        int r = val % 3;  // 当前优惠券面值的余数
        long long best = val;  // 单独成组合
        
        // 尝试接在之前的组合后面
        if (r == 0 && dp[0] != NEG_INF) {
            best = max(best, dp[0] + val);
        } else if (r == 1 && dp[2] != NEG_INF) {
            best = max(best, dp[2] + val);
        } else if (r == 2 && dp[1] != NEG_INF) {
            best = max(best, dp[1] + val);
        }
        
        // 更新状态
        dp[r] = max(dp[r], best);
        maxVal = max(maxVal, dp[r]);
    }
    
    cout << maxVal << "\n";
    return 0;
}

• Java

import java.util.*;
import java.io.*;

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[] tokens = br.readLine().split(" ");
        
        // dp[r] 表示以余数r结尾的合法组合的最大面值和
        final long NEG_INF = Long.MIN_VALUE / 2;
        long[] dp = {NEG_INF, NEG_INF, NEG_INF};
        long maxVal = 0;  // 至少可以选一张优惠券
        
        for (int i = 0; i < n; i++) {
            long val = Long.parseLong(tokens[i]);
            int r = (int)(val % 3);  // 当前优惠券面值的余数
            long best = val;  // 单独成组合
            
            // 尝试接在之前的组合后面
            if (r == 0 && dp[0] != NEG_INF) {
                best = Math.max(best, dp[0] + val);
            } else if (r == 1 && dp[2] != NEG_INF) {
                best = Math.max(best, dp[2] + val);
            } else if (r == 2 && dp[1] != NEG_INF) {
                best = Math.max(best, dp[1] + val);
            }
            
            // 更新状态
            dp[r] = Math.max(dp[r], best);
            maxVal = Math.max(maxVal, dp[r]);
        }
        
        System.out.println(maxVal);
    }
}

02. 幸运数字计数系统

问题描述

小毛在淘天商城工作，负责设计一个幸运数字识别系统。在这个系统中，一个正整数被称为"幸运数字"，当且仅当它的各位数字从左