科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇文章以 leetcode/biweekly/177/README.md 为骨架完整梳理力扣第 177 场双周赛Biweekly Contest 177的四道题Smallest Pair with Different Frequencies、Merge Close Characters、Minimum Operations to Make Array Parity Alternating与Sum of K-Digit Numbers in a Range。文章将逐题给出思考过程、正确性论证、Python / Java / C / Go 四语言实现与复杂度分析并结合当前 codeforces-go 仓库中对应的 Go 源码a/a.go、b/b.go、c/c.go、d/d.go与测试用例a/a_test.go 等做源码级佐证。读完本文你将掌握统计频次后的贪心选择栈模拟消除类问题奇偶交替的通用化建模以及贡献法 快速幂 模逆元四类高频竞赛技巧。赛题总览本场双周赛的四道题由易到难恰好覆盖了算法竞赛中四类最常用的思维工具题号题目核心核心算法时间复杂度Q1找出现次数不同且值最小的数对哈希表计数 贪心O(n)Q2按间隔规则合并/消除靠近字符栈模拟 位置记录O(n)Q3用最少操作把数组改成奇偶交替贪心 分类讨论O(n)Q4求 k 位数区间内所有数字之和贡献法 快速幂 逆元O(log k)仓库中每题均配有独立的说明文档a/、b/、c/、d/目录下的 README.md、Go 实现*.go与测试文件*_test.go测试由 copypasta/template/leetcode/generator_test.go 生成的骨架驱动通过testutil.RunLeetCodeFuncWithFile配合题目的输入输出样例文件如a.txt自动校验。Q1Smallest Pair with Different Frequencies —— 频次不同的最小数对题意与无解判断题目要求在数组中找出两个数x y且x与y在数组中的出现次数频次不同。若所有数的出现次数都相同则无解。无解的判定如果nums中每个数的出现次数都一样那么任意两个数的频次都相等直接返回[-1, -1]。贪心构造为什么取全局最小值为 x 一定最优核心观察来自 a/README.md只要有任意两个出现次数不同的元素把全局最小值min(nums)作为x即可满足条件。因为x是最小值任何另一个出现次数不同的数必然大于x题目要求的x y自动成立。对于y只需在nums中选出出现次数不等于x的出现次数的最小元素即可。这样既保证了x y构造上天然成立又让(x, y)在满足条件的所有数对中字典序最小。统计出现次数用哈希表或用数组当值域较小时即可。四语言实现Python 版核心逻辑Counter 统计 生成器筛选class Solution: def minDistinctFreqPair(self, nums: List[int]) - List[int]: cnt Counter(nums) mn min(nums) cnt_min cnt[mn] min_y min((y for y, c in cnt.items() if c ! cnt_min), defaultNone) if min_y is None: return [-1, -1] return [mn, min_y]Go 版与仓库 a/a.go 一致注意minY math.MaxInt作为不存在的哨兵func minDistinctFreqPair(nums []int) []int { cnt : map[int]int{} mn : math.MaxInt for _, x : range nums { cnt[x] mn min(mn, x) } cntMin : cnt[mn] minY : math.MaxInt for y, c : range cnt { if c ! cntMin { minY min(minY, y) } } if minY math.MaxInt { return []int{-1, -1} } return []int{mn, minY} }复杂度时间复杂度O(n)其中 n 是nums的长度。空间复杂度O(n)哈希表开销。仓库中对应的测试入口位于 a/a_test.go样例数据见a.txt可直接go test ./leetcode/biweekly/177/a/验证。Q2Merge Close Characters —— 栈模拟的靠近字符合并问题模型这不是真正的消除本题的合并/消除规则与力扣常见的邻项消除问题如 1047 删除字符串中的所有相邻重复项思路同源但判定条件改为新遍历到的字符下标与它在栈保留串中最后一次出现的最大下标之差 k 时才把该字符入栈否则忽略。详细推导见 b/README.md。用栈保存未被消除的字符时未被消除的字符都在栈中因此新遍历到的字符的下标就是栈的大小len(st)——这是本题建模的关键一步它把原始下标问题转化成了栈大小问题。判定式len(st) - last[ch] k其中last[ch]记录字符ch在栈中的最新位置。为了 O(1) 查询可以用长度 26 的数组或哈希表保存每个字符在栈中的最新下标。正确性直觉逐个字符扫描凡是离同类字符太近距离 ≤ k的字符都会被丢弃最终栈内保留下来的字符满足任意两个相同字符在保留串中的间距都严格大于 k。这是典型的在线贪心对每个字符只做一次入栈/丢弃决策无需回溯。实现细节初始值的选取Go 实现在仓库 b/b.go 中有一个值得注意的细节last数组初始化为-k-1保证首次遇到某个字母时len(ans)-last[i] k恒为 true从而必然入栈func mergeCharacters(s string, k int) string { last : [26]int{} for i : range last { last[i] -k - 1 // 保证首次遇到字母 i 时len(ans)-last[i] k 是 true } ans : []byte{} for _, ch : range s { // ch 在 ans 中的下标是 len(ans) if len(ans)-last[ch-a] k { last[ch-a] len(ans) ans append(ans, byte(ch)) } } return string(ans) }Python/Java/C 版本则使用-inf或Integer.MIN_VALUE / 2、INT_MIN / 2作为初始哨兵效果相同。注意 Java/C/Go 中使用MIN_VALUE / 2而非MIN_VALUE是为了避免后续减法运算溢出。复杂度时间复杂度O(n)使用定长 26 数组或 O(n |Σ|)其中 |Σ| 26 是字符集大小创建数组本身需要 O(|Σ|) 时间。空间复杂度O(|Σ|)返回值不计入。顺带一提仓库 b/4019/README.md 注明本题与力扣第 3853 题合并靠近字符完全相同属于同一道题的换壳复现值得在题单中互相参照。Q3Minimum Operations to Make Array Parity Alternating —— 奇偶交替的最小操作数与极差两种目标奇偶模式要把nums变成奇偶交替只可能对应两种全局模式偶奇偶奇偶奇……奇偶奇偶奇偶……因此可以枚举这两种情况分别计算再取最优详见 c/README.md。核心贪心事实每个元素至多操作一次遍历过程中若nums[i]的奇偶性不等于目标奇偶性则操作一次1或-1后其奇偶性必定反转从而必然等于目标奇偶性。因此每个元素要么不操作要么恰好操作一次不需要考虑多次操作。通用做法 vs 特殊做法文档给出了两条路线通用做法可迁移到 632. 最小区间对每个x nums[i]不操作视作列表[x]操作视作列表[x-1, x1]于是得到 n 个列表问题等价于找一个最短的值域范围[a, b]覆盖每个列表中的至少一个数——这正是 632. 最小区间 的模型可排序后滑动窗口求解。针对本题的特殊做法O(n) 贪心设全局最小值gMin min(nums)、全局最大值gMax max(nums)分类讨论修改策略若n 1无需修改返回[0, 0]。若gMin gMax规定要修改的数统一加一则最终极差为 1若有的加一有的减一极差会变成 2不优。若gMin 1 gMax等于gMin的数加一等于gMax的数减一最终极差为 1。若gMin 1 gMax等于gMin的加一、等于gMax的减一区间[gMin1, gMax-1]内的中间值保持不动即可因为它们总可以落在新的最小最大值之间不影响极差n ≥ 2 的奇偶交替数组极差天然至少为 1。结论对需要修改的数等于gMin则加一等于gMax则减一其余情况不修改。奇偶性判定的位运算技巧对目标模式target0 表示以偶开头1 表示以奇开头位置i上应有的奇偶性是target ^ (i % 2)。代码中统一使用等价写法if (x-i)1 ! target { // 等价于 x1 ! target ^ i%2 op ... }这一写法避免了在每个位置重新计算target ^ i%2同时保持逻辑完全等价。仓库实现见 c/c.go。Go 实现双模式枚举 极差兜底func makeParityAlternating(nums []int) []int { if len(nums) 1 { return []int{0, 0} } gMin : slices.Min(nums) gMax : slices.Max(nums) f : func(target int) (int, int) { op, mn, mx : 0, math.MaxInt, math.MinInt for i, x : range nums { if (x-i)1 ! target { // 等价于 x1 ! target ^ i%2 op if x gMin { x } else if x gMax { x-- } } mn min(mn, x) mx max(mx, x) } return op, max(mx-mn, 1) // 在 n 2 的情况下极差至少是 1 } op1, minD1 : f(0) op2, minD2 : f(1) if op1 op2 || op1 op2 minD1 minD2 { return []int{op1, minD1} } return []int{op2, minD2} }注意两点工程细节一是返回max(mx-mn, 1)对极差做兜底n ≥ 2 时奇偶交替数组极差至少为 1二是两个模式都算完后优先比较操作数操作数相同再比较极差Go 代码op1 op2 || op1 op2 minD1 minD2的短路语义即表达这一规则。复杂度时间复杂度O(n)。空间复杂度O(1)。Q4Sum of K-Digit Numbers in a Range —— 贡献法 快速幂 模逆元贡献法把数位之和拆成每一位的贡献这是全场比赛最有思维含量的一题推导过程见 d/README.md。核心思路是贡献法答案本质上是一堆数字相加其中大量数字是重复的可以按位统计每个数位值出现了多少次从而算出它对总和的贡献。以k 3三位数、ℓ 2、r 5为例当十位数填 5 时百位数有r - ℓ 1 4种填法个位数也有 4 种填法共4² 16个三位数的十位是 5。由于456 400 50 6十位上的 5 实际代表 50这 50 在 16 个不同的三位数中出现因此十位填 5 的贡献是50 × 16 800。一般化公式推导一般地在从低到高第i位i 从 0 开始上填xℓ ≤ x ≤ r相当于填了x·10^i。其余k-1位每位都有m r - ℓ 1种填法共m^(k-1)种填法因此x对答案的贡献为x · 10^i · (r - ℓ 1)^(k-1)枚举x与i并求和利用等差数列求和Σx与等比数列求和Σ10^i可将双层枚举化简为闭式(ℓ r)·m / 2 · (10^k − 1) / 9 · m^(k−1)其中(ℓ r)·m / 2来自等差数列求和(10^k − 1) / 9 1 10 ... 10^(k−1)来自等比数列求和。模运算三件套快速幂、除法转逆元、负数修正由于答案可能非常大需要在模1_000_000_007下计算此时10^k与m^(k−1)需要快速幂倍增法O(log k)除以2与除以9必须换成乘对应的模逆元2 的逆元与9 的逆元。由于18 2 × 9代码里直接乘pow(18, MOD-2)费马小定理求逆元一步到位pow(10, k) - 1在取模后可能为负数需要 MOD修正。仓库 Go 实现 d/d.goconst mod 1_000_000_007 func pow(x, n int) int { res : 1 for ; n 0; n / 2 { if n%2 0 { res res * x % mod } x x * x % mod } return res } func sumOfNumbers(l, r, k int) int { m : r - l 1 return (l r) * m * (pow(10, k) - 1 mod) % mod * pow(18, mod-2) % mod * pow(m, k-1) % mod }Python 版更简洁用内置pow(x, n, MOD)与pow(18, -1, MOD)直接求逆元class Solution: def sumOfNumbers(self, l: int, r: int, k: int) - int: MOD 1_000_000_007 m r - l 1 return (l r) * m * (pow(10, k, MOD) - 1) * pow(18, -1, MOD) * pow(m, k - 1, MOD) % MOD复杂度时间复杂度O(log k)快速幂主导。空间复杂度O(1)。总结四题串起的四条方法论Q1演示了先保证构造可行性取最小值让 x y 自动成立再做局部最优选择的贪心模板Q2演示了栈模拟消除类问题的通用建模用len(st)代表当前新字符的下标配一个last[]数组做 O(1) 的最近位置查询Q3演示了奇偶交替类问题的两种处理层级通用化转化为最小区间覆盖模型可迁移到 632 题以及针对本题的 O(1) 空间的分类讨论贪心Q4演示了贡献法的完整闭环按位拆贡献 → 等差数列/等比数列求和化简 → 快速幂 模逆元落地。如果你想进一步巩固这些技巧仓库中 leetcode/biweekly/177/a/README.md、leetcode/biweekly/177/b/README.md、leetcode/biweekly/177/c/README.md、leetcode/biweekly/177/d/README.md 保留了逐题的完整推导而各目录下的a.go/b.go/c.go/d.go与其*_test.go例如 a/a_test.go构成了题解即代码、代码即测试的可复现闭环——在仓库根目录执行go test ./leetcode/biweekly/177/...即可一键跑通本场全部样例作为日常刷题与复盘的标准入口。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐力扣双周赛 159 Q1 题解奇偶交替的最小相邻交换次数——codeforces-go 仓库源码解析力扣双周赛 159 Q1 题解奇偶交替的最小相邻交换次数——codeforces go 仓库源码解析 导读 本文基于 codeforces go 仓库中 双周科学计算codeforces-go 仓库实战力扣双周赛 104「英雄的力量」贡献法递推题解全解析codeforces go 仓库实战力扣双周赛 104「英雄的力量」贡献法递推题解全解析 导读 本篇技术指南以仓库中 双周赛 104 第四题题解 https:科学计算力扣双周赛 134 题解交替组计数、贪心取点与 AND 值为 k 的子数组枚举codeforces-go 仓库配套实现力扣双周赛 134 题解交替组计数、贪心取点与 AND 值为 k 的子数组枚举codeforces go 仓库配套实现 本篇文章以 leetcode/bi科学计算上一篇NocoBase 数据可视化上下文变量ctx使用指南按用户、页面与筛选条件动态渲染图表下一篇暗黑破坏神2存档编辑器零基础打造完美游戏体验的终极工具创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考