✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：小兰的珠宝设计工坊

1️⃣：计算前缀总子串数，用数学公式求解对称美珠宝数量

2️⃣：维护颜色计数器，在线更新对称美珠宝的增量

3️⃣：用总子串数减去对称美珠宝数得到最终答案

难度：中等

这道题目的关键在于理解对称美珠宝和不对称美珠宝的定义，并通过数学公式避免暴力枚举。通过维护颜色频次和在线计算，可以在 O(n) 时间内解决问题，体现了数学建模的优雅性。

题目二：小毛的音乐节拍创作系统

1️⃣：建立带约束的动态规划状态，分别记录以不同长度结尾的方案数

2️⃣：处理"a后不能跟c"的约束，在状态转移时排除非法情况

3️⃣：按顺序计算各长度方案数，注意模运算和边界条件

难度：中等

这道题目巧妙地将约束条件融入动态规划的状态设计中。通过分类讨论不同结尾状态，可以有效处理复杂的约束关系。算法的精髓在于如何在状态转移中正确排除违反约束的情况。

题目三：小基的智能网络基站优化方案

1️⃣：分析两种策略的性质，识别出x≥y时的简单情况

2️⃣：将复杂情况转化为树上最大匹配问题

3️⃣：使用树形DP计算最大匹配，通过状态转移求解最优方案

难度：中等偏难

这道题目的精髓在于将看似复杂的操作问题转化为经典的图论问题。通过观察策略的本质，可以发现问题等价于树上的最大匹配。树形动态规划的应用展现了算法设计中"化繁为简"的思想。

01. 小兰的珠宝设计工坊

问题描述

小兰是一位著名的珠宝设计师，她的工坊专门制作独特的项链。小兰有一个特殊的设计理念：她认为"对称美珠宝"（即项链的第一颗珠子和最后一颗珠子颜色相同）过于普通，缺乏创意。因此，她更偏爱制作"不对称美珠宝"。

现在小兰有一串由 颗不同颜色珠子组成的原材料，每颗珠子用一个小写字母表示其颜色。她想要分析这串珠子的设计潜力：对于这串珠子的每一个前缀部分，计算出能从中截取多少种不同长度的连续珠宝片段，使得这些片段都是"不对称美珠宝"。

具体来说，小兰需要依次考虑原材料的前 颗、前 颗、...、前 颗珠子，对于每种情况，计算所有可能的连续片段中有多少个是不对称美珠宝（即第一颗和最后一颗珠子颜色不同）。

输入格式

第一行包含一个正整数 ，表示珠子总数。

第二行包含一个长度为 的字符串 ，由小写字母组成，表示每颗珠子的颜色。

输出格式

输出 行，第 行输出一个整数，表示原材料前 颗珠子的所有连续片段中，不对称美珠宝的数量。

样例输入

4
abda

样例输出

0
1
3
5

数据范围

• 

• 字符串只包含小写字母

题解

这道题的关键是理解什么是对称美珠宝和不对称美珠宝，然后高效地统计数量。

问题分析： 对称美珠宝指的是首尾珠子颜色相同的连续片段，不对称美珠宝则相反。对于任意长度的前缀，需要计算其所有子串中不对称美珠宝的数量。

核心思路： 可以用总的子串数量减去对称美珠宝的数量来得到答案。对于长度为 的前缀：

• 总子串数量 =
• 对称美珠宝数量 = 所有相同字符形成的子串数量之和

算法步骤：

1. 对于每个前缀，维护每种颜色的出现次数
2. 对于颜色 出现 次，它能形成的对称美珠宝数量为
3. 总的对称美珠宝数量是所有颜色的贡献之和
4. 不对称美珠宝数量 = 总子串数 - 对称美珠宝数

在线算法： 当处理第 个位置时，新增的对称美珠宝数量等于之前相同颜色的出现次数加1（包括当前位置的单个字符）。

时间复杂度：，空间复杂度：（只需要26个字母的计数器）。

参考代码

• Python

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

n = int(input())
s = input()

# 统计每种颜色的出现次数
color_cnt = [0] * 26
sym_cnt = 0  # 对称美珠宝总数

for i in range(n):
    # 获取当前珠子颜色
    color = ord(s[i]) - ord('a')
    
    # 新增的对称美珠宝数量
    sym_cnt += color_cnt[color] + 1
    
    # 更新颜色计数
    color_cnt[color] += 1
    
    # 计算前i+1个珠子的总子串数
    length = i + 1
    total_cnt = length * (length + 1) // 2
    
    # 输出不对称美珠宝数量
    print(total_cnt - sym_cnt)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    string s;
    cin >> n >> s;
    
    // 统计每种颜色的出现次数
    vector<long long> color_cnt(26, 0);
    long long sym_cnt = 0;  // 对称美珠宝总数
    
    for (int i = 0; i < n; i++) {
        // 获取当前珠子颜色
        int color = s[i] - 'a';
        
        // 新增的对称美珠宝数量
        sym_cnt += color_cnt[color] + 1;
        
        // 更新颜色计数
        color_cnt[color]++;
        
        // 计算前i+1个珠子的总子串数
        long long length = i + 1;
        long long total_cnt = length * (length + 1) / 2;
        
        // 输出不对称美珠宝数量
        cout << total_cnt - sym_cnt << '\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 s = br.readLine();
        
        // 统计每种颜色的出现次数
        long[] colorCnt = new long[26];
        long symCnt = 0;  // 对称美珠宝总数
        
        for (int i = 0; i < n; i++) {
            // 获取当前珠子颜色
            int color = s.charAt(i) - 'a';
            
            // 新增的对称美珠宝数量
            symCnt += colorCnt[color] + 1;
            
            // 更新颜色计数
            colorCnt[color]++;
            
            // 计算前i+1个珠子的总子串数
            long length = i + 1;
            long totalCnt = length * (length + 1) / 2;
            
            // 输出不对称美珠宝数量
            System.out.println(totalCnt - symCnt);
        }
    }
}

02. 小毛的音乐节拍创作系统

问题描述

小毛是一位知名的电子音乐制作人，他正在开发一套智能节拍创作系统。该系统可以根据用户指定的节拍长度自动生成各种节拍组合方案。

在小毛的创作理念中，一段音乐可以由若干个基础节拍单元组成，每个基础节拍单元的长度只能是 、 或 拍中的一种。但是，小毛发现某些节拍组合会产生不和谐的效果：特别是当长度为 拍的节拍单元后面直接跟随长度为 拍的节拍单元时，会产生突兀的音乐转换，影响整体的流畅性。

现在小毛需要为音乐创作软件预先计算所有可能的和谐节拍组合方案数。对于每种可能的音乐总长度 ，计算有多少种不同的节拍单元排列方式，使得整段音乐听起来和谐流畅。

由于方案数可能非常大，请将结果对 取模后输出。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：

在一行上输入四个整数 ，代表最大音乐长度、可选的三种基础节拍单元长度 、、。保证 、、 两两互不相等。

除此之外，保证单个测试文件的 之和不超过 。

输出格式

对于每组测试数据，新起一行，输出 个整数，其中第 个数表示长度为 的音乐的和谐节拍组合方案数对 取模的结果。

样例输入

2
5 1 2 3
4 1 2 3

样例输出

1 2 4 6 11
1 2 4 6

样例	解释说明
第一组样例	当时，长度为1到5的音乐分别有1,2,4,6,11种和谐组合方案
第二组样例	当时，长度为1到4的音乐分别有1,2,4,6种和谐组合方案

数据范围

• 

• 

• 、、 两两互不相等

• 单个测试文件的 之和不超过

题解

这道题是一个带约束的动态规划问题，关键是要正确处理"长度为a的节拍单元后不能直接跟随长度为c的节拍单元"这个约束。

问题分析： 需要计算每种长度的音乐有多少种和谐的节拍组合方案。这是一个经典的计数动态规划问题，但加入了特殊的约束条件。

核心思路： 用状态转移的方法，分别记录以不同长度节拍单元结尾的方案数。设：

• dp0[i] 表示长度为i且以长度a结尾的方案数
• dp1[i] 表示长度为i且以长度b结尾的方案数
• dp2[i] 表示长度为i且以长度c结尾的方案数
• ans[i] 表示长度为i的总方案数

状态转移：

1. dp0[i] = ans[i-a]（前面可以是任意合法结尾）
2. dp1[i] = ans[i-b]（前面可以是任意合法结尾）
3. dp2[i] = ans[i-c] - dp0[i-c]（前面可以是任意合法结尾，但要排除以a结尾的情况）
4. ans[i] = dp0[i] + dp1[i] + dp2[i]

初始状态：ans[0] = 1（长度为0的空音乐有1种方案）

实现要点：

• 注意边界条件检查（i >= a/b/c）
• 取模运算要处理负数情况
• 按顺序计算，确保依赖的状态已经计算完成

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

参考代码

• Python

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

MOD = 10**9 + 7

T = int(input())
for _ in range(T):
    n, a, b, c = map(int, input().split())
    
    # 初始化DP数组
    dp_a = [0] * (n + 1)  # 以长度a结尾的方案数
    dp_b = [0] * (n + 1)  # 以长度b结尾的方案数
    dp_c = [0] * (n + 1)  # 以长度c结尾的方案数
    total = [0] * (n + 1)  # 总方案数
    
    total[0] = 1  # 初始状态
    
    result = []
    for i in range(1, n + 1):
        # 计算以各种长度结尾的方案数
        if i >= a:
            dp_a[i] = total[i - a]
        
        if i >= b:
            dp_b[i] = total[i - b]
        
        if i >= c:
            # 以c结尾，但前面不能是a
            dp_c[i] = (total[i - c] - dp_a[i - c] + MOD) % MOD
        
        # 计算总方案数
        total[i] = (dp_a[i] + dp_b[i] + dp_c[i]) % MOD
        result.append(total[i])
    
    print(' '.join(map(str, result)))

• Cpp

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

const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n, a, b, c;
        cin >> n >> a >> b >> c;
        
        // 初始化DP数组
        vector<long long> dp_a(n + 1, 0);  // 以长度a结尾的方案数
        vector<long long> dp_b(n + 1, 0);  // 以长度b结尾的方案数
        vector<long long> dp_c(n + 1, 0);  // 以长度c结尾的方案数
        vector<long long> total(n + 1, 0);  // 总方案数
        
        total[0] = 1;  // 初始状态
        
        for (int i = 1; i <= n; i++) {
            // 计算以各种长度结尾的方案数
            if (i >= a) {
                dp_a[i] = total[i - a];
            }
            
            if (i >= b) {
                dp_b[i] = total[i - b];
            }
            
            if (i >= c) {