农田最大产出评估 题意 有  个连续地块，每个地块有一个肥力指数。选取任意一段连续的地块，这段地块的"产出系数"等于段内最小肥力指数乘以地块数量。求所有连续子段中最大的产出系数。 思路 先想想暴力怎么做：枚举所有区间 ，找区间最小值再乘以长度。这是  的， 到  会超时。 换个角度想——如果我们固定"谁是区间里的最小值"呢？ 假设第  个地块的肥力  是某个区间的最小值，那这个区间最远能往左延伸到哪里？往右延伸到哪里？答案就是：往左找到第一个比  小的位置 ，往右找到第一个比  小的位置 ，那以  为最小值的最宽区间就是 ，宽度为 ，产出系数就是 。 怎...

分布式计算任务调度 题意 有  个计算任务（编号 1 到 ），每个任务有一个计算量 。需要把这些任务分配给  个处理节点，满足：  分配给同一节点的任务 ID 必须连续 不同节点之间任务 ID 必须递增（即把任务数组切成连续的若干段） 单个任务不可拆分  目标：使负载最高节点与最低节点的差异最小，输出最优方案下负载最高节点的负载量。 思路 把  个任务按顺序切成  段连续子数组，要求最大段和尽量小——这不就是经典的"分割数组的最大值"吗？ 为什么最小化最大值就等价于最小化最大最小之差？直觉上想：总量固定，把最大的压下来，各段就更均匀，差值自然更小。严格来说，当最大值取到最小...

深海潜艇探险 题意 一艘潜艇初始能量为 ，要穿越  个危险区域。第  个区域穿越时消耗  能量，穿越后补充  能量。驾驶员可以自由选择穿越顺序，但全程能量必须严格大于 0。问是否存在一种顺序能安全通过所有区域。 思路 自由选择顺序——典型的贪心调度问题。关键是怎么排序才能让能量尽可能"安全"。 先想一个直觉： 如果某个区域"赚能量"（），那当然越早做越好，这样后面的能量越充裕。反过来，如果某个区域"亏能量"（），应该放到最后做，趁能量高的时候硬扛。 所以第一步很自然：把区域分成两组，一组是"收益区"（），一组是&q...

实现Masked Multi-Head Self-Attention 题意 给定输入张量 （形状 ）和四个权重矩阵 （均为 ），以及 head 数量 ，要求实现完整的 Masked Multi-Head Self-Attention 计算，输出最终结果（保留两位小数）。 思路 这道题没有算法上的难度，纯粹是按步骤实现 Transformer 里 Decoder 用的 Masked Multi-Head Self-Attention。关键是把每一步的矩阵运算和维度变换搞对。 整个流程分七步，我们一步步理清楚： 第一步：线性投影。 用输入  分别乘以  得到 ，形状不变，仍然是 。 第二步：拆成多...

K-Means聚类下的Anchor优化输出 题意 给定  个矩形框（宽和高），用基于 IOU 距离的 K-Means 聚类算法选出  个代表性 anchor 尺寸。初始中心取前  个框，迭代最多  次，最终按面积降序输出  个 anchor。 思路 IOU 距离是什么？ 在目标检测里，两个框有多"相似"通常用 IOU（交并比）来衡量。这里的框都以左上角对齐来计算： $$ 距离就是 。IOU 越大，距离越小，说明两个框越像。 K-Means 流程 K-Means 本身的套路你应该很熟了，只是这里距离函数换成了 IOU 距离：  初始化：拿前  个框作为初始聚类中心。 分配：对...

无线网络信号塔覆盖 题意 给一个  的城市网格，每个格子有一个整数值：  正数：居民区，数据需求为该值  负数：可以建信号塔的位置，信号半径为  零：空地  信号塔在 ，半径为 ，能覆盖  处的居民区，条件是欧几里得距离 。 服务价值规则：  没被任何塔覆盖的居民区，价值为 0 被  个塔同时覆盖的居民区，有效价值从  降为 （信号干扰）  目标：选择激活哪些塔，使总有效价值最大。在最大价值前提下，激活的塔数尽量少。 数据范围：，信号塔数量不超过 11。 思路 看到"信号塔数量不超过 11"，这个限制非常关键。，直接枚举所有信号塔的激活方案完全可行。 先想清楚整个流程： 预...

云服务资源调度 题意 有  个任务，每个任务有一个计算成本 。服务器的最大计算容量为 。为每台服务器分配任务时，采用贪心策略：总是优先选择当前未分配的、计算成本最高的、且不超出剩余容量的任务。问处理完所有任务最少需要多少台服务器。 思路 题目描述的其实是一个确定性的装箱模拟：每开一台新服务器，就从剩余任务中反复挑最大的能放进去的，直到再也放不进，然后开下一台。 具体流程：  把任务按成本从大到小排序。 遍历任务，遇到第一个还没被分配的任务，就开一台新服务器，把这个任务放进去。 接着从剩余任务中扫描，每次挑最大的且不超出剩余容量的任务放进去，直到没有能放的为止。 重复 2-3 直到所有任务都被分...

分布式系统任务调度 题意 给一棵二叉树（以层序遍历数组表示，-1 代表空节点），每个节点有唯一整数 ID。给定两个节点 ID  和 ，找到它们的最近公共祖先（LCA），然后输出该 LCA 管辖的节点总数（不包含 LCA 自身）。 题目说"层级越低优先级越高"，所以"最低共同主控节点"就是 LCA。如果  是  的祖先，那 LCA 就是 。 思路 层序遍历数组天然支持用下标关系表示父子：对于下标  的节点，左孩子是 ，右孩子是 ，父亲是 。 这题节点数只有 32，所以不需要什么花里胡哨的算法，直接暴力就行。分两步走： 第一步：找 LCA 怎么在数组表示的二...

ID3决策树训练 题意 给定  个训练样本，每个样本有  个二值特征和一个二值标签（0=正常，1=退化）。要求用 ID3 算法构建决策树，然后对  个查询样本进行预测。 思路 什么是 ID3 决策树？ ID3 的核心思想很简单：每次选一个"最有区分力"的特征把数据一分为二，递归建树，直到不需要再分为止。 那怎么衡量"区分力"？用信息增益。 信息增益怎么算？ 先回顾信息熵。对于一组标签，信息熵定义为： $$ 其中  是各类别的占比。熵越大，数据越"混乱"；熵为 0，说明所有样本同类。 选特征  把数据分成""和&qu...

K-Means算法 题意 给定  个二维坐标点（基站位置），要求用 K-Means 聚类算法将它们分成  组。然后用轮廓系数评估每个簇的质量，找出平均轮廓系数最低的那个簇，输出该簇质心坐标（保留两位小数，银行家舍入）。 关键规则：  初始中心取前  个点 轮廓系数 ，其中  是点  到本簇其他点的平均欧式距离， 是到最近其他簇所有点的平均距离 若簇只有 1 个点（或更少），  思路 这题没有复杂的算法设计，就是一道"照着说明书实现"的模拟题。但细节不少，咱们把它拆成三步。 第一步：K-Means 聚类 K-Means 本身很标准：  拿前  个点当初始中心 每个点归到最近的...

虫洞网络 题意 有  个虫洞网络，每个网络连接若干星系，激活需要一定能量。一旦激活某个网络，就能在该网络内的所有星系之间免费瞬移。 给定起点星系 、终点星系 、总能量 ，求从  到  的最小能量消耗。如果无法到达或能量不够，输出 。 思路 每个虫洞网络把一组星系"打包"在一起，付一次费就能在组内任意跳。怎么建模？ 最直接的想法：同一网络内任意两个星系之间连一条边，权值为激活成本。但如果一个网络有  个星系，就要连  条边，太多了。 更聪明的做法是引入虚拟节点。为每个网络创建一个虚拟节点，然后：  每个星系  虚拟节点：边权 = 该网络的激活成本（表示"花钱进入这个...

量子门 题意 有  个量子比特，初始状态用一个长度为  的 01 向量表示。有  个量子门可以操作，施加第  个门会翻转比特  本身，同时还会翻转所有与它有纠缠关系的比特 （给定  条纠缠关系  表示门  额外翻转比特 ）。每个门最多用一次（用两次等于没用）。 要求选出一个门的子集，使得施加后所有比特变为 0。若无解输出 -1；若有解，输出操作数最少、字典序最小的方案（升序输出门编号）。 数据范围： ， 思路 每个门要么用要么不用，用了就把一组比特全部异或 1——这不就是 （模 2 域）上的线性方程组吗？ 把每个门  的效果写成一个列向量 ，其中  表示门  会翻转比特 。设  表示是否使用门...

环形粒子加速器的能量校准 题意 给定一个长度为  的整数序列，它满足"循环单调非递减"性质：在环形意义下，至多存在一个断点位置 ，使得 （下标取模），其余相邻对都满足 。 现在要把一个新能量值  插入序列，使得新序列仍然满足这个性质。如果有多个合法位置，选下标最小的。 思路 先搞清楚"循环单调非递减"到底是什么。你可以把序列想象成一个环，沿着环走一圈，最多只能有一个地方是"下降"的。比如 [23, 37, 39, 49, 49, 16, 22]，从 49 到 16 有一个下降，其他都是非递减的——这就像一个排好序的数组被旋转了一下。 ...

最优分词器 题意 给定一个纯小写字母组成的文本串 text，一个词典（每个词带有分值），以及一些"相邻词对"的转移加分（可正可负）。 要求把 text 完整切分成词典中的词序列，使得词典分之和 + 相邻词之间的转移加分之和最大。如果无法完整覆盖，输出 。 思路 为什么普通 DP 不够？ 如果没有转移加分，这就是一个经典的"词典分词"问题：dp[i] 表示前  个字符能获得的最大分值，枚举以位置  结尾的所有词典词转移即可。 但加上了转移加分后，问题变了——当前能拿多少分，不仅取决于"切到了哪里"，还取决于"上一个词是什么&q...