科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本文以灵茶山艾府灵神在 codeforces-go 仓库中收录的力扣双周赛 160 全部四题题解为主体逐一拆解 Q1–Q4 的数学建模、算法选型与四种语言的实现差异。读完本文你将掌握「库函数进制转换的边界处理」「带等待约束的网格图 DP 归约技巧」「动态计算边权的最短路建模」「二分答案 子数组 GCDLogTrick的判定思路」并能直接对照仓库内的 Go 源码与测试用例进行本地验证。赛题概览双周赛 160 的四道题覆盖了四种典型算法模型仓库在 leetcode/biweekly/160 下按 a/b/c/d 四个子目录组织每个子目录都包含README.md完整多语言题解、x.goGo 提交版、x.txt测试样例数据和x_test.go测试入口题目核心算法对应目录Q1 十六进制与三十六进制转换进制转换、库函数与手写实现a/Q2 交替方向最小成本路径 II网格图 DP记忆化搜索 → 递推 → 空间优化b/Q3 有向图中到达目的地的最短时间动态边权 Dijkstrac/Q4 数组稳定性因子二分答案 LogTrick 贪心d/仓库中每个子目录的测试文件由模板自动生成例如 b_test.go 通过testutil.RunLeetCodeFuncWithFile(t, minCost, b.txt, 0)读取b.txt中的输入输出对来校验实现这为复现和验证题解提供了现成闭环。Q1十六进制与三十六进制转换进制转换Q1 要求实现函数concatHex36(n)输出n²的十六进制表示字母大写与n³的三十六进制表示字母大写的拼接字符串。它是整场比赛中思维难度最低、但对语言基础库熟练度要求最高的一题。库函数写法Python / Java / Go三种语言都提供了现成的进制转换设施Python利用 numpy 的np.base_repr(n, base)直接得到任意进制的字符串表示一行完成np.base_repr(n ** 2, base16) np.base_repr(n ** 3, base36)。JavaInteger.toHexString(n * n)输出十六进制自带小写字母Integer.toString(n * n * n, 36)输出三十六进制最后统一toUpperCase()。Gostrconv.FormatInt(int64(n*n), 16)与strconv.FormatInt(int64(n*n*n), 36)拼接后strings.ToUpper(s)。仓库中的提交版实现如下见 a.gofunc concatHex36(n int) string { s : strconv.FormatInt(int64(n*n), 16) strconv.FormatInt(int64(n*n*n), 36) return strings.ToUpper(s) }需要注意的两个细节溢出风险n*n*n可能超过 32 位整数范围Go 侧显式转成int64Java 侧如果n较大则需考虑乘法溢出这是比赛中容易踩的坑大小写统一库函数输出的字母可能为小写如 Go 的FormatInt必须通过ToUpper对齐题目对字母大写的约束。手写写法CC 标准库没有直接支持三十六进制的转换题解给出了手写base_repr(v, base)循环取v % base得到当前位d 10时映射到0d否则映射到Ad-10最后翻转字符串。该写法适用于任意base ≤ 36本质上是「除基取余 逆序输出」的标准流程值得在其他语言中遇到同样需求时复用。复杂度分析时间复杂度O(log n)因为O(log n³) O(3·log n) O(log n)空间复杂度O(log n)用于存放结果字符串。Q2交替方向最小成本路径 II网格图 DPQ2 是经典题「64. 最小路径和」的变形。题解建议先完成简单版本再切入本题核心难点在于交替移动模式与等待成本的建模。问题转化把等待成本并入进入成本题目从第 1 秒奇数秒出发因此下一步必然进入相邻单元格并处于偶数秒此时必须等待 1 秒等待后回到奇数秒又必须移动。由此可以推出关键结论问题等价于把每个单元格的代价设为waitCost[i][j] (i1)·(j1)在此基础上求最小路径和。⚠️ 起点和终点无需等待只需计算进入成本。这个转化把「时间奇偶性 等待」的复杂约束归约成了纯网格 DP直接套用 64 题的转移即可。方案一记忆化搜索自顶向下以 Go 实现为例b.godfs(i, j)表示到达(i,j)的最小总成本var dfs func(int, int) int dfs func(i, j int) (res int) { if i 0 || j 0 { return math.MaxInt } if i 0 j 0 { return 1 // 起点只有进入成本不需要等待 } p : memo[i][j] if *p 0 { *p min(dfs(i, j-1), dfs(i-1, j)) waitCost[i][j] (i1)*(j1) } return *p } return int64(dfs(m-1, n-1) - waitCost[m-1][n-1]) // 终点不需要等待边界越界返回MaxInt表示不可达起点返回1题目规定起点进入成本为 1无需等待每个状态由上方(i-1,j)与左侧(i,j-1)转移而来加上当前格进入成本waitCost[i][j]与等待成本(i1)·(j1)最终答案要减去终点的waitCost因为终点不需要等待这就是 README 中反复强调的「起点和终点无需等待」。方案二1:1 翻译成递推自底向上记忆化搜索与递推只是顺序不同。递推版用f[i1][j1]保存答案并用一个巧妙的初始化让边界自动对齐f[0][1] -waitCost[0][0] // 计算 f[1][1] 的时候抵消掉 for i, row : range waitCost { f[i1][0] math.MaxInt for j, c : range row { f[i1][j1] min(f[i1][j], f[i][j1]) c (i1)*(j1) } } return int64(f[m][n] - waitCost[m-1][n-1])f[0][1] -waitCost[0][0]的设计非常精妙转移f[1][1] f[0][1] waitCost[0][0] 1时恰好抵消掉起点的进入成本只留下等待成本从而避免对起点特判。方案三空间优化一—— 去掉第一维由于f[i1][j1]只依赖当前行左侧与上一行同列可以压缩为一维数组b.gof : make([]int, n1) for j : range f { f[j] math.MaxInt } f[1] -waitCost[0][0] for i, row : range waitCost { for j, c : range row { f[j1] min(f[j], f[j1]) c (i1)*(j1) } } return int64(f[n] - waitCost[m-1][n-1])空间复杂度从O(mn)降到O(n)。方案四空间优化二—— 原地修改 waitCost直接把waitCost当作 DP 数组注意起点赋1、终点赋0先处理首行首列再逐格累加。这要求数组元素类型能容纳中间结果Python 与 Go 可行而 C/Java 的 32 位int数组会溢出因此题解明确标注「C 和 Java 的数组是 32 位整数无法实现」——这是方案四不适用于全部语言的硬性约束func minCost(m, n int, f [][]int) int64 { f[0][0] 1 f[m-1][n-1] 0 for j : 1; j n; j { f[0][j] f[0][j-1] j 1 } for i : 1; i m; i { f[i][0] f[i-1][0] i 1 for j : 1; j n; j { f[i][j] min(f[i][j-1], f[i-1][j]) (i1)*(j1) } } return int64(f[m-1][n-1]) }注意第一行/第一列没有上方/左侧来源要单独按f[i][0] f[i-1][0] i1递推这正是原地版区别于带哨兵版的地方。四种方案的时间复杂度均为O(mn)空间复杂度依次为O(mn)、O(mn)、O(n)、O(1)对比清晰呈现了网格 DP 优化的完整路径。Q3有向图中到达目的地的最短时间动态边权 DijkstraQ3 是一道「披着图论外衣」的 Dijkstra 应用题每条边有开放时间窗[start, end]必须在该窗口内出发且移动耗时恒为 1。题解直截了当地给出结论直接套 Dijkstra 模板关键在于正确理解动态边权。边权为什么是动态的设起点到x的最短时间为d_x。从x出发到邻居y出发时间是max(d_x, start_i)早到了就等到start_i再走且必须满足max(d_x, start_i) ≤ end_i到达y的时间是max(d_x, start_i) 1。因此这条边的有效边权是max(d_x, start_i) 1 - d_x它与当前节点到达时间d_x相关是动态计算的。其性质是到达越早边权越大到达越晚边权越小最小为 1。由于边权恒为非负Dijkstra 的正确性不受影响这是本题能用 Dijkstra 的根本前提。Go 实现要点仓库实现见 c.go其中自定义了小根堆hp实现container/heap的Len/Less/Swap/Push/Pop接口这是算法竞赛中避免标准库泛型开销的常见写法。核心松弛逻辑for _, e : range g[x] { y : e.to newD : max(d, e.start) 1 if newD-1 e.end newD dis[y] { dis[y] newD heap.Push(h, pair{newD, y}) } }要点松弛条件newD-1 e.end等价于出发时间max(dx, start) ≤ end即必须赶在窗口关闭前出发newD dis[y]是标准 Dijkstra 的距离松弛当堆顶节点是n-1时直接返回d提前终止这与在 README 中标注的「走到终点即可返回」一致全部出队仍找不到终点则返回-1。复杂度分析时间复杂度O(n m·log m)其中m是edges长度空间复杂度O(n m)邻接表 距离数组。Q4数组稳定性因子二分答案 LogTrick 贪心Q4 是全场压轴题综合了二分答案、子数组 GCD 性质LogTrick与贪心策略。题解先抛出转化思路再给出优化前与两种优化写法是四题中最值得精读的一篇。转化最小化最大值 → 二分答案「最小化最大值」是二分答案的经典信号。原问题被转化成判定性问题给定上界upper能否通过至多maxC次修改把某个元素改成 1让数组的稳定性因子最长稳定子数组的长度即所有元素 GCD ≥ 2 的最长子数组长度不超过upper若能说明答案≤ upper上界还可以更小若不能说明答案 upper上界必须增大。这正是二分可行性的单调性来源。贪心决策修改哪个元素遍历nums用 LogTrick 维护以i为右端点的所有子数组 GCD。当发现某个 GCD ≥ 2 的最长子数组长度 upper时必须修改。修改谁若改i左边的元素nums[i]仍可能和后续元素组成不合法子数组若把nums[i]改成 1则包含nums[i]的任意子数组的 GCD 均为 1后续无需再考虑它严格优于改左边。因此贪心策略是发现非法长段时把当前右端点nums[i]改成 1 并消耗一次修改机会。遍历结束若修改次数 ≤maxC判定成立。二分边界与上取整恒等式题解推荐开区间二分check(mid) true时更新的是谁最后就返回谁避免加一减一的边界困扰。左端点初始值-1子数组长度不可能为负必不满足右端点初始值n不修改一定满足右端点优化将n个白球中maxC个涂黑后剩余n - maxC个白球均分成maxC1段最长连续白球长度为⌈(n - maxC)/(maxC1)⌉该值作为上界必满足要求。利用上取整恒等式⌈a/b⌉ ⌊(ab-1)/b⌋a ≥ 0b ≥ 1可得⌈(n - maxC)/(maxC1)⌉ ⌊n/(maxC1)⌋于是 Go 侧可直接用sort.Search(n/(maxC1), ...)作为二分上界即 d.go 中的写法。优化前二分内嵌 LogTrickcheck(upper)每次遍历都做一次 LogTrick对每个i更新所有区间 GCD、去重合并 GCD 相同的区间intervals越靠左 GCD 越小再判断i - intervals[0].l 1 upper时消耗一次修改并intervals.clear()因为改成 1 后 GCD 全为 1直接清空。复杂度为O(n·log U · log M)其中U max(nums)M n/maxC。优化写法一预计算 leftMin每次二分都重算 LogTrick 较慢。可以先预处理leftMin[i]以i为右端点、GCD ≥ 2 的子数组的最小左端点不存在则为n。之后check(upper)变成一次线性扫描d.goans : sort.Search(n/(maxC1), func(upper int) bool { c : maxC i : upper for i n { if i-leftMin[i]1 upper { if c 0 { return false } c-- i upper 1 // 修改 nums[i]1 后跳过当前及后续受影响的右端点 } else { i } } return true })跳步i upper 1的依据把nums[i]改成 1 后任何包含i的子数组 GCD 均为 1因此下一个可能需要检查的右端点直接从iupper1开始。预处理部分用哨兵{1, 0}简化了「GCD ≥ 2 的最长子数组」的获取intervals[1]即为该区间。复杂度降为O(n·log U n·log M)。优化写法二栈 滑动窗口另一种预处理leftMin的方式借鉴 3171 题的技巧维护滑动窗口内元素 GCD 的栈窗口左端left移动时用「栈重建」从i-1向left反向做后缀 GCD摊销更新从而在线性时间内求出每个右端点的最小合法左端点。两种优化写法的二分部分完全一致仅预处理不同最终复杂度同为O(n·log U n·log M)空间O(n)见 d.go。仓库复现与自测指南仓库以「题解 实现 数据 测试」四件套组织每题README、.go、.txt、_test.go可直接在本仓库复现验证查看完整题解每题的多语言详解在 a/README.md、b/README.md、c/README.md、d/README.md含 Python/Java/C/Go 四语代码、复杂度分析与专题训练指引Go 提交版实现各子目录下的x.go即提交可用的完整代码如 b.go 同时保留记忆化、递推与两种空间优化共 4 个版本d.go 保留两种 leftMin 预处理写法便于对照学习跑测试验证测试入口由模板生成如 c_test.go 调用testutil.RunLeetCodeFuncWithFile(t, minTime, c.txt, 0)读取官方样例数据 c.txt。在仓库根目录执行go test ./leetcode/biweekly/160/...即可一键验证四题实现与数据是否一致延伸训练每份题解末尾的「专题训练」与「分类题单」均指向仓库作者整理的算法题单体系Q2 对应「网格图 DP」、Q3 对应「单源最短路Dijkstra 算法」、Q4 对应「二分答案·最小化最大值」与「LogTrick」专题可作为赛后同类题强化路径。小结双周赛 160 的难点分布层次分明Q1 考察进制转换的库函数与边界意识Q2 用「等待成本并入进入成本」将带约束网格图归约为经典最小路径和Q3 用动态边权复用了最短路模板Q4 则串联起二分答案、LogTrick 与贪心修改策略。四题的 Go 实现、样例数据与测试入口均已收录在仓库对应目录按上文路径即可完成从「读懂思路」到「本地跑通」的完整闭环。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 题解动态边权最短路 Dijkstra——力扣双周赛 160 第三题 minTime 深度解析codeforces go 题解动态边权最短路 Dijkstra——力扣双周赛 160 第三题 minTime 深度解析 本篇以算法竞赛模板库 codefor科学计算codeforces-go 仓库题解力扣双周赛 160 的十六进制与三十六进制转换问题concatHex36codeforces go 仓库题解力扣双周赛 160 的十六进制与三十六进制转换问题concatHex36 本篇以 leetcode/biweekly/科学计算distribution 项目中 otlploggrpc 导出器实验特性全解析通过 OTEL_GO_X_OBSERVABILITY 开启导出器自观测distribution 项目中 otlploggrpc 导出器实验特性全解析通过 OTEL_GO_X_OBSERVABILITY 开启导出器自观测 本文围绕科学计算上一篇TypeScript 从模块获取类型The Concise TypeScript Book 第 37 章的导出值与跨模块类型推断实战下一篇5步掌握Switch大气层系统从零到精通的完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 力扣双周赛 160 全题解：进制转换、网格图 DP、动态边权 Dijkstra 与二分答案 + LogTrick（附 Go 源码）
科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本文以灵茶山艾府灵神在 codeforces-go 仓库中收录的力扣双周赛 160 全部四题题解为主体逐一拆解 Q1–Q4 的数学建模、算法选型与四种语言的实现差异。读完本文你将掌握「库函数进制转换的边界处理」「带等待约束的网格图 DP 归约技巧」「动态计算边权的最短路建模」「二分答案 子数组 GCDLogTrick的判定思路」并能直接对照仓库内的 Go 源码与测试用例进行本地验证。赛题概览双周赛 160 的四道题覆盖了四种典型算法模型仓库在 leetcode/biweekly/160 下按 a/b/c/d 四个子目录组织每个子目录都包含README.md完整多语言题解、x.goGo 提交版、x.txt测试样例数据和x_test.go测试入口题目核心算法对应目录Q1 十六进制与三十六进制转换进制转换、库函数与手写实现a/Q2 交替方向最小成本路径 II网格图 DP记忆化搜索 → 递推 → 空间优化b/Q3 有向图中到达目的地的最短时间动态边权 Dijkstrac/Q4 数组稳定性因子二分答案 LogTrick 贪心d/仓库中每个子目录的测试文件由模板自动生成例如 b_test.go 通过testutil.RunLeetCodeFuncWithFile(t, minCost, b.txt, 0)读取b.txt中的输入输出对来校验实现这为复现和验证题解提供了现成闭环。Q1十六进制与三十六进制转换进制转换Q1 要求实现函数concatHex36(n)输出n²的十六进制表示字母大写与n³的三十六进制表示字母大写的拼接字符串。它是整场比赛中思维难度最低、但对语言基础库熟练度要求最高的一题。库函数写法Python / Java / Go三种语言都提供了现成的进制转换设施Python利用 numpy 的np.base_repr(n, base)直接得到任意进制的字符串表示一行完成np.base_repr(n ** 2, base16) np.base_repr(n ** 3, base36)。JavaInteger.toHexString(n * n)输出十六进制自带小写字母Integer.toString(n * n * n, 36)输出三十六进制最后统一toUpperCase()。Gostrconv.FormatInt(int64(n*n), 16)与strconv.FormatInt(int64(n*n*n), 36)拼接后strings.ToUpper(s)。仓库中的提交版实现如下见 a.gofunc concatHex36(n int) string { s : strconv.FormatInt(int64(n*n), 16) strconv.FormatInt(int64(n*n*n), 36) return strings.ToUpper(s) }需要注意的两个细节溢出风险n*n*n可能超过 32 位整数范围Go 侧显式转成int64Java 侧如果n较大则需考虑乘法溢出这是比赛中容易踩的坑大小写统一库函数输出的字母可能为小写如 Go 的FormatInt必须通过ToUpper对齐题目对字母大写的约束。手写写法CC 标准库没有直接支持三十六进制的转换题解给出了手写base_repr(v, base)循环取v % base得到当前位d 10时映射到0d否则映射到Ad-10最后翻转字符串。该写法适用于任意base ≤ 36本质上是「除基取余 逆序输出」的标准流程值得在其他语言中遇到同样需求时复用。复杂度分析时间复杂度O(log n)因为O(log n³) O(3·log n) O(log n)空间复杂度O(log n)用于存放结果字符串。Q2交替方向最小成本路径 II网格图 DPQ2 是经典题「64. 最小路径和」的变形。题解建议先完成简单版本再切入本题核心难点在于交替移动模式与等待成本的建模。问题转化把等待成本并入进入成本题目从第 1 秒奇数秒出发因此下一步必然进入相邻单元格并处于偶数秒此时必须等待 1 秒等待后回到奇数秒又必须移动。由此可以推出关键结论问题等价于把每个单元格的代价设为waitCost[i][j] (i1)·(j1)在此基础上求最小路径和。⚠️ 起点和终点无需等待只需计算进入成本。这个转化把「时间奇偶性 等待」的复杂约束归约成了纯网格 DP直接套用 64 题的转移即可。方案一记忆化搜索自顶向下以 Go 实现为例b.godfs(i, j)表示到达(i,j)的最小总成本var dfs func(int, int) int dfs func(i, j int) (res int) { if i 0 || j 0 { return math.MaxInt } if i 0 j 0 { return 1 // 起点只有进入成本不需要等待 } p : memo[i][j] if *p 0 { *p min(dfs(i, j-1), dfs(i-1, j)) waitCost[i][j] (i1)*(j1) } return *p } return int64(dfs(m-1, n-1) - waitCost[m-1][n-1]) // 终点不需要等待边界越界返回MaxInt表示不可达起点返回1题目规定起点进入成本为 1无需等待每个状态由上方(i-1,j)与左侧(i,j-1)转移而来加上当前格进入成本waitCost[i][j]与等待成本(i1)·(j1)最终答案要减去终点的waitCost因为终点不需要等待这就是 README 中反复强调的「起点和终点无需等待」。方案二1:1 翻译成递推自底向上记忆化搜索与递推只是顺序不同。递推版用f[i1][j1]保存答案并用一个巧妙的初始化让边界自动对齐f[0][1] -waitCost[0][0] // 计算 f[1][1] 的时候抵消掉 for i, row : range waitCost { f[i1][0] math.MaxInt for j, c : range row { f[i1][j1] min(f[i1][j], f[i][j1]) c (i1)*(j1) } } return int64(f[m][n] - waitCost[m-1][n-1])f[0][1] -waitCost[0][0]的设计非常精妙转移f[1][1] f[0][1] waitCost[0][0] 1时恰好抵消掉起点的进入成本只留下等待成本从而避免对起点特判。方案三空间优化一—— 去掉第一维由于f[i1][j1]只依赖当前行左侧与上一行同列可以压缩为一维数组b.gof : make([]int, n1) for j : range f { f[j] math.MaxInt } f[1] -waitCost[0][0] for i, row : range waitCost { for j, c : range row { f[j1] min(f[j], f[j1]) c (i1)*(j1) } } return int64(f[n] - waitCost[m-1][n-1])空间复杂度从O(mn)降到O(n)。方案四空间优化二—— 原地修改 waitCost直接把waitCost当作 DP 数组注意起点赋1、终点赋0先处理首行首列再逐格累加。这要求数组元素类型能容纳中间结果Python 与 Go 可行而 C/Java 的 32 位int数组会溢出因此题解明确标注「C 和 Java 的数组是 32 位整数无法实现」——这是方案四不适用于全部语言的硬性约束func minCost(m, n int, f [][]int) int64 { f[0][0] 1 f[m-1][n-1] 0 for j : 1; j n; j { f[0][j] f[0][j-1] j 1 } for i : 1; i m; i { f[i][0] f[i-1][0] i 1 for j : 1; j n; j { f[i][j] min(f[i][j-1], f[i-1][j]) (i1)*(j1) } } return int64(f[m-1][n-1]) }注意第一行/第一列没有上方/左侧来源要单独按f[i][0] f[i-1][0] i1递推这正是原地版区别于带哨兵版的地方。四种方案的时间复杂度均为O(mn)空间复杂度依次为O(mn)、O(mn)、O(n)、O(1)对比清晰呈现了网格 DP 优化的完整路径。Q3有向图中到达目的地的最短时间动态边权 DijkstraQ3 是一道「披着图论外衣」的 Dijkstra 应用题每条边有开放时间窗[start, end]必须在该窗口内出发且移动耗时恒为 1。题解直截了当地给出结论直接套 Dijkstra 模板关键在于正确理解动态边权。边权为什么是动态的设起点到x的最短时间为d_x。从x出发到邻居y出发时间是max(d_x, start_i)早到了就等到start_i再走且必须满足max(d_x, start_i) ≤ end_i到达y的时间是max(d_x, start_i) 1。因此这条边的有效边权是max(d_x, start_i) 1 - d_x它与当前节点到达时间d_x相关是动态计算的。其性质是到达越早边权越大到达越晚边权越小最小为 1。由于边权恒为非负Dijkstra 的正确性不受影响这是本题能用 Dijkstra 的根本前提。Go 实现要点仓库实现见 c.go其中自定义了小根堆hp实现container/heap的Len/Less/Swap/Push/Pop接口这是算法竞赛中避免标准库泛型开销的常见写法。核心松弛逻辑for _, e : range g[x] { y : e.to newD : max(d, e.start) 1 if newD-1 e.end newD dis[y] { dis[y] newD heap.Push(h, pair{newD, y}) } }要点松弛条件newD-1 e.end等价于出发时间max(dx, start) ≤ end即必须赶在窗口关闭前出发newD dis[y]是标准 Dijkstra 的距离松弛当堆顶节点是n-1时直接返回d提前终止这与在 README 中标注的「走到终点即可返回」一致全部出队仍找不到终点则返回-1。复杂度分析时间复杂度O(n m·log m)其中m是edges长度空间复杂度O(n m)邻接表 距离数组。Q4数组稳定性因子二分答案 LogTrick 贪心Q4 是全场压轴题综合了二分答案、子数组 GCD 性质LogTrick与贪心策略。题解先抛出转化思路再给出优化前与两种优化写法是四题中最值得精读的一篇。转化最小化最大值 → 二分答案「最小化最大值」是二分答案的经典信号。原问题被转化成判定性问题给定上界upper能否通过至多maxC次修改把某个元素改成 1让数组的稳定性因子最长稳定子数组的长度即所有元素 GCD ≥ 2 的最长子数组长度不超过upper若能说明答案≤ upper上界还可以更小若不能说明答案 upper上界必须增大。这正是二分可行性的单调性来源。贪心决策修改哪个元素遍历nums用 LogTrick 维护以i为右端点的所有子数组 GCD。当发现某个 GCD ≥ 2 的最长子数组长度 upper时必须修改。修改谁若改i左边的元素nums[i]仍可能和后续元素组成不合法子数组若把nums[i]改成 1则包含nums[i]的任意子数组的 GCD 均为 1后续无需再考虑它严格优于改左边。因此贪心策略是发现非法长段时把当前右端点nums[i]改成 1 并消耗一次修改机会。遍历结束若修改次数 ≤maxC判定成立。二分边界与上取整恒等式题解推荐开区间二分check(mid) true时更新的是谁最后就返回谁避免加一减一的边界困扰。左端点初始值-1子数组长度不可能为负必不满足右端点初始值n不修改一定满足右端点优化将n个白球中maxC个涂黑后剩余n - maxC个白球均分成maxC1段最长连续白球长度为⌈(n - maxC)/(maxC1)⌉该值作为上界必满足要求。利用上取整恒等式⌈a/b⌉ ⌊(ab-1)/b⌋a ≥ 0b ≥ 1可得⌈(n - maxC)/(maxC1)⌉ ⌊n/(maxC1)⌋于是 Go 侧可直接用sort.Search(n/(maxC1), ...)作为二分上界即 d.go 中的写法。优化前二分内嵌 LogTrickcheck(upper)每次遍历都做一次 LogTrick对每个i更新所有区间 GCD、去重合并 GCD 相同的区间intervals越靠左 GCD 越小再判断i - intervals[0].l 1 upper时消耗一次修改并intervals.clear()因为改成 1 后 GCD 全为 1直接清空。复杂度为O(n·log U · log M)其中U max(nums)M n/maxC。优化写法一预计算 leftMin每次二分都重算 LogTrick 较慢。可以先预处理leftMin[i]以i为右端点、GCD ≥ 2 的子数组的最小左端点不存在则为n。之后check(upper)变成一次线性扫描d.goans : sort.Search(n/(maxC1), func(upper int) bool { c : maxC i : upper for i n { if i-leftMin[i]1 upper { if c 0 { return false } c-- i upper 1 // 修改 nums[i]1 后跳过当前及后续受影响的右端点 } else { i } } return true })跳步i upper 1的依据把nums[i]改成 1 后任何包含i的子数组 GCD 均为 1因此下一个可能需要检查的右端点直接从iupper1开始。预处理部分用哨兵{1, 0}简化了「GCD ≥ 2 的最长子数组」的获取intervals[1]即为该区间。复杂度降为O(n·log U n·log M)。优化写法二栈 滑动窗口另一种预处理leftMin的方式借鉴 3171 题的技巧维护滑动窗口内元素 GCD 的栈窗口左端left移动时用「栈重建」从i-1向left反向做后缀 GCD摊销更新从而在线性时间内求出每个右端点的最小合法左端点。两种优化写法的二分部分完全一致仅预处理不同最终复杂度同为O(n·log U n·log M)空间O(n)见 d.go。仓库复现与自测指南仓库以「题解 实现 数据 测试」四件套组织每题README、.go、.txt、_test.go可直接在本仓库复现验证查看完整题解每题的多语言详解在 a/README.md、b/README.md、c/README.md、d/README.md含 Python/Java/C/Go 四语代码、复杂度分析与专题训练指引Go 提交版实现各子目录下的x.go即提交可用的完整代码如 b.go 同时保留记忆化、递推与两种空间优化共 4 个版本d.go 保留两种 leftMin 预处理写法便于对照学习跑测试验证测试入口由模板生成如 c_test.go 调用testutil.RunLeetCodeFuncWithFile(t, minTime, c.txt, 0)读取官方样例数据 c.txt。在仓库根目录执行go test ./leetcode/biweekly/160/...即可一键验证四题实现与数据是否一致延伸训练每份题解末尾的「专题训练」与「分类题单」均指向仓库作者整理的算法题单体系Q2 对应「网格图 DP」、Q3 对应「单源最短路Dijkstra 算法」、Q4 对应「二分答案·最小化最大值」与「LogTrick」专题可作为赛后同类题强化路径。小结双周赛 160 的难点分布层次分明Q1 考察进制转换的库函数与边界意识Q2 用「等待成本并入进入成本」将带约束网格图归约为经典最小路径和Q3 用动态边权复用了最短路模板Q4 则串联起二分答案、LogTrick 与贪心修改策略。四题的 Go 实现、样例数据与测试入口均已收录在仓库对应目录按上文路径即可完成从「读懂思路」到「本地跑通」的完整闭环。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 题解动态边权最短路 Dijkstra——力扣双周赛 160 第三题 minTime 深度解析codeforces go 题解动态边权最短路 Dijkstra——力扣双周赛 160 第三题 minTime 深度解析 本篇以算法竞赛模板库 codefor科学计算codeforces-go 仓库题解力扣双周赛 160 的十六进制与三十六进制转换问题concatHex36codeforces go 仓库题解力扣双周赛 160 的十六进制与三十六进制转换问题concatHex36 本篇以 leetcode/biweekly/科学计算distribution 项目中 otlploggrpc 导出器实验特性全解析通过 OTEL_GO_X_OBSERVABILITY 开启导出器自观测distribution 项目中 otlploggrpc 导出器实验特性全解析通过 OTEL_GO_X_OBSERVABILITY 开启导出器自观测 本文围绕科学计算上一篇TypeScript 从模块获取类型The Concise TypeScript Book 第 37 章的导出值与跨模块类型推断实战下一篇5步掌握Switch大气层系统从零到精通的完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考