牛之国 [牛客链接](https://www.nowcoder.com/practice/98cd1d48b86943e487c7148cf5fca714) 思路 所有城市同时向所有其他城市派出施工队，速度为 1，两支施工队碰头即连通。对于城市  和城市 ，双方各派一支队伍沿最短路线相向而行，经过  年后碰头。因此在时刻 ，两座城市连通当且仅当 。 问题转化为：找到最小的 ，使得以  为阈值的距离图是连通的。这正是最小生成树的瓶颈边问题——对所有城市对建边，用 Kruskal 求 MST，答案就是 MST 中最长边除以 2 再向上取整。 为什么是瓶颈边？ MST 的一个经典性质：将所有边按权值...

牛牛的糖果树 题意 一棵  个节点的有根树（根为 ），每个节点有一个颜色 。牛牛选择一棵子树，先扔掉其中出现次数最多的颜色的所有糖果（若有多个颜色并列最多则全部扔掉），然后吃剩下的糖果。吃到的糖果颜色依次异或（同色多个糖果也逐个异或），求所有子树选择中异或和的最大值。 思路 DSU on tree（树上启发式合并） 先抓住一个关键性质：颜色  出现  次时，异或贡献为 （ 次），等于 （ 为奇）或 （ 为偶）。 因此，对于一棵子树：  设  = 所有节点颜色的异或和 设  = 出现次数最多的颜色的频率 若  为偶数，则被扔掉的颜色异或贡献为 ，答案就是  若  为奇数，则被扔掉的颜色异或贡献为...

牛牛与切割机 [题目链接](https://www.nowcoder.com/practice/cda06078a54142d29da7adc3b9ad5880) 思路 有一个序列 ，将其切割一刀，分成两个非空的连续子序列  和 （），切割代价为两部分元素和的乘积。求最小切割代价。 前缀和枚举 设总和为 ，前缀和为 。在位置  处切割的代价为： $$ 只需遍历所有合法切割点 ，维护前缀和并计算代价，取最小值即可。 样例演示 输入 ，总和 ：    切割位置  左部分和  右部分和  代价     1 1 14 14   2 3 12 36   3 6 9 54   4 10 5 50    最...

串 题意 给出  个只包含小写字母的字符串，将其中长度为奇数的字符串按顺序拼接后输出。 思路 纯模拟题，没有任何弯弯绕绕。 逐个读入字符串，判断长度是否为奇数（len % 2 == 1），如果是就拼接到结果串的末尾。最后输出即可。 唯一需要注意的点：字符串总长度可能很大（题目说总和不超过某个值），所以拼接时用 StringBuilder（Java）或直接 +=（C++ 的 string）即可，不需要额外优化。 代码    C++   Java   #include <bits/stdc++.h> using namespace std; int main(){ int n; sca...

小美的梯子 [题目链接](https://www.nowcoder.com/practice/bd5627c6d0c14951b8072830e26a041b) 思路 每个梯子的形状为 |=|，由左右各一个 | 和中间一个 = 组成。多个梯子排成一行时，相邻梯子可以共用 |，例如两个梯子为 |=|=|。 观察规律： 个梯子需要  个 | 和  个 =。设有  个 | 和  个 =，则：  | 的约束：，即  = 的约束：  因此答案为 。注意当  时无法构成任何梯子，答案为 。 复杂度分析  时间复杂度：，只需一次读入和一次取最小值运算。 空间复杂度：，仅使用常数个变量。  代码    C++...

订单分类 [题目链接](https://www.nowcoder.com/practice/6c685c2ff88043989c09ba9c10785f0a) 思路 给定若干订单 ID（由字母、数字和特殊字符组成），根据首字符类型和剩余字符的组成进行分类。这是一道字符串模拟题，按规则逐条判断即可。 分类规则 设 ID 的第一个字符为 first，剩余部分为 rest：  electronics：first 是字母，且 rest 非空且全为数字。 clothing：first 是数字，且 rest 非空且全为字母。 accessories：first 是字母，且 rest 全为字母或数字（包括 ...

小美的数对合并 [题目链接](https://www.nowcoder.com/practice/feea5d33fef743aeb718e4ab6fbaf9a2) 思路 给定长度为  的数组 ，对于满足  且  的点对 ，在  和  之间连一条无向边。求图中极大连通块的数量。 变量替换 令 ，则条件  等价于： $$ 因此，当  时， 之间有边当且仅当 ，即  数组在位置  上存在逆序对。 连通块一定是连续段 如果 （），那么对于任意 ：  若 ，则  构成逆序对， 与  相连； 若 ，则 ， 构成逆序对， 与  相连。  因此  和  之间的所有点都与  或  处于同一连通块。这说明连通块...

图像处理中的卷积操作实现 [题目链接](https://www.nowcoder.com/practice/798b474486af4528b9722feacc39aafb) 思路 本题要求对灰度图像矩阵进行二维卷积操作，使用零填充（zero padding）处理边界。 核心步骤：  零填充：设卷积核尺寸为 ，令 。在原始  图像的四周各填充  层零，得到  的填充矩阵。   逐像素卷积：对输出矩阵的每个位置 ，从填充矩阵中取出以  为中心的  区域，与卷积核逐元素相乘后求和：  $$  格式化输出：每个结果用 Python 的 round(x, 2) 保留两位小数，再转字符串输出（尾部多余的...

我们惺惺相惜 [题目链接](https://www.nowcoder.com/practice/e5cb693b91fe405e8aa233503b7fced5) 思路 核心转化：Dilworth 定理 题目要求判断子数组  能否分成两个非空的严格递增子序列。由 Dilworth 定理，一个序列能被划分成至多  条严格递增子序列，当且仅当最长非递增子序列的长度不超过 。 注意，如果子数组本身就是严格递增的，我们也可以把它拆成两个非空部分，两部分各自严格递增。因此只要子数组长度  且能被至多 2 条严格递增子序列覆盖，答案就是 YES。 等价条件：子数组  是"好区间"   ...

小美的陡峭值操作 [题目链接](https://www.nowcoder.com/practice/a4d34a7d8fb145af85f7190ee91dddf3) 思路 定义数组的陡峭值为相邻元素之差的绝对值之和：。可以最多进行一次操作：选一个区间 ，将区间内所有元素加 1。求操作后陡峭值的最小值。 操作对差分的影响 设差分 ，则陡峭值 。 对区间  整体加 1，只影响区间边界处的两个差分值：  若 ： 增加 1（左边界外侧和内侧的差距变大） 若 ： 减少 1（右边界内侧和外侧的差距变小）  区间内部的差分完全不变。因此问题转化为：选两个位置 （分别对应  和 ），使得  相比  的减少量...

行走 [题目链接](https://www.nowcoder.com/practice/9c9835bf3c9c4947bce69e30d4412217) 思路 小美在二维坐标平面上，从  出发，进行  次移动。第  次移动选择满足  的整数 ，移动到 。问能否恰好到达 。 三个关键条件 设目标曼哈顿距离 ，总步长和 ，最大步长 。 条件一：总步长足够。 显然需要 ，否则无论怎么走都到不了。 条件二：奇偶性匹配。 每步移动  的曼哈顿距离，净位移的曼哈顿距离与  同奇偶（多走的部分必须以"往返"形式抵消，每次抵消消耗 2 的距离）。因此需要 。 条件三：最大步长不能过大。 ...

信用评分模型优化 [题目链接](https://www.nowcoder.com/practice/27a2c6a4127c4c7080d34fc017d337bc) 思路 给定一组申请者的特征数据和信用评分结果（'G' 表示良好，'B' 表示不良），需要计算每个特征的信息增益比（Information Gain Ratio），输出信息增益比最高的特征索引。 信息增益比 信息增益比是 C4.5 决策树算法使用的特征选择准则，定义为： $$ 其中：   是特征  对数据集  的信息增益；  是特征  的固有值（Intrinsic Value），也称分裂信息。  信息熵 数据集  的信息熵定义为：...

小红闯关 [题目链接](https://www.nowcoder.com/practice/7ce4b75f7a304be481e73bc4dd2705a4) 思路 有  个关卡，通过第  个关卡需要  单位时间，必须按顺序通过。每通过  个关卡（包括用跳关道具跳过的关卡），获得一个跳关道具，使用后可以  时间通过任意一个关卡。求通过所有关卡的最少时间。 关键观察 无论哪些关卡被跳过，每个关卡都会被"通过"（要么花时间，要么用道具跳过），因此关卡的完成进度是固定的——通过前  个关卡后，总共获得  个跳关道具。 第  个道具在通过第  个关卡后获得，最早可用于第  个关卡。...

小红的完全平方数 [题目链接](https://www.nowcoder.com/practice/8e83151b7a5b4e1196eb9aa4c4ff7d95) 思路 数组是"好数组"当且仅当任意两个元素的乘积都是完全平方数。每次操作可以选一个元素乘以任意正整数，求最少操作次数。 核心观察：无平方因子部分 对于正整数 ，将其质因数分解为 ，定义  的无平方因子部分（square-free part）为： $$ 即保留所有指数为奇数的质因子，各取一次。例如 ，。 关键性质：两个正整数  的乘积  是完全平方数，当且仅当 。 证明： 是完全平方数等价于  的所有质因子指数...