08-01 19:16 宁波大学产品经理发布于浙江

关注

文远知行（07.27场）笔试复盘：三道编程题思路详解与踩坑点分析

Hello，各位牛友！

文远知行近期的笔试，趁热打铁，把三道编程题的思路和AC代码整理了一下分享给大家。整体感觉题目难度中等，都是大家比较熟悉的经典模型，但想做到完全Bug-Free还是需要注意一些细节。希望这篇复盘能帮到后续参加的同学，祝大家都能顺利上岸！

第一题：分发糖果

题目大意

有一排人，每个人都有一个评分值。你需要按照以下规则给他们分发糖果：

每个人至少得到 1 颗糖果
评分更高的邻居，得到的糖果也必须更多
目标是计算出满足这些规则所需的最少糖果总数

考点分析

贪心算法。这道题的难点在于，每个人的糖果数同时受到左、右两个邻居的制约。只考虑单边约束很容易，但要同时满足两边，就需要巧妙的解法。正确的思路是通过两次贪心遍历来解耦这个双向约束。

样例输入与输出

样例 1:

[1,0,2]

输出: 5 (最优分配为 )

样例 2:

[1,2,2]

输出: 4 (最优分配为 )

解题思路

这道题是LeetCode上的原题，非常经典。核心思想是"两边夹击"。

第一次遍历（从左到右）：

初始化一个 candies 数组，所有人糖果都为1
从左到右遍历评分数组。如果当前学生 i 的评分比他左边的学生 i-1 高 (ratings[i] > ratings[i-1])，那么他的糖果数应该至少是左边学生糖果数加一，即 candies[i] = candies[i-1] + 1
这次遍历结束后，我们保证了所有"右边比左边评分高"的情况都得到了满足

第二次遍历（从右到左）：

现在从右到左遍历。如果当前学生 i 的评分比他右边的学生 i+1 高 (ratings[i] > ratings[i+1])，他的糖果数需要更新
关键点：此时他的糖果数应该是 max(candies[i], candies[i+1] + 1)。为什么要取 max？因为第一次遍历的结果已经满足了左边的约束，我们不能破坏它
例如，对于评分 ，左到右遍历后糖果是 ；右到左遍历时，candies 会更新为 candies+1=2，candies 会更新为 candies+1=3，结果是 ``
但对于评分 ，左到右遍历后是 ，右到左遍历时，虽然评分不满足 >，但我们不能把 `` 降下来。因此，取最大值可以同时兼顾两个方向的约束

汇总：将最终的 candies 数组求和，就是最少的糖果总数。

AC代码 (Python)

import json

def solve():
    """
    处理分发糖果问题
    """
    try:
        # 使用 json 库来安全、高效地解析输入字符串
        line = input()
        ratings = json.loads(line)
    except (json.JSONDecodeError, IndexError):
        print(0)
        return

    n = len(ratings)
    if n == 0:
        print(0)
        return

    # 1. 从左到右遍历，满足右边比左边评分高的约束
    left_to_right_candies = [1] * n
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            left_to_right_candies[i] = left_to_right_candies[i - 1] + 1

    # 2. 从右到左遍历，满足左边比右边评分高的约束
    # 直接在第一次结果上优化，并累加总数以节省空间
    total_candies = 0
    right_val = 1 # 模拟一个从右往左的糖果计数器
    for i in range(n - 1, -1, -1):
        # 如果当前学生评分比右边高，则右侧规则生效
        if i < n - 1 and ratings[i] > ratings[i + 1]:
            right_val += 1
        else:
            # 否则，重置为1
            right_val = 1
        
        # 核心：当前学生的糖果数是两种规则下的最大值
        final_candy = max(left_to_right_candies[i], right_val)
        total_candies += final_candy
        
    print(total_candies)

if __name__ == "__main__":
    solve()

第二题：课程价值最大化

题目大意

给定一组课程，每门课程都有开始时间、结束时间和价值。你需要从中选择一部分课程，要求所选课程之间时间上不能有重叠（一门课程的结束时间等于另一门的开始时间不算重叠），目标是让所选课程的总价值最大。

考点分析

动态规划 (DP) + 贪心 + 二分查找。这是一个经典的加权区间调度问题。

贪心：按结束时间对课程进行排序是解决此类问题的标准预处理步骤
动态规划：dp[i] 通常定义为"考虑前 i 门课程所能获得的最大价值"
二分查找：用于优化状态转移过程，将复杂度从 O(n²) 降低到 O(nlogn)

样例输入与输出

样例 1:

输出: 14

样例 2:

输出: 10

解题思路

排序：将所有课程按照结束时间升序排列。为什么要按结束时间？因为当我们考虑第 i 门课时，这个排序策略能保证所有可能与它搭配的、不冲突的课程都位于它的前面，方便我们做决策。
定义DP状态：我们定义 dp[i] 为"处理完排序后的前 i 门课程（从1到i），可以获得的最大价值"。
状态转移：对于第 i 门课程（设其开始时间为 start_i，结束时间为 end_i，价值为 value_i），我们有两种选择：
- 不选择第 i 门课：那么最大价值就和处理前 i-1 门课时一样，即 dp[i-1]
- 选择第 i 门课：那么我们就不能选择任何在 start_i 之后结束的课程。我们需要找到一个最大的索引 p，使得第 p 门课的结束时间 end_p <= start_i。那么选择第 i 门课的总价值就是 dp[p] + value_i

所以，状态转移方程为：

dp[i] = max(dp[i-1], dp[p] + value_i)

优化查找：暴力查找 p 会使时间复杂度达到 O(n²)。由于课程是按结束时间有序的，我们可以使用二分查找在 O(logn) 的时间内快速找到这个 p。

AC代码 (Python)

import sys
import bisect

def solve():
    """
    处理课程价值最大化问题
    """
    try:
        n = int(sys.stdin.readline())
        courses = []
        for _ in range(n):
            # 存储为 (结束时间, 开始时间, 价值) 以便排序
            s, e, v = map(int, sys.stdin.readline().split())
            courses.append((e, s, v))
    except (ValueError, IndexError):
        return

    # 1. 按课程结束时间升序排序
    courses.sort()

    # dp[i] 表示考虑前 i 门课程能获得的最大价值
    # dp 数组长度为 n+1，dp[0] = 0 作为哨兵
    dp = [0] * (n + 1)
    
    # 提取所有结束时间，用于二分查找
    end_times = [c[0] for c in courses]

    for i in range(1, n + 1):
        end_time, start_time, value = courses[i-1]
        
        # 决策1: 不选择当前第 i 门课程
        # 此时最大价值与考虑前 i-1 门课时相同
        option1_value = dp[i-1]
        
        # 决策2: 选择当前第 i 门课程
        # 使用二分查找 (bisect_right) 找到在当前课程开始前就已结束的课程的临界点
        # bisect_right 会找到 start_time 在 end_times 中的插入点
        # 这个索引 p 正好是前 p 门课程，它们的结束时间都 <= start_time
        p = bisect.bisect_right(end_times, start_time, hi=i-1)
        
        # dp[p] 就是这 p 门课程可以获得的最大价值
        # dp数组索引比课程索引大1，所以dp[p]对应的是前p门课的结果
        option2_value = (dp[p] if p > 0 else 0) + value
        
        # 状态转移：取两种决策中的最大值
        dp[i] = max(option1_value, option2_value)

    print(dp[n])

if __name__ == "__main__":
    solve()

第三题：奶牛编号递推

题目大意

奶牛的编号 f(n) 由一个线性递推关系式决定：

f(n) = 2×f(n−1) + 3×f(n−2) + f(n−3)

初始条件为 f(1)=1, f(2)=2, f(3)=31。

需要计算 f(n) 对 123456789 取模的结果，其中 n 非常大（可达 10¹⁸）。

考点分析

线性代数 + 矩阵快速幂。

这是一个非常明显的信号：

固定的线性递推关系
超大的 n

当遇到这种情况时，几乎可以肯定是考察矩阵快速幂。其思想是将递推过程转化为矩阵的幂运算，然后利用类似整数快速幂的分治思想，将计算 A^n 的时间复杂度从 O(n) 优化到 O(logn)。

样例输入与输出

样例:

输出:

解题思路

构造状态向量：递推关系涉及到前三项，所以我们可以构造一个 3×1 的状态向量：

V_n = [f(n), f(n−1), f(n−2)]ᵀ

构建转移矩阵：我们的目标是找到一个 3×3 的矩阵 A，使得 V_n = A × V_{n−1}。

根据递推公式 f(n) = 2f(n−1) + 3f(n−2) + 1f(n−3)，我们可以构建出矩阵 A 的第一行。

另外两个关系是平凡的：f(n−1) = 1f(n−1) + 0f(n−2) + 0f(n−3) 和 f(n−2) = 0f(n−1) + 1f(n−2) + 0f(n−3)。

综合起来，转移矩阵 A 为：

A = [2  3  1]
    [1  0  0]
    [0  1  0]

建立递推关系：

[f(n)  ]     [2  3  1] [f(n−1)]
[f(n−1)] =   [1  0  0] [f(n−2)]
[f(n−2)]     [0  1  0] [f(n−3)]

由此可得：V_n = A × V_{n−1} = A² × V_{n−2} = ⋯ = A^{n−3} × V_3

其中 V_3 是我们的初始状态向量：V_3 = [f(3), f(2), f(1)]ᵀ = ᵀ 4. 矩阵快速幂：现在的任务就是高效计算 A^{n−3}。我们可以实现一个 mat_pow(matrix, power) 函数，使用二分法原理来计算矩阵的幂。所有计算过程中都要对 MOD 取模。 5. 计算最终结果：得到 A^{n−3} 后，记为 Result_Matrix。最终的 f(n) 就是 Result_Matrix 的第一行与初始向量 V_3 的点积：

f(n) = Result_Matrix[0][0]×f(3) + Result_Matrix[0][1]×f(2) + Result_Matrix[0][2]×f(1)

AC代码 (Python)

import sys

MOD = 123456789

def mat_mul(A, B):
    """
    计算两个 3x3 矩阵的乘积 (A * B)，结果对 MOD 取模。
    """
    C = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
    return C

def mat_pow(base_matrix, power):
    """
    计算矩阵的快速幂 (base_matrix ^ power)。
    """
    # 结果矩阵初始化为单位矩阵
    result_matrix = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    for i in range(3):
        result_matrix[i][i] = 1
    
    temp_matrix = base_matrix
    
    while power > 0:
        # 如果幂是奇数，将结果乘上当前的基底矩阵
        if power & 1:
            result_matrix = mat_mul(result_matrix, temp_matrix)
        # 基底矩阵自乘
        temp_matrix = mat_mul(temp_matrix, temp_matrix)
        # 幂次减半
        power >>= 1
        
    return result_matrix

def solve():
    """
    主解决函数
    """
    try:
        t = int(sys.stdin.readline())
        for _ in range(t):
            n = int(sys.stdin.readline())
            
            if n <= 2:
                print(n)
                continue
            if n == 3:
                print(31)
                continue

            # 转移矩阵 A
            transition_matrix = [
                [2, 3, 1],
                [1, 0, 0],
                [0, 1, 0]
            ]
            
            # 初始状态向量 V3 = [f(3), f(2), f(1)]
            initial_vector = [31, 2, 1]
            
            # 我们需要计算 A^(n-3)
            power = n - 3
            result_mat = mat_pow(transition_matrix, power)
            
            # f(n) = Result_Matrix[0] · V3
            ans = 0
            for i in range(3):
                ans = (ans + result_mat[0][i] * initial_vector[i]) % MOD
            
            print(ans)

    except (ValueError, IndexError):
        return

if __name__ == "__main__":
    solve()

#笔试##秋招##算法#