小红的星尘收集 题目分析 小红在太空中发现一排星尘簇，每个星尘簇有一个能量值。收集第  个位置的星尘时，相邻的第  和第  个星尘会消散，无法再被收集。求能获得的最大能量总和。 这是经典的打家劫舍问题：从一排数中选取若干个，要求任意两个被选中的数不相邻，使得总和最大。 思路 动态规划 定义  为考虑前  个星尘时能获得的最大能量。对于第  个星尘，有两种决策：  不收集：最大能量等于 。 收集：获得  的能量，但第  个不能选，所以最大能量等于 。  取两者较大值： $$ 初始条件：，（虚拟边界）。 由于  只依赖前两个状态，可以用两个变量滚动优化，空间复杂度降为 。 示例推演 输入 2 7 ...

模型量化最小误差 题目分析 神经网络有  层，每层有  个实数权重。每层需要选择一个量化位宽 ，所有层的位宽之和不能超过 。 对于位宽 ，每个权重  的量化过程为：  放大并取整： 还原：  每层的量化误差为该层所有权重的  之和，总误差为所有层误差之和。求最小总误差乘以  后向下取整的结果。 思路 分组背包 DP 这是一个经典的分组背包问题。每一层是一个"组"，每组有  种选择（位宽 、、），对应的"体积"就是位宽值，"价值"就是该层在对应位宽下的量化误差。背包容量为 ，目标是在总位宽不超过预算的前提下，最小化总误差。 预处理： 对...

三项评分线性定价 题意 已知  部手机，每部手机有三项评分  和对应的价格 。价格与评分之间满足线性关系： $$ 根据这  组已知数据拟合出四个系数 ，然后对  部新手机预测价格，四舍五入到整数后输出。 思路 这是一道经典的多元线性回归问题，使用最小二乘法求解。 构造设计矩阵 （每行为 ）和价格向量 ，参数向量  由正规方程给出： $$ 实际实现中直接调用 numpy.linalg.lstsq 即可，它内部使用 SVD 分解求解，数值稳定性优于直接求逆。 拟合出  后，对每部待预测手机计算 ，四舍五入输出。 代码 import sys import numpy as np def main()...

整理科研数据文件 题目分析 给定  个文件名，要求按照"自然排序"规则排序输出。自然排序与普通字典序排序的区别在于：数字部分按数值大小比较而非逐字符比较，例如 Run2 应排在 Run10 前面。 排序规则：  将文件名拆分为交替的非数字段和数字段，如 ts010tc12 拆分为 ["ts", "010", "tc", "12"]。 逐段比较：两个非数字段按字典序比较；两个数字段按数值比较；类型不同时数字段排在前面。 前缀优先：一个文件名是另一个的前缀时，较短的排在前面。 稳定性：数值相等的项（...

小店的经营分析 题目分析 给定  天的经营数据（盈利为正，亏损为负），以及一个目标利润区间 ，求有多少个连续经营周期（子数组）的总利润恰好落在目标区间内。 即统计满足  的  对数。 思路 归并排序 + 前缀和 子数组和可以用前缀和表示：。问题转化为：在前缀和数组  中，统计满足 （且 ）的有序对  的个数。 暴力枚举所有对是  的，对于  会超时。我们利用归并排序在合并过程中高效统计。 关键观察：在归并排序的合并阶段，左半部分和右半部分各自已排好序。对于左半部分的每个 ，我们要在右半部分找满足  的 ，即 。 由于右半部分已排序，可以用双指针  维护满足条件的区间 。随着  从左到右遍历（左...

细胞增殖 题目分析 细胞种群数量满足公式 ，其中  为增殖基数， 为稳定基数， 为增殖周期（正整数，）。 给定  条升序排列的观测记录和  组假说 ，对每组假说需要回答：  有多少条记录能被该假说解释（即存在正整数  使 ） 所有合法周期值中，单个  对应的最多记录数（增殖峰值）  思路 枚举幂次 + 二分查找 关键观察：对于 ， 增长极快， 最多只有约  个取值。例如  时  不超过 。因此可以枚举所有可能的 ，计算 ，然后在有序的观测数组中二分查找该值出现的次数。 对  和  需要特殊处理：  ：（），所以 。所有值等于  的记录都匹配，且它们对应任意 ，因此总数和峰值均为该值的出现次数。...

物流中心包裹分拣 题意 传送带上有  个包裹，每个包裹标有一个目的地编号。要求将这些包裹划分成最多数量的连续批次，使得每个批次独立排序后，按原先批次顺序拼接起来的结果与全局排序的结果一致。 思路 什么时候可以在位置  后面切一刀？当且仅当前  个元素的多重集合恰好等于全局排序后前  个元素的多重集合。换句话说，前  个位置已经"集齐"了它们排序后应该拥有的所有元素，不多也不少。 怎么高效判断两个多重集合相等？维护一个频次差值表 diff：从左到右扫描，每到位置 ，把原数组 a[i] 的计数 ，把排序数组 s[i] 的计数 。同时用一个变量 nonzero 记录 diff 中...

健身达人每日步数 题目分析 给定  天的步数记录，如果某天的步数严格大于其后某一天步数的两倍，则该天称为"突破日"。求突破日的总数。 换句话说，第  天是突破日当且仅当存在  使得 ，等价于 。 思路 后缀最小值 对于每一天，我们需要判断它的步数是否严格大于后面所有天中最小步数的两倍。暴力做法对每个位置都扫描后面所有元素求最小值，时间复杂度 。 优化方法很直观：从右往左遍历，维护一个后缀最小值 suffix_min。对于当前位置 （），如果 ，则第  天是突破日。判断完成后，将  纳入后缀最小值的更新。 注意最后一天没有后续天，不可能是突破日。另外需要特判  的边界情况。 ...

奶茶店特调 题目分析 有  层奶茶原料从底到顶排列，每层有一个风味编号和一个身份编号（初始位置  到 ）。执行  次"升级"操作，每次指定某个身份编号的层进行升级：  若该层正下方有一层风味编号相同，则两层融合为一层，新层风味编号 。 新层继承升级状态，继续尝试与下方融合，直到下方不存在或风味不同。 融合产生的新层没有身份编号，不能被直接指定升级，但可以被动参与后续融合。  如果某个身份编号的层已经在之前的融合中被消耗，则跳过该次操作。求所有操作结束后剩余层数。 思路 链表模拟 核心观察：每次升级操作是一个向下的链式融合过程——找到目标层，不断检查正下方的层是否风味相同，相...

均衡版 KMeans 分群与新用户归类 题目分析 给定  位客户的  维特征向量，使用均衡版 KMeans 将其划分为  个群组，每组容量严格均衡（ 或 ），迭代至收敛后，对新客户进行归类。 思路 模拟均衡 KMeans 聚类 与标准 KMeans 不同，本题要求每个簇的容量严格均衡，因此分配阶段需要加入容量限制。 初始化：取前  个客户的特征作为初始质心。容量分配为：前  个质心容量为 ，其余为 。 分配阶段：按客户编号  到  顺序处理。对每个客户，计算到所有未满员质心的平方欧氏距离，选距离最小的质心（并列选编号小的）。 更新阶段：每个质心更新为该簇内所有成员特征的逐维均值向下取整。 收敛...

结构化剪枝后的分类预测 题目分析 给定样本矩阵 （）、线性分类器权重矩阵 （）和剪枝比例 ，模拟"行剪枝"过程：按 L1 范数从小到大移除  中最不重要的  行及  中对应的列，然后用剪枝后的矩阵做线性变换 + Softmax 预测每个样本的类别。 思路 矩阵剪枝 + 线性分类模拟 按题意逐步实现即可，关键是把每一步的细节处理正确：  计算剪枝行数 ：。特判：当  且  时，强制 （至少剪一行）。   计算每行 L1 范数：对  的第  行，。按 L1 从小到大排序，移除最小的  行。   特征对齐： 移除的行索引对应  要移除的列索引。保留剩余特征，得到 （）和 （）。 ...

无核翻转的卷积计算 题目分析 给定一个  的核矩阵（ 为奇数）和一张  的灰度图，要求进行无核翻转的相关运算（cross-correlation）。在图像四周用 0 进行充分填充（same padding），使得输出尺寸与原图一致，然后对每个像素位置 ，将核与其邻域逐元素相乘后求和，得到输出像素值。 与卷积不同，相关运算不翻转核——核的左上角元素直接对齐到邻域的左上角。 思路 零填充 + 暴力枚举 这是一道图像处理中的基础相关运算模拟题。关键在于正确理解 same padding 和无翻转这两个要求。 算法步骤：  零填充：在原图四周各填充 （整除）圈零，构造一个  的填充矩阵。原图的  位置...

ViT中的Patch Embedding 题目分析 给定图像尺寸 img_size、块大小 patch_size、通道数 channels 和嵌入维度 embedding_dim，计算 Vision Transformer 中 Patch Embedding 层输出的形状。 思路 数学推导 ViT 将输入图像划分为等大的正方形 patch，每个 patch 通过线性映射得到一个嵌入向量。在所有 patch token 前面还会拼接一个分类 token（CLS token）。 具体计算步骤：  每条边上的 patch 数量为 。 总 patch 数量为 。 加上 1 个 CLS token，最终...

Prompt上下文信息精简 题目分析 给定一棵用层序数组表示的二叉树，每个节点有整数权值（可正、可负、可零）。可以"剪枝"任意子树（将其置为 null），目标是使剩余节点的权值之和最大。输出剪枝后的层序数组（去掉末尾的 null）。 思路 树形DP + 贪心剪枝 核心思想：对每个节点，自底向上计算其子树在最优剪枝下能获得的最大权值和。 定义  为以节点  为根、经过最优剪枝后的子树权值和： $$ 即：如果某个子树的最优和为负，直接剪掉（贡献 0）；否则保留。 选择最优根：遍历所有节点，找  最大的节点作为输出子树的根。这样处理了根节点本身为负、但某棵子树更优的情况。 构建输...