这是 LeetCode 3574. 最大子数组 GCD 分数 的 Rust 实现。解题思路核心观察翻倍操作最多只能让子数组的 GCD 乘以 2。因此对于每个子数组我们需要判断是否能通过最多 k 次翻倍操作使 GCD 翻倍。关键步骤1. 预处理统计每个数中因子 2 的个数即 x 能被 2 整除的次数2. 枚举子数组固定左端点 l向右扩展右端点 r3. 维护三个值- g当前子数组的 GCD- mi子数组中因子 2 个数的最小值- t具有最小因子 2 个数的元素个数4. 判断翻倍如果 t k说明需要翻倍的元素超过 k 个无法翻倍否则 GCD 可以翻倍时间复杂度O(n^2 \cdot \log n)空间复杂度O(n)Rust 代码rustimpl Solution {pub fn max_gcd_score(nums: Veci32, k: i32) - i64 {let n nums.len();// 预处理统计每个数中因子 2 的个数let mut cnt vec![0i32; n];for i in 0..n {let mut x nums[i];while x % 2 0 {cnt[i] 1;x / 2;}}let mut ans: i64 0;// 枚举所有子数组for l in 0..n {let mut g: i32 0; // 当前子数组 GCDlet mut mi: i32 1 30; // 最小因子 2 个数let mut t: i32 0; // 具有最小因子 2 个数的元素个数for r in l..n {// 更新 GCDg Self::gcd(g, nums[r]);// 更新最小因子 2 个数及其出现次数if cnt[r] mi {mi cnt[r];t 1;} else if cnt[r] mi {t 1;}// 判断是否能翻倍 GCD// 如果具有最小因子 2 个数的元素个数 k则无法翻倍let val if t k { g as i64 } else { (g * 2) as i64 };let len (r - l 1) as i64;ans ans.max(len * val);}}ans}// 递归实现 GCDfn gcd(a: i32, b: i32) - i32 {if b 0 {a} else {Self::gcd(b, a % b)}}}代码说明- cnt[i] 记录 nums[i] 中因子 2 的个数例如 12 2^2 × 3则 cnt[i] 2- 翻倍操作的本质是将某个数乘以 2相当于增加一个因子 2- 子数组 GCD 中因子 2 的个数取决于子数组中所有数因子 2 个数的最小值 mi- 如果具有最小值 mi 的元素个数 t k则最多 k 次翻倍无法让所有这些元素的因子 2 个数都增加GCD 无法翻倍- 否则可以通过翻倍使 GCD 乘以 2这个解法在 n \le 1500 的约束下可以通过所有测试用例。
这是 LeetCode 3574. 最大子数组 GCD 分数 的 Rust 实现。解题思路核心观察翻倍操作最多只能让子数组的 GCD 乘以 2。因此对于每个子数组我们需要判断是否能通过最多 k 次翻倍操作使 GCD 翻倍。关键步骤1. 预处理统计每个数中因子 2 的个数即 x 能被 2 整除的次数2. 枚举子数组固定左端点 l向右扩展右端点 r3. 维护三个值- g当前子数组的 GCD- mi子数组中因子 2 个数的最小值- t具有最小因子 2 个数的元素个数4. 判断翻倍如果 t k说明需要翻倍的元素超过 k 个无法翻倍否则 GCD 可以翻倍时间复杂度O(n^2 \cdot \log n)空间复杂度O(n)Rust 代码rustimpl Solution {pub fn max_gcd_score(nums: Veci32, k: i32) - i64 {let n nums.len();// 预处理统计每个数中因子 2 的个数let mut cnt vec![0i32; n];for i in 0..n {let mut x nums[i];while x % 2 0 {cnt[i] 1;x / 2;}}let mut ans: i64 0;// 枚举所有子数组for l in 0..n {let mut g: i32 0; // 当前子数组 GCDlet mut mi: i32 1 30; // 最小因子 2 个数let mut t: i32 0; // 具有最小因子 2 个数的元素个数for r in l..n {// 更新 GCDg Self::gcd(g, nums[r]);// 更新最小因子 2 个数及其出现次数if cnt[r] mi {mi cnt[r];t 1;} else if cnt[r] mi {t 1;}// 判断是否能翻倍 GCD// 如果具有最小因子 2 个数的元素个数 k则无法翻倍let val if t k { g as i64 } else { (g * 2) as i64 };let len (r - l 1) as i64;ans ans.max(len * val);}}ans}// 递归实现 GCDfn gcd(a: i32, b: i32) - i32 {if b 0 {a} else {Self::gcd(b, a % b)}}}代码说明- cnt[i] 记录 nums[i] 中因子 2 的个数例如 12 2^2 × 3则 cnt[i] 2- 翻倍操作的本质是将某个数乘以 2相当于增加一个因子 2- 子数组 GCD 中因子 2 的个数取决于子数组中所有数因子 2 个数的最小值 mi- 如果具有最小值 mi 的元素个数 t k则最多 k 次翻倍无法让所有这些元素的因子 2 个数都增加GCD 无法翻倍- 否则可以通过翻倍使 GCD 乘以 2这个解法在 n \le 1500 的约束下可以通过所有测试用例。
![P10098 [ROIR 2023] 地铁建设 (Day 2)](http://pic.xiahunao.cn/yaotu/P10098 [ROIR 2023] 地铁建设 (Day 2))
