科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文以 codeforces-go 仓库中 leetcode/biweekly/104/c/README.md 的官方题解为主体完整拆解 LeetCode 2680Biweekly Contest 104 第三题「最大或值」的两种核心做法前后缀分解与基于「枚举右维护左」思想的 O(1) 空间位运算优化。你将掌握如何通过位运算性质推导贪心结论、用前后缀 OR 在 O(1) 时间内替换任一元素以及如何用allOr ^ x | fixed的技巧把空间复杂度压到 O(1)。仓库中 c.go、c_test.go 提供了可直接运行的实现与测试可帮助你边读边验证。题目回顾给你一个下标从 0 开始的整数数组nums和一个整数k。一次操作中你可以选择nums中任意一个元素将它乘以 2。请你执行恰好 k 次操作即可以对同一个元素重复操作并返回执行完所有操作后nums中**所有元素按位或OR**的最大可能值。关键约束k次操作可以全部作用于同一个数因此所有操作的净效果等价于把某一个元素nums[i]左移k位。问题转化为选择下标i计算nums[0] | ... | nums[i-1] | (nums[i] k) | nums[i1] | ... | nums[n-1]的最大值。方法一前后缀分解推导为什么「只修改一个数」是最优的提示 1要让答案最大首先应当最大化答案的二进制长度。OR 运算结果的二进制长度越长数值越大。提示 2把「乘 2」即左移 1 位分配给多个数雨露均沾不如只分配给一个数这样能得到更长更大的答案。证明反证法假设最优解中答案的长度与修改后的某个nums[i]一样长并且我们还修改了其他的数。那么把其他数上的「乘 2」全部转移到nums[i]上nums[i]会得到更长的二进制表示从而整个 OR 的结果也更长与「答案的长度已经是最大」矛盾。因此最优做法必然是只修改一个数。提示 3枚举把nums[i]乘 k 次 2即左移 k 次。修改后如何计算所有元素的 OR 值参考「238. 除自身以外数组的乘积」的前缀/后缀预处理思路预处理每个nums[i]左侧元素的 OR 值pre以及右侧元素的 OR 值suf从而O(1)得到把nums[i]左移 k 位后所有元素的 OR答案 pre[i] | (nums[i] k) | suf[i]代码实现时只需预处理右侧元素的 OR 值后缀或左侧元素的 OR 值前缀或可以一边遍历nums一边累积计算。多语言实现class Solution: def maximumOr(self, nums: List[int], k: int) - int: n len(nums) # suf[i] 表示 nums[i1:] 的 OR suf [0] * n for i in range(n - 2, -1, -1): suf[i] suf[i 1] | nums[i 1] # pre 表示 nums[:i] 的 OR ans pre 0 for x, suf_or in zip(nums, suf): ans max(ans, pre | (x k) | suf_or) pre | x return ansclass Solution { public long maximumOr(int[] nums, int k) { int n nums.length; // suf[i] 表示 nums[i1] 到 nums[n-1] 的 OR int[] suf new int[n]; for (int i n - 2; i 0; i--) { suf[i] suf[i 1] | nums[i 1]; } long ans 0; // pre 表示 nums[0] 到 nums[i-1] 的 OR int pre 0; for (int i 0; i n; i) { ans Math.max(ans, pre | ((long) nums[i] k) | suf[i]); pre | nums[i]; } return ans; } }class Solution { public: long long maximumOr(vectorint nums, int k) { int n nums.size(); // suf[i] 表示 nums[i1] 到 nums[n-1] 的 OR vectorint suf(n); for (int i n - 2; i 0; i--) { suf[i] suf[i 1] | nums[i 1]; } long long ans 0; // pre 表示 nums[0] 到 nums[i-1] 的 OR int pre 0; for (int i 0; i n; i) { ans max(ans, pre | ((long long) nums[i] k) | suf[i]); pre | nums[i]; } return ans; } };#define MAX(a, b) ((b) (a) ? (b) : (a)) long long maximumOr(int* nums, int numsSize, int k) { // suf[i] 表示 nums[i1] 到 nums[n-1] 的 OR int* suf malloc(numsSize * sizeof(int)); suf[numsSize - 1] 0; for (int i numsSize - 2; i 0; i--) { suf[i] suf[i 1] | nums[i 1]; } long long ans 0; // pre 表示 nums[0] 到 nums[i-1] 的 OR int pre 0; for (int i 0; i numsSize; i) { int x nums[i]; ans MAX(ans, pre | ((long long) x k) | suf[i]); pre | x; } free(suf); return ans; }func maximumOr(nums []int, k int) int64 { n : len(nums) // suf[i] 表示 nums[i1] 到 nums[n-1] 的 OR suf : make([]int, n) for i : n - 2; i 0; i-- { suf[i] suf[i1] | nums[i1] } // pre 表示 nums[0] 到 nums[i-1] 的 OR ans, pre : 0, 0 for i, x : range nums { ans max(ans, pre|xk|suf[i]) pre | x } return int64(ans) }var maximumOr function(nums, k) { const n nums.length; // suf[i] 表示 nums[i1] 到 nums[n-1] 的 OR const suf Array(n); suf[n - 1] 0; for (let i n - 2; i 0; i--) { suf[i] suf[i 1] | nums[i 1]; } // pre 表示 nums[0] 到 nums[i-1] 的 OR let ans 0n, pre 0n; for (let i 0; i n; i) { const x BigInt(nums[i]); const res pre | (x BigInt(k)) | BigInt(suf[i]); ans res ans ? res : ans; pre | x; } return Number(ans); };impl Solution { pub fn maximum_or(nums: Veci32, k: i32) - i64 { let n nums.len(); // suf[i] 表示 nums[i1] 到 nums[n-1] 的 OR let mut suf vec![0; n]; for i in (0..n - 1).rev() { suf[i] suf[i 1] | nums[i 1]; } let mut ans 0; // pre 表示 nums[0] 到 nums[i-1] 的 OR let mut pre 0; for (x, suf_or) in nums.into_iter().zip(suf) { ans ans.max(pre | ((x as i64) k) | suf_or as i64); pre | x as i64; } ans } }实现要点suf[i]记录的是「下标 i1 到末尾」的 OR递推式suf[i] suf[i1] | nums[i1]从右往左构建pre是滚动变量表示「下标 0 到 i-1」的 OR每次遍历到i时先参与计算再累加nums[i]Go / C / C / Java / Rust 中x k需先转为long/long long再参与运算避免int溢出例如k最大可接近 32nums[i]左移后会超过 32 位有符号整数范围JavaScript 全程使用BigInt规避精度问题。复杂度分析时间复杂度O(n)其中 n 为nums的长度后缀预处理一次、正序枚举一次。空间复杂度O(n)需要存储长度为 n 的suf数组。方法二O(1) 空间优化方法一的空间开销来自后缀数组。能否只通过全体 OR 值直接算出「去掉某个 x 之后其余 n-1 个数的 OR」可以核心技巧如下。设nums所有数的 OR 为allOr。方法一求的其实就是(去掉 x 后其余数的 OR) | (x k)。推导(allOr ^ x) | fixed先通过异或运算直接去掉 x即allOr ^ x。但这不一定正确如果其他数在x占用的某些比特位上也是 1异或会把它们一并抹掉需要把这种 1 重新加回来。如果有多个nums[i]在同一个比特位上都是 1那么无论去掉哪一个 x其余 n-1 个数的 OR 在该比特位上恒为 1。用二进制数fixed记录这些「恒为 1」的比特位。于是去掉 x 后其余 n-1 个数的 OR 等于(allOr ^ x) | fixed先直接去掉allOr中的 x再用fixed修正被误删的公共 1。如何计算 fixed「枚举右维护左」在遍历nums的过程中allOr x中出现的 1必然在此之前已经出现过一次因为allOr是之前所有数的 OR说明该比特位至少在两个数上都是 1将其 OR 到fixed中即可fixed | allOr x // 在更新 allOr 之前记录公共的 1 allOr | x // 更新所有数的 OR最后遍历nums对每个 x 计算(allOr ^ x) | fixed | (x k)取最大值。多语言实现class Solution: def maximumOr(self, nums: List[int], k: int) - int: all_or fixed 0 for x in nums: # 如果在计算 all_or | x 之前all_or 和 x 有公共的 1 # 那就意味着有多个 nums[i] 在这些比特位上都是 1 fixed | all_or x # 把公共的 1 记录到 fixed 中 all_or | x # 所有数的 OR return max((all_or ^ x) | fixed | (x k) for x in nums)class Solution { public long maximumOr(int[] nums, int k) { int allOr 0; int fixed 0; for (int x : nums) { // 如果在计算 allOr | x 之前allOr 和 x 有公共的 1 // 那就意味着有多个 nums[i] 在这些比特位上都是 1 fixed | allOr x; // 把公共的 1 记录到 fixed 中 allOr | x; // 所有数的 OR } long ans 0; for (int x : nums) { ans Math.max(ans, (allOr ^ x) | fixed | ((long) x k)); } return ans; } }class Solution { public: long long maximumOr(vectorint nums, int k) { int all_or 0, fixed 0; for (int x : nums) { // 如果在计算 all_or | x 之前all_or 和 x 有公共的 1 // 那就意味着有多个 nums[i] 在这些比特位上都是 1 fixed | all_or x; // 把公共的 1 记录到 fixed 中 all_or | x; // 所有数的 OR } long long ans 0; for (int x : nums) { ans max(ans, (all_or ^ x) | fixed | ((long long) x k)); } return ans; } };#define MAX(a, b) ((b) (a) ? (b) : (a)) long long maximumOr(int* nums, int numsSize, int k) { int all_or 0, fixed 0; for (int i 0; i numsSize; i) { int x nums[i]; // 如果在计算 all_or | x 之前all_or 和 x 有公共的 1 // 那就意味着有多个 nums[i] 在这些比特位上都是 1 fixed | all_or x; // 把公共的 1 记录到 fixed 中 all_or | x; // 所有数的 OR } long long ans 0; for (int i 0; i numsSize; i) { int x nums[i]; ans MAX(ans, (all_or ^ x) | fixed | ((long long) x k)); } return ans; }func maximumOr(nums []int, k int) int64 { allOr, fixed : 0, 0 for _, x : range nums { // 如果在计算 allOr | x 之前allOr 和 x 有公共的 1 // 那就意味着有多个 nums[i] 在这些比特位上都是 1 fixed | allOr x // 把公共的 1 记录到 fixed 中 allOr | x // 所有数的 OR } ans : 0 for _, x : range nums { ans max(ans, (allOr^x)|fixed|xk) } return int64(ans) }var maximumOr function(nums, k) { let allOr 0, fixed 0; for (const x of nums) { // 如果在计算 allOr | x 之前allOr 和 x 有公共的 1 // 那就意味着有多个 nums[i] 在这些比特位上都是 1 fixed | allOr x; // 把公共的 1 记录到 fixed 中 allOr | x; // 所有数的 OR } let ans 0n; for (const x of nums) { const res (BigInt(allOr ^ x) | BigInt(fixed) | (BigInt(x) BigInt(k))); ans res ans ? res : ans; } return Number(ans); };impl Solution { pub fn maximum_or(nums: Veci32, k: i32) - i64 { let mut all_or 0; let mut fixed 0; for x in nums { // 如果在计算 all_or | x 之前all_or 和 x 有公共的 1 // 那就意味着有多个 nums[i] 在这些比特位上都是 1 fixed | all_or x; // 把公共的 1 记录到 fixed 中 all_or | x; // 所有数的 OR } nums.into_iter() .map(|x| (all_or ^ x) as i64 | fixed as i64 | ((x as i64) k)) .max() .unwrap() } }复杂度分析时间复杂度O(n)统计allOr/fixed一遍求答案一遍。空间复杂度O(1)只使用两个整数变量完全无需额外数组。仓库源码印证两种实现并存测试双保险在 codeforces-go 仓库中这道题的 Go 实现同时保留了两种解法见 c.gomaximumOr方法二O(1) 空间位运算优化maximumOr2方法一前后缀分解构建suf后缀 OR 数组后一边累积pre一边取最大值。两者的结果一致正好互为对拍可用于验证两种思路在边界情况下如k很大、nums含 0、多个元素同一位为 1 等的输出完全相等。对应的测试文件 c_test.go 提供了两层验证func Test_c(t *testing.T) { targetCaseNum : 0 // -1 if err : testutil.RunLeetCodeFuncWithFile(t, maximumOr, c.txt, targetCaseNum); err ! nil { t.Fatal(err) } if err : testutil.RunFuncWithRandomInput(t, maximumOr); err ! nil { t.Fatal(err) } }第一层RunLeetCodeFuncWithFile读取 c.txt 中的固定样例逐条比对。c.txt中的数据格式为「每 3 行一组输入 nums、输入 k、期望输出」仓库中已收录的样例包括[12,9]、k1→30[8,1,2]、k2→35读取逻辑见 leetcode/testutil/leetcode.go 的RunLeetCodeFuncWithFile它按函数签名fNumIn fNumOut行一组把纯文本数据解析为用例再交给RunLeetCodeFuncWithExamples通过反射调用并逐组断言。第二层RunFuncWithRandomInput属于随机输入测试用随机生成的nums与k反复调用maximumOr用于发现手工样例难以覆盖的边界情况。运行方式在仓库根目录执行go test ./leetcode/biweekly/104/c -run Test_c -v思维拓展这类题与仓库内的知识点关联本题本质是「前后缀分解」在位运算场景下的典型应用可以迁移到一类经典问题需要快速求「删掉/修改某个元素后整个序列某种聚合值」的题目如除自身以外数组的乘积、前后缀最值等。仓库内还沉淀了相关位运算工具与笔记copypasta/bits.go 汇集了 AND/OR/XOR 的常用性质如和|的区间单调性、bits.Len与二进制长度的换算是理解本题「长度最大化」与fixed位运算推理的底层基础官方题解将本题归类到「专题前后缀分解」所属的动态规划题单见 leetcode/biweekly/104/c/README.md 末尾的分类题单同主题题目还包括滑动窗口与双指针、单调栈贡献法、拆位位运算、贪心与思维等——这些分类在仓库的 leetcode 目录下均有大量对应题解可供刷题对照。小结贪心结论k 次乘 2 等价于只把某一个数左移 k 位目标是最大化整个数组 OR 的二进制长度。方法一前后缀分解O(n) 时间、O(n) 空间思路直观是「除自身以外数组的乘积」技巧的位运算变体。方法二allOr ^ x | fixedO(n) 时间、O(1) 空间用「枚举右维护左」预处理所有「至少两个数共有的 1」再用异或去掉单个 x 并用 fixed 修正是面试中值得掌握的位运算优化套路。验证闭环仓库同时提供两种实现的 Go 源码c.go、固定样例c.txt与随机输入测试c_test.go可直接运行验证也可以作为后续同类题目的模板参考。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 实战精讲LeetCode 2657 前缀公共数组——用位运算集合表示法实现 O(n) 解法codeforces go 实战精讲LeetCode 2657 前缀公共数组——用位运算集合表示法实现 O n 解法 本篇文章以 codeforces go科学计算LeetCode 136 只出现一次的数字用异或运算实现 O(n) 时间 O(1) 空间解法LeetCode 136 只出现一次的数字用异或运算实现 O n 时间 O 1 空间解法 导读 LeetCode 136「只出现一次的数字」Single N文档教程知识库codeforces-go 题解LeetCode 双周赛 102「数组所有前缀的得分」—— 前缀最大值与得分累计的单遍扫描codeforces go 题解LeetCode 双周赛 102「数组所有前缀的得分」—— 前缀最大值与得分累计的单遍扫描 导读 本文基于 leetcode/科学计算上一篇Bytebase Plan Check Run 运行时派生重构从存储冗余配置到动态派发的实现全解下一篇PocketPal AI 上手指南下载、加载模型并完全离线地运行手机端 LLM创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考