科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本文是算法竞赛模板库 codeforces-go 对 LeetCode 第 121 场双周赛第三题minimum-number-of-operations-to-make-x-and-y-equal使 X 和 Y 相等的最少操作数的完整技术解析。全文以仓库 leetcode/biweekly/121/c/README.md 题解为主体结合仓库中同目录的 Go 实现、测试数据与 testutil 自动化测试框架分别讲解图论建模 BFS 与记忆化搜索两种解法并给出 Python / Java / C / Go 四语言可运行代码与复杂度推导。读完本文你将掌握「带除法操作的加减最短路问题」的两类标准建模思路以及此类题目在仓库中从题解文档到自动验证测试的完整工程化落地方式。题目背景与操作规则本题来自 2024 年 1 月举行的第 121 场双周赛第三题题号为 2998题目名为minimum-number-of-operations-to-make-x-and-y-equal。从题解代码可以确认问题的操作集合为对当前数x每次操作可以执行x 1加一执行x - 1减一当x是 5 的倍数时执行x / 5除以 5当x是 11 的倍数时执行x / 11除以 11。目标是从给定的x出发通过上述操作的最少次数到达y。题解给出了两条截然不同的思考路径方法一把每个数看成图上的节点每种操作看成一条边跑 BFS 求最短路方法二基于「除法操作能成规模缩小问题」这一观察设计带记忆化的递归搜索复杂度可从O(x)降到O(log²(x/y))。方法一BFS 最短路建模核心思想把操作看成连边题解的第一句话就点明了本质每个操作都可以理解成从x向操作后的数连边。于是整个问题被抽象为一张无限图节点是整数1、-1、/5、/11分别是从当前节点出发的四类有向边后两者仅在整除时存在。题目所求的「最少操作次数」就是图中从x到y的最短路长度而所有边权都为 1因此 BFS 天然是最短路的最优算法——第一次从队列中弹出y时步数即为答案。关键剪枝x y时无需 BFS题解特别指出如果x y那么只能使用加一操作。原因很直接-1、/5、/11三种操作都会让数变小只会使x与y的差距进一步拉大因此唯一可行的路径就是一步步加一操作次数直接等于y - x。if x y: return y - x双数组 BFS 与三个实现细节题解代码采用「双数组」实现 BFS交替使用两个队列取代标准 BFS 中常用的队列 距离数组并做了三处值得注意的优化答案上界ans x - y既然只用减一操作x - y步一定能到达y这为搜索提供了一个当前已知最好的上界BFS 过程中一旦发现更优的步数就更新它最终min(ans, step)即答案。vis数组的规模上界x ans 1由于1操作至多执行x - y次若加一超过这个次数直接减一回到y反而更优所以 BFS 过程中涉及的最大数不会超过x (x - y)据此给vis数组分配容量避免了对无限整数域做哈希或超大数组的开销。add函数的提前收束当某个待加入的节点v y时不再把它入队展开而是直接假设后续只能加一用step 1 y - v更新答案——此时step是当前层数1是从v走到y方向的第一步加一y - v是剩余加一步数。这本质上是一种边界触底直接结算的剪枝大幅减少了无效状态的展开。四语言实现class Solution: def minimumOperationsToMakeEqual(self, x: int, y: int) - int: if x y: return y - x ans x - y # 总操作次数不会超过 x-y vis [False] * (x ans 1) # 1 操作至多执行 x-y 次 q [] step 0 def add(v: int) - None: if v y: nonlocal ans ans min(ans, step 1 y - v) # 只能执行 1 操作 elif not vis[v]: vis[v] True q.append(v) add(x) while True: tmp q q [] for v in tmp: if v y: return min(ans, step) if v % 11 0: add(v // 11) if v % 5 0: add(v // 5) add(v - 1) add(v 1) step 1class Solution { public int minimumOperationsToMakeEqual(int x, int y) { if (x y) { return y - x; } int ans x - y; // 总操作次数不会超过 x-y boolean[] vis new boolean[x ans 1]; // 1 操作至多执行 x-y 次 vis[x] true; ListInteger q List.of(x); int step 0; while (true) { ListInteger tmp q; q new ArrayList(); for (int v : tmp) { if (v y) { return Math.min(ans, step); } if (v y) { ans Math.min(ans, step y - v); continue; } if (v % 11 0 !vis[v / 11]) { vis[v / 11] true; q.add(v / 11); } if (v % 5 0 !vis[v / 5]) { vis[v / 5] true; q.add(v / 5); } if (!vis[v - 1]) { vis[v - 1] true; q.add(v - 1); } if (!vis[v 1]) { vis[v 1] true; q.add(v 1); } } step; } } }class Solution { public: int minimumOperationsToMakeEqual(int x, int y) { if (x y) { return y - x; } int ans x - y; // 总操作次数不会超过 x-y vectorint vis(x ans 1); // 1 操作至多执行 x-y 次 vectorint q; int step 0; auto add { if (v y) { ans min(ans, step 1 y - v); // 只能执行 1 操作 } else if (!vis[v]) { vis[v] true; q.push_back(v); } }; add(x); while (true) { auto tmp move(q); // move 后 q 为空 for (int v : tmp) { if (v y) { return min(ans, step); } if (v % 11 0) { add(v / 11); } if (v % 5 0) { add(v / 5); } add(v - 1); add(v 1); } step; } } };func minimumOperationsToMakeEqual(x, y int) int { if x y { return y - x } ans : x - y // 总操作次数不会超过 x-y vis : make([]bool, xans1) // 1 操作至多执行 x-y 次 q : []int{} step : 0 add : func(v int) { if v y { ans min(ans, step1y-v) // 只能执行 1 操作 } else if !vis[v] { vis[v] true q append(q, v) } } add(x) for { tmp : q q nil for _, v : range tmp { if v y { return min(ans, step) } if v%11 0 { add(v / 11) } if v%5 0 { add(v / 5) } add(v - 1) add(v 1) } step } }复杂度分析时间复杂度O(x)。vis数组长度为x (x - y) 1每个元素至多被访问一次因此 BFS 展开的状态总数是O(x)的。空间复杂度O(x)。主要为vis布尔数组的开销。方法二记忆化搜索状态转移推导为什么可以只考虑最近的倍数BFS 虽然直观但O(x)的复杂度在面对较大输入时仍有压力。方法二观察到除法是唯一能把数打小的操作而且只要到达一个能被 5 或 11 整除的数就可以执行一次除法让问题规模锐减。设f(x)表示从x到y的最少操作数题解先枚举了x y时的全部可能性只用减一操作代价是x - y通过若干次减一到达最近的小于等于x的 11 的倍数x x - x mod 11再除以 11问题变成f(x / 11) f(x / 11)总代价x mod 11 1 f(x / 11)。题解特别论证了无需再往下减继续减到x - 11再除以 11等价于先把x除以 11 再减一——两者到达同一个数但后者操作次数更小因此到达x后应立即除 11不再继续减通过若干次加一到达最近的大于x的 11 的倍数x x 11 - x mod 11再除以 11代价11 - x mod 11 1 f(x / 11 1)同理对除数 5 有两条对称转移x mod 5 1 f(x / 5)与5 - x mod 5 1 f(x / 5 1)。取上述所有方式的最小值即f(x) min( x - y, f(x/11) x%11 1, f(x/111) 11 - x%11 1, f(x/5) x%5 1, f(x/51) 5 - x%5 1 )而x y时只剩加一操作直接返回y - x递归出口。四语言实现class Solution: cache def minimumOperationsToMakeEqual(self, x: int, y: int) - int: if x y: return y - x return min(x - y, self.minimumOperationsToMakeEqual(x // 11, y) x % 11 1, self.minimumOperationsToMakeEqual(x // 11 1, y) 11 - x % 11 1, self.minimumOperationsToMakeEqual(x // 5, y) x % 5 1, self.minimumOperationsToMakeEqual(x // 5 1, y) 5 - x % 5 1)class Solution { private final MapInteger, Integer memo new HashMap(); public int minimumOperationsToMakeEqual(int x, int y) { if (x y) { return y - x; } if (memo.containsKey(x)) { return memo.get(x); } int ans x - y; ans Math.min(ans, minimumOperationsToMakeEqual(x / 11, y) x % 11 1); ans Math.min(ans, minimumOperationsToMakeEqual(x / 11 1, y) 11 - x % 11 1); ans Math.min(ans, minimumOperationsToMakeEqual(x / 5, y) x % 5 1); ans Math.min(ans, minimumOperationsToMakeEqual(x / 5 1, y) 5 - x % 5 1); memo.put(x, ans); return ans; } }class Solution { unordered_mapint, int memo; public: int minimumOperationsToMakeEqual(int x, int y) { if (x y) { return y - x; } auto it memo.find(x); if (it ! memo.end()) { return it-second; } return memo[x] min({x - y, minimumOperationsToMakeEqual(x / 11, y) x % 11 1, minimumOperationsToMakeEqual(x / 11 1, y) 11 - x % 11 1, minimumOperationsToMakeEqual(x / 5, y) x % 5 1, minimumOperationsToMakeEqual(x / 5 1, y) 5 - x % 5 1}); } };func minimumOperationsToMakeEqual(x, y int) int { memo : map[int]int{} var dfs func(int) int dfs func(x int) int { if x y { return y - x } if v, ok : memo[x]; ok { return v } res : min(x-y, dfs(x/11)x%111, dfs(x/111)11-x%111, dfs(x/5)x%51, dfs(x/51)5-x%51) memo[x] res return res } return dfs(x) }复杂度分析O(log²(x/y))题解给出了严谨的规模推导由于除法对x的影响远大于加减可以认为每次递归都把x的规模变成x/5与x/11两个分支当x y时递归终止。因此从x到y的过程中x的规模会变成x / (5^p * 11^q)其中指数p与q各有O(log(x/y))个取值组合起来的状态个数为O(log²(x/y))。时间复杂度O(log²(x/y))。动态规划的时间复杂度等于「状态个数 × 单个状态的计算时间」状态个数为O(log²(x/y))单个状态只做常数次min比较与取模运算故总复杂度为O(log²(x/y))。空间复杂度O(log²(x/y))。保存每个状态所需的空间等于状态个数记忆化哈希表 /cache缓存。对比方法一的O(x)方法二在x远大于y的场景下优势显著这也是它成为本题更优解的原因。仓库工程化实践Go 实现与自动化测试提交版 Go 核心实现仓库中的 c.go 正是方法二的 Go 版本与题解文档中的sol-Go代码完全一致以memo哈希表 闭包dfs实现记忆化代码量极短且与题解一一对应是题解文档 ↔ 提交代码同步维护的典型范例。反射驱动的测试框架testutil 测试目录 中的测试文件是Code generated by copypasta/template/leetcode/generator_test.go生成的核心调用为if err : testutil.RunLeetCodeFuncWithFile(t, minimumOperationsToMakeEqual, c.txt, 0); err ! nil { t.Fatal(err) }其中RunLeetCodeFuncWithFile定义在 leetcode/testutil/leetcode.go它按「函数参数个数 返回值个数」为一组从c.txt中逐组切分输入输出再借助反射reflect.TypeOf(f)、fValue.Call(ins)自动完成参数解析、调用与结果比对同时支持-1指定最后一个用例、targetCaseNum定向运行单个用例等功能。测试数据文件 c.txt 中保存了本题的全部官方样例如26 1 - 3、54 2 - 4、25 30 - 5每组输入输出占一行中间以空行分隔在仓库根目录执行go test ./leetcode/biweekly/121/c/即可一键验证实现。题解文档的生成与维护链路从源码结构看c_test.go的生成依赖 copypasta/template/leetcode/generator.go 中的GenLeetCodeTests系列函数它登录力扣国服账号后拉取指定场次contestTag如biweekly-contest-121的题目信息解析题目 HTML 中的 Go 默认代码与 Input/Output 样例然后批量生成a.go/b.go/c.go的实现文件、*_test.go测试文件与*.txt测试数据。README 题解文档中的sol-Go代码则与生成出的c.go保持一致形成「题解 → 代码 → 测试数据 → 自动验证」的闭环这正是本仓库把每道 LeetCode 题目沉淀为可复现工程资产的方式。相似题目与延伸思考题解文档在文末给出了两类思路的进阶训练方向**方法一图建模 BFS**的延伸题转化数字的最小运算数minimum-operations-to-convert-number力扣难度分 1850。该题同样是给定一组运算、求从起点到目标的最少运算数建模方式与本题方法一几乎同构适合巩固 BFS 最短路的思维**方法二除法缩规模 记忆化搜索**的延伸题吃掉 N 个橘子的最少天数minimum-number-of-days-to-eat-n-oranges力扣难度分 2048。该题同样具备只有除法能大幅缩小规模的结构其自顶向下搜索 记忆化的写法与本题方法二一脉相承。两类题目共同揭示了一个可迁移的解题模式当操作集中存在整除类操作时优先考虑对倍数附近的状态做跳转跳到最近的倍数再除配合记忆化即可把线性复杂度压到对数级而当状态空间可预测、规模可控时图建模 BFS 则是最通用、最不容易出错的兜底方案。结合仓库 leetcode/SOLUTIONS.md 中按题单分类整理的全部题解可以系统地完成从单个题型到解题套路的进阶。总结本文以 codeforces-go 仓库对第 121 场双周赛第三题的题解文档为骨架完整还原了两种解法BFS 将每个操作视为图上的一条边用双数组队列求最短路并以x - y为上界做剪枝复杂度O(x)记忆化搜索则利用除法对规模的指数级压缩只在 5/11 的最近倍数处做跳转把复杂度优化到O(log²(x/y))。与此同时仓库以 c.go、c_test.go、c.txt 与 testutil 反射测试框架为这道题沉淀了一套可一键验证的工程化闭环。掌握这两种建模方式与复杂度论证手法即可从容应对同类运算集合 最少步数问题。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 题解LeetCode 第 112 场双周赛「通过操作使字符串相等 II」的奇偶分组计数法codeforces go 题解LeetCode 第 112 场双周赛「通过操作使字符串相等 II」的奇偶分组计数法 本篇以 codeforces go 仓库科学计算codeforces-go 题解精讲LeetCode 双周赛 122 第三题 Minimum Length of Array Using Operations 的取模操作推演与最短化证明codeforces go 题解精讲LeetCode 双周赛 122 第三题 Minimum Length of Array Using Operations科学计算购买水果的最少金币记忆化搜索、递推与单调队列优化全解析LeetCode 118 场双周赛 T3 · codeforces-go 题解购买水果的最少金币记忆化搜索、递推与单调队列优化全解析LeetCode 118 场双周赛 T3 · codeforces go 题解 本文以 codefo科学计算上一篇CANN ops-math 中 NotEqual 不相等比较算子实战指南从 aclnn 接口调用到 NPU 内核实现下一篇HowToCook 菜谱实战蒜蓉西兰花的焯水火候与蒜蓉汁浇淋全流程解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
