任务批处理负载均衡 题意 把  个连续任务按顺序划分成  个批次（不能打乱顺序），每个批次有一个总计算成本（该批次内所有任务成本之和）。要求找到一种划分方案，使得  个批次的总计算成本的标准差最小。输出每个批次包含的任务数量。 思路 标准差最小，等价于什么？ 因为均值是固定的（总成本除以 ，跟怎么分无关），所以最小化标准差就是最小化方差，也就是最小化： $$ 其中  是第  批的总成本， 是均值。 问题转化成：把数组按顺序切  段，每段和尽量接近均值。这是一个经典的区间 DP。 定义  为前  个任务分成  个批次时，所有批次的  之和的最小值。转移方程： $$ 枚举上一段的结束位置 ，把第 ...

火星探测器稳定性分析 题意 给定  个环境稳定性指数（整数，范围 ），找出最长的连续子数组，满足：  所有元素都在  内 子数组内最大值与最小值的差   如果有多个等长的最长子数组，按起始索引从小到大输出。索引从  开始。 思路 两个约束怎么同时处理？ 先看第一个约束：每个元素都要在  内。这意味着一旦碰到范围外的元素，窗口就必须断开重新开始——这个元素是天然的分割点。 再看第二个约束：窗口内 。这是经典的"最大值减最小值不超过阈值的最长子数组"问题，用滑动窗口 + 单调队列解决。 具体做法：维护一个左端点 left，右端点 right 从左往右扫。遇到不在  的元素，直接...

时空漫游者的能量跳跃 题意 一条线性路径上有  个能量信标（编号  到 ），每个信标有一个能量值（可正可负）。从信标  出发，可以跳到前方距离  以内的任意信标（即 ）。从信标  出发跳到信标 ，求路径上收集到的最大能量总和。 思路 拿到这题，第一反应是什么？ 从起点到终点，每一步最多跳  格，要求路径上经过的信标能量之和最大——这不就是一个经典的 DP 模型吗？ 定义  为从信标  出发到达信标  时能收集到的最大能量。转移方程很直接： $$ 也就是说，到达  的最优方案 =  自身的能量 + 前面  个位置中  值最大的那个。 暴力做法每个位置回头扫  个，总复杂度 。能不能更快？ 注意到...

11294808 小苯的好区间 题目链接 https://www.nowcoder.com/practice/d47bbdc50a3941fc97e37f6d4217c535 题意 给两个长度为 n 的 01 字符串 s 和 t，求有多少区间 [l, r] 使得 s 和 t 在该区间按位或（OR）后得到一个"好串"（全为 0 或全为 1）。 思路分析 关键观察：先对每个位置 i 预处理 c[i] = s[i] OR t[i]，得到一个新的 01 串 c。  OR 结果全为 0：要求 s[i] = t[i] = '0'，即 c[i] = '0' OR 结果全为 1：要求每个位...

小红的等差数列 [题目链接](https://www.nowcoder.com/practice/425cf859f39e4012a7436b5729ff0b10) 思路 题目要求删除最少数字使数组变成等差数列。等价于：在原数组中找最长的等差子序列，删除的数量即为  减去该子序列长度。 最长等差子序列 DP 定义  为以第  个元素结尾、公差为  的最长等差子序列长度。 状态转移：枚举每个 ，令 ，则： $$ 若  不存在，视为 1（只有  本身），则 。 最终答案为 。 由于公差  的范围可能很大，用哈希表（unordered_map）存储每个位置的状态。 边界情况   时，任意数组都是等差...

11294805 小红的偏移值 题目链接: https://www.nowcoder.com/practice/adfc6ec3f23747a38c0029bec76127cd 题意 给定一个只含小写字母的字符串，定义一个字符串的「偏移值」为其中不同字母的数量。求所有非空子串的偏移值之和。 思路 贡献法。不直接枚举每个子串计算不同字母数（O(n^3) 或 O(n^2)），而是对每个字符位置 i，计算 s[i] 在多少个子串中「首次出现」，即作为该字符在子串中的最左出现位置。 设 prev[i] 为 s[i] 在位置 i 之前最近一次出现同一字母的位置（不存在则为 -1）。 那么 s[i] 作为...

小红和苹果树 [题目链接](https://www.nowcoder.com/practice/aba1a8a8d30f49619ce195d2a09029db) 思路 问题建模 苹果  的位置为 ，从第  秒开始下落，每秒下落 1 个单位，因此苹果到达  的时刻为： $$ 小红从时刻  出发，初始位置为 ，每秒最多移动  个单位。 小红能同时被苹果  和苹果 （设 ）砸到，当且仅当她能在时刻  到达 ，又在时刻  到达 ，即： $$ 此外，从初始位置  在时刻  到达  的条件为： $$ 转化为 DP 将问题转化为：在所有苹果中，找一个最长子序列，使得按  排序后相邻两个苹果均可连续到达，且...

小红的高频数字 题目链接: https://www.nowcoder.com/practice/b985c93a6fc949128682b4134aa2ebf7 题意 给定长度为  的数组和最多  次操作，每次操作可以将某个数加一。问操作后数组中出现次数最多的数最多出现几次。 解题思路 排序 + 滑动窗口 核心观察：  最优策略一定是选取一段连续区间的数，把它们都变成同一个数（即区间最大值）。 若数组排序后，选区间 ，把所有数都变成 ，所需操作数为 。  算法：  对数组排序。 使用滑动窗口维护区间 ，同时维护区间和 。 固定右端点 ，若当前窗口的操作数超过 ，则移动左端点  直到满足条件。 ...

小红的加边距离 [题目链接](https://www.nowcoder.com/practice/b53afc9bbc214e4e8a465d85ed2563d9) 思路 关键观察：加边后的距离公式 题目允许添加边 ，条件是原树中存在节点  使得  和  都是原树的边（即  在原树中有公共邻居）。 加边策略：对于原树中任意两节点 ，若它们在原树中的距离  且存在公共邻居，则可以直接连边。而对于树中距离为 2 的两个节点，它们一定共享同一个中间节点作为公共邻居。因此，将所有可能的边都加完后，两点之间的新距离为： $$ 直觉上，新图中每一步可以"跳过"一个中间节点，因此相当于原...

小苯的数组操作 [题目链接](https://www.nowcoder.com/practice/e507cdcb1d7f4254b9119d49149d7da9) 题目理解 给定长度为  的数组 ，允许以下两种操作（至多  次）将数组变为严格递减：  操作1（加法）：选择前缀  和整数 ，令 （）。 操作2（取模）：选择前缀  和整数 ，令 （）。  要求构造合法方案。 思路 关键观察 加法操作的核心性质：对前缀  的所有元素加同一个值 ，不改变该前缀内元素间的相对差。也就是说，（）保持不变。 这意味着：如果处理位置  时对前缀  加某个值，不会破坏已经满足的  的顺序关系（差值不变，若原来...

11294799 小淘的完美序列 题目链接: https://www.nowcoder.com/practice/7c391af0215a4a7595eb3dd3d9b7f107 支持语言: C++, Java --- 题意 给定正整数  和 ，构造一个长度为  的完美序列：序列中每个元素均为  的非零子掩码（即每个元素  满足  且 ），所有元素互不相同，且所有元素按升序排列，全部元素按位或等于 。 若无法构造则输出 NO，否则输出 YES 及序列。 --- 分析 可行性判断  的非零子掩码数量恰好为 ，其中 （ 的二进制中  的个数）。  若 ：不可能找到  个不同的正子掩码，输出 NO。...

小红的根节点个数 [题目链接](https://www.nowcoder.com/practice/bcc26fa906c64a3189939669f446dd73) 思路 问题建模 设  为节点  的权值的因子个数。当以节点  为根时，对于每条边 （ 为  的父节点），需满足 。 换根分析 固定以节点 1 为根，对每条边 （其中  是  的父节点）分析：  当根  不在  中时，方向为 （ 是子节点），约束为 ； 当根  在  中时，方向翻转为 （ 是子节点），约束为 。  因此对每条边  有：  若 ：根  必须在  中（否则约束违反）； 若 ：根  不能在  中； 若两者都违反：不存在合...

多重图问题？ [题目链接](https://www.nowcoder.com/practice/f95ed44fef0d40f8b82a1d5a2f8dca93) 思路 给定一张无向连通多重图（可能含自环和重边），小淘、小天、阿牛三人分别位于不同节点，图中还有一个宝藏节点。求三人到宝藏的最短路中，最小值和最大值。 关键观察  图中所有边权均为 1（题目要求经过的边数），因此最短路用 BFS 求解即可。 只需从宝藏节点出发做一次 BFS，得到宝藏到所有节点的最短距离，然后直接读取三人所在节点的距离值。 自环对最短路没有影响（走自环不会缩短到任何节点的距离），构建邻接表时跳过自环即可。 重边在无权...

串串异或 [题目链接](https://www.nowcoder.com/practice/6724661724314aa4ae0b1d4018ee9e34) 题意 定义两个字符串 （长度 ）和 （长度 ）的"异或"操作：  将两字符串右对齐，较短的字符串左侧用空格补齐； 从右往左逐位比较：相同则该位为 ，不同则该位为 ； 得到一个二进制串，将其转换为十进制输出（对  取模）。  思路 核心观察 对齐后，位置 （从末尾起， 索引）对应二进制数的第  位（即权重 ）。若该位字符不同，则答案加 。 因此： $$ 其中超出字符串范围的字符视为空格。 算法步骤  从  到  遍历；...