✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

蚂蚁-2026.04.09-算法岗

三道题方向各异：第一题考查单调性判断，第二题建模为 HMM，用 Viterbi 求最优路径，第三题需要分解最小公倍数中的质因子结构。题面表述清晰，难点在于每题所用模型差异较大，切题方向需要分开判断。

1. 柯南的机关积分

问题描述

柯南在追查黑衣组织时，进入了一条由 道机关构成的密道。他的初始积分为 ，每道机关处有两扇可选的门，每扇门对应一种对当前积分的运算：

• + x：积分加
• - x：积分减
• * x：积分乘
• / x：积分整除 ，结果向下取整

每经过一扇门后，立即将积分截断至区间 ：

• 结果小于 时，积分取
• 结果大于 时，积分取

柯南在每道机关处必须二选一。请计算通过全部 道机关后，积分的最大可能值。

输入格式

第一行输入一个整数 ，表示机关数量。

接下来 行，每行给出两组操作，格式为：

op1 x1 op2 x2

其中 op1、op2 是四种运算符之一， 均为正整数。

输出格式

输出一个整数，表示通过全部 道机关后可以达到的最大积分。

样例输入1

3
+ 10 * 2
* 2 / 5
- 5 / 2

样例输入2

3
- 10 * 1
* 2 / 100
/ 2 + 1000

样例输出1

17

样例输出2

1002

数据范围

• 
• 
• 每一步运算后都要把积分截断到

样例解释1

从初始值 出发，第一关选 + 10 得到 ，第二关选 * 2 得到 ，第三关选 - 5 得到 。

样例解释2

第一关选 - 10 截断为 ，选 * 1 同样得到 ；第二关选 * 2 得到 ；第三关选 + 1000 得到 。

题解

四种运算配合截断操作后，每一步转移都构成关于当前积分的单调不减函数。这一性质使贪心策略成立：每道机关处直接选取两扇门中结果较大的那扇，最终输出即为全局最优。

单调性分析

设当前积分为 ，对任意正整数 ：

• 关于 严格递增
• 关于 严格递增
• （）关于 单调不减
• 关于 单调不减

截断操作 同样保持单调不减。因此，每扇门的完整转移（运算后截断）都是 的单调不减函数。

贪心的正确性

设 为第 关结束后积分为 时，后续所有关卡能取得的最优值。每一步转移均单调不减， 作为若干此类函数的复合，仍然单调不减。

因此，若当前关两个候选结果为 和 且 ，则 。选取较大的候选值，后续的最优表现不会更差。这保证了每关局部最大就是全局最优路径的一部分。

算法流程

初始化 ，顺序处理每道机关：

1. 分别计算两扇门作用后的结果
2. 对两个结果各自截断至
3. 取较大值更新

输出最终的 。

复杂度分析

• 时间复杂度：
• 空间复杂度：

参考代码（Python）

import sys

def readline():
    return sys.stdin.readline().strip()

LIMIT = 10**9

def bound(value):
    if value < 1:
        return 1
    if value > LIMIT:
        return LIMIT
    return value

def perform(value, operator, operand):
    if operator == "+":
        return bound(value + operand)
    if operator == "-":
        return bound(value - operand)
    if operator == "*":
        return bound(value * operand)
    return bound(value // operand)

def main():
    steps = int(readline())
    score = 1
    for _ in range(steps):
        first_op, first_num, second_op, second_num = readline().split()
        first_num = int(first_num)
        second_num = int(second_num)
        result_a = perform(score, first_op, first_num)
        result_b = perform(score, second_op, second_num)
        score = result_a if result_a >= result_b else result_b
    print(score)

if __name__ == "__main__":
    main()

2. 工藤新一的推理路径

问题描述

工藤新一在分析一段密文时，发现它可以用离散型隐马尔可夫模型（HMM）建模。给定模型参数与若干条观测序列，需要对每条序列分别求出：

• 最可能的隐藏状态序列（最优路径）。
• 该路径对应的对数概率。

模型参数包括：

• 初始状态分布 pi。
• 状态转移矩阵 A。
• 观测概率矩阵 B。
• 多条离散观测序列 obs。

若使用 Python，除标准库外只允许依赖 numpy。所有计算须在对数域中进行，以规避概率连乘导致的数值下溢。

输入格式

输入只有一行，是一个标准 JSON 对象，不含注释，格式如下：

{"pi":[0.6,0.4],"A":[[0.7,0.3],[0.4,0.6]],"B":[[0.5,0.4,0.1],[0.1,0.3,0.6]],"obs":[[0,0],[2,1,0]]}

字段含义如下：

• pi：长度为 N 的初始状态概率数组。
• A：N×N 的状态转移矩阵，A[i][j] 表示从状态 i 转移到状态 j 的概率。
• B：N×M 的观测概率矩阵，B[i][k] 表示状态 i 生成符号 k 的概率。
• obs：共 S 条观测序列，每个符号均为区间 [0, M-1] 内的整数。

输入中的概率已合法归一化，无需额外校验。

输出格式

输出一行压缩后的 JSON，键名顺序固定为 paths 在前、logp 在后：

{"paths":[[0,0],[1,1,0]],"logp":[-2.253795,-4.017384]}

要求：

• paths[i] 对应 obs[i] 的最优隐藏状态序列。
• logp[i] 对应该最优路径的对数概率。
• logp 中每个数固定保留 6 位小数。
• 整行 JSON 不插入额外空格。

样例输入

{"pi":[0.6,0.4],"A":[[0.7,0.3],[0.4,0.6]],"B":[[0.5,0.4,0.1],[0.1,0.3,0.6]],"obs":[[0,0]]}

样例输出

{"paths":[[0,0]],"logp":[-2.253795]}

数据范围

• 1 ≤ N ≤ 4
• 1 ≤ M ≤ 4
• 1 ≤ S ≤ 10
• 单条观测序列长度 1 ≤ L ≤ 6
• 所有浮点计算按 float64 处理

样例解释

• 样例 1：观测序列为 [0, 0]，共两个符号。最优路径为 0 → 0，对应概率 ，取对数后约为 -2.253795。

题解

本题对每条观测序列独立运行 Viterbi 算法，求解最大概率路径并回溯还原。

状态定义

设 为处理到第 个观测符号、当前隐藏状态为 时所能达到的最大对数概率。

同时维护前驱数组 ，记录第 步到达状态 的最优前驱状态。最终沿 从后向前回溯，可还原完整路径。

对数域的作用

概率连乘会随序列增长而迅速趋零，直接用浮点乘法容易产生下溢。将所有概率取对数后，乘法转化为加法：

转移过程变为对若干对数值求和后取最大，数值稳定性得以保证。本题只需最优路径，无需计算全局归一化概率，因此使用 max 转移即可，不涉及 log-sum-exp。

转移公式

初始化：

递推（）：

每步枚举终点状态 ，遍历所有前驱状态 ，取使括号内值最大的 作为最优前驱，存入 。

回溯过程

在末层 中取最大值对应的状态作为路径终点，随后依据 逐步向前回跳，将各步状态收集后翻转，得到最终路径。最优路径的对数概率即为 。

复杂度分析

设隐状态数为 ，单条序列长度为 ，序列条数为 ：

• 时间复杂度：
• 空间复杂度：

在本题约束（，）下，按定义直接实现即可满足性能要求。

参考代码（Python）

import sys
import json
import math

def to_log_vector(values):
    return [math.log(x) if x > 0 else float("-inf") for x in values]

def to_log_matrix(