✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：分发糖果

1️⃣：从左到右遍历，处理右边评分比左边高的情况

2️⃣：从右到左遍历，处理左边评分比右边高的情况

3️⃣：取两次遍历结果的最大值作为最终答案

难度：中等

这道题的关键在于理解双向约束问题，通过两次贪心遍历分别处理不同方向的约束条件。每个人的糖果数需要同时满足与左右邻居的相对关系，使用两个数组分别记录左扫描和右扫描的结果，最后取最大值确保所有约束都得到满足。

题目二：课程价值最大化

1️⃣：按结束时间对所有课程进行排序

2️⃣：使用动态规划，dp[i] 表示前 i 门课程的最大价值

3️⃣：结合二分查找快速定位不冲突的课程位置

难度：中等

这道题目是经典的活动选择问题的变形，需要在保证时间不冲突的前提下最大化价值。通过按结束时间排序，可以将问题转化为标准的动态规划模型。二分查找的引入将时间复杂度从 O(n²) 优化到 O(n log n)，体现了算法优化的重要性。

题目三：奶牛编号递推

1️⃣：识别线性递推关系 f(n) = 2×f(n-1) + 3×f(n-2) + f(n-3)

2️⃣：构造转移矩阵将递推关系表示为矩阵乘法

3️⃣：使用矩阵快速幂在 O(log n) 时间内求解

难度：中等偏难

这道题目结合了数学递推和高效算法设计。由于 n 可达 10^18，必须使用矩阵快速幂来避免超时。关键在于将递推关系转化为矩阵形式，然后利用快速幂的思想进行优化。这类问题在竞赛中常见，考查选手对数学建模和算法优化的综合能力。

01. 分发糖果

问题描述

为排成一列的人分配糖果，规则如下：

1. 每个人至少分配到 颗糖果。
2. 任意两个相邻的人中，评分更高的人必须获得更多的糖果。

输入格式

第一行包含一个字符串，表示一个整数数组，其中数组元素用逗号分隔，数组用方括号包围。

输出格式

输出一个整数，表示满足条件所需的最少糖果总数。

样例输入

[1,0,2]

[1,2,2]

样例输出

5

4

数据范围

题解

这道题的核心思想是使用贪心算法，通过两次遍历来确保每个人都得到合适的糖果数量。

首先分析问题的本质：每个人的糖果数不仅要满足"至少1颗"的约束，还要满足"评分更高的人比相邻评分低的人多"的约束。由于每个人都有两个邻居（除了边界），需要同时考虑左右两边的约束。

解法分为三个步骤：

1. 从左到右遍历：如果当前人的评分比左边邻居高，那么他的糖果数应该是左边邻居的糖果数加1。这样可以保证所有"右边比左边高"的约束得到满足。

2. 从右到左遍历：如果当前人的评分比右边邻居高，那么他的糖果数应该是右边邻居的糖果数加1。这样可以保证所有"左边比右边高"的约束得到满足。

3. 取最大值：对于每个位置，取两次遍历结果的最大值，这样就能同时满足两个方向的约束。

举个例子，对于 [1,0,2]：

• 初始都是1: [1,1,1]
• 从左到右: [1,1,2]（因为ratings[2] > ratings[1]）
• 从右到左: [2,1,2]（因为ratings[0] > ratings[1]）
• 最终结果: [max(1,2), max(1,1), max(2,2)] = [2,1,2]

时间复杂度是 ，空间复杂度是 ，对于给定的数据范围完全可以接受。

参考代码

• Python

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

def solve():
    line = input()
    # 解析输入的数组格式 [1,0,2]
    nums = []
    num = ""
    for c in line:
        if c.isdigit() or c == '-':
            num += c
        elif num:
            nums.append(int(num))
            num = ""
    if num:
        nums.append(int(num))
    
    n = len(nums)
    if n == 0:
        print(0)
        return
    
    # 从左到右扫描，处理左邻居约束
    left = [1] * n
    for i in range(1, n):
        if nums[i] > nums[i-1]:
            left[i] = left[i-1] + 1
    
    # 从右到左扫描，处理右邻居约束
    right = [1] * n
    for i in range(n-2, -1, -1):
        if nums[i] > nums[i+1]:
            right[i] = right[i+1] + 1
    
    # 取两个方向的最大值
    total = sum(max(left[i], right[i]) for i in range(n))
    print(total)

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string line;
    getline(cin, line);
    
    // 解析输入数组
    vector<int> nums;
    string temp = "";
    for (char c : line) {
        if (isdigit(c) || c == '-') {
            temp += c;
        } else if (!temp.empty()) {
            nums.push_back(stoi(temp));
            temp = "";
        }
    }
    if (!temp.empty()) {
        nums.push_back(stoi(temp));
    }
    
    int n = nums.size();
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    
    // 左扫描：处理左邻居的约束
    vector<int> lft(n, 1);
    for (int i = 1; i < n; i++) {
        if (nums[i] > nums[i-1]) {
            lft[i] = lft[i-1] + 1;
        }
    }
    
    // 右扫描：处理右邻居的约束
    vector<int> rgt(n, 1);
    for (int i = n-2; i >= 0; i--) {
        if (nums[i] > nums[i+1]) {
            rgt[i] = rgt[i+1] + 1;
        }
    }
    
    // 计算最终答案
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += max(lft[i], rgt[i]);
    }
    
    cout << ans << endl;
    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));
        String line = br.readLine();
        
        // 解析输入数组
        List<Integer> nums = new ArrayList<>();
        StringBuilder temp = new StringBuilder();
        for (char c : line.toCharArray()) {
            if (Character.isDigit(c) || c == '-') {
                temp.append(c);
            } else if (temp.length() > 0) {
                nums.add(Integer.parseInt(temp.toString()));
                temp = new StringBuilder();
            }
        }
        if (temp.length() > 0) {
            nums.add(Integer.parseInt(temp.toString()));
        }
        
        int n = nums.size();
        if (n == 0) {
            System.out.println(0);
            return;
        }
        
        // 左扫描：确保右边比左边高时糖果更多
        int[] leftCnt = new int[n];
        Arrays.fill(leftCnt, 1);
        for (int i = 1; i < n; i++) {
            if (nums.get(i) > nums.get(i-1)) {
                leftCnt[i] = leftCnt[i-1] + 1;
            }
        }
        
        // 右扫描：确保左边比右边高时糖果更多
        int[] rightCnt = new int[n];
        Arrays.fill(rightCnt, 1);
        for (int i = n-2; i >= 0; i--) {
            if (nums.get(i) > nums.get(i+1)) {
                rightCnt[i] = rightCnt[i+1] + 1;
            }
        }
        
        // 计算总和
        long totalCnt = 0;
        for (int i = 0; i < n; i++) {
            totalCnt += Math.max(leftCnt[i], rightCnt[i]);
        }
        
        System.out.println(totalCnt);
    }
}

02. 课程价值最大化

问题描述

小文需要从多门课程中选择一部分进行学习，每门课程都有一个开始时间、一个结束时间和对应的价值。选择的课程时间不能有任何冲突，目标是使得所选课程的总价值最大。

输入格式

第一行输入一个整数 ，代表课程的数量。

接下来的 行，每行包含三个整数 , , ，分别代表一门课程的开始时间、结束时间和价值。

输出格式

输出一个整数，表示可以获得的最大总价值。

样例输入

3
1 10 10
3 4 11
4 5 3

4
1 3 5
2 5 6  
4 6 5
5 7 4

样例输出

14

10

数据范围

题解

这是一道经典的活动选择问题，需要在保证时间不冲突的前提下使价值最大化。

关键思路是使用动态规划结合二分查找。基本想法是：

1. 按照结束时间对所有课程进行升序排序
2. 使用动态规划，dp[i] 表示考虑前 i 门课程能获得的最大价值
3. 对于第 i 门课程，有两种选择：选择它或不选择它

状态转移方程为： dp[i] = max(dp[i-1], dp[j] + value[i])

其中 j 是满足 end[j] <= start[i] 的最大下标，也就是在第 i 门课程开始之前结束的最后一门课程。

为什么要按结束时间排序？因为这样可以保证对于任意位置 i，前面的所有课程都比当前课程更早结束，便于找到不冲突的课程。

使用二分查找可以快速找到合适的 j 值，将时间复杂度从 优化到 。

举个例子，对于样例1：

• 排序后：[(3,4,11), (4,5,3), (1,10,10)]
• dp[0] = 0
• dp[1] = max(0, 0+11) = 11
• dp[2] = max(11, 11+3) = 14 （因为课程2在课程1结束后开始）
• dp[3] = max(14, 0+10) = 14 （课程3与前面的课程冲突）

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

参考代码

• Python

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

def solve():
    n = int(input())
    courses = []
    
    # 读入课程信息
    for _ in range(n):
        s, e, v = map(int, input().split())
        courses.append((e, s, v))  # 按结束时间排序
    
    # 按结束时间排序