在算法竞赛圈里B. Odd Sum Segments 是一道被很多人拿来练手的经典思维题。第一次做它的时候我差点就去写区间 DP 了因为“数组分段 每段和满足某种性质”这个描述实在太容易让人往动态规划的方向想。但后来想明白才发现题目的核心根本不是动态规划而是奇偶性。整道题的题眼就一句话子段和是不是奇数只取决于这个子段里奇数的个数。偶数无论怎么参与相加都不会改变和的奇偶性。抓住这一点后面所有推导都会变得顺理成章。这篇文章我会从题意拆解开始把两个关键条件的推导过程、构造方法、C 和 Python 实现、样例逐段走读、常见错误排查全部过一遍。无论你是刚接触竞赛、想通过这道题锻炼思维的新手还是已经有一定经验、想帮学弟学妹把这道题讲透的学长学姐都能从里面拿到可以直接复现的东西。1. 题目回顾Odd Sum Segments 到底在问什么1.1 题意拆成四个要素题目给了一个长度为 n 的整数数组 a以及一个目标段数 k。要求我们把数组切成恰好 k 个非空的连续子段并且让每个子段的元素和都是奇数。这里的“连续”指的是原数组中的连续区间不允许打乱元素顺序也不允许跳过某些元素。每一段的长度没有限制可以只包含一个元素也可以很长但绝对不能为空。如果做不到输出 NO如果做得到要先输出 YES再输出一种合法切割方案的“右端点列表”。所谓右端点列表就是 k 个数字第 i 个数字表示第 i 个子段在原数组中的结束下标。下标从 1 开始计数。因为 k 段拼接起来必须恰好覆盖整个数组所以最后一段的右端点一定是 n。这一点在写代码的时候特别容易出问题后面我会专门强调。为什么输出的是右端点而不是断点这是出题人故意设计的输出格式。很多同学第一次做这类题时会下意识想到输出断点位置比如切成三段就输出两个断点结果和题目要求的输出数量对不上。其实只要记住一个规则输出 k 个数最后一个必须是 n就不会被绕进去。1.2 用两个小例子建立直觉先说一个可行例子。假设输入这组数据6 3 7 1 3 6 4 2数组里的奇数分别是 7、1、3出现在下标 1、2、3 的位置奇数总数 c 3恰好等于目标段数 k 3。一种合法的切法是让三个奇数分别坐镇三段第 1 段只有 [7]和为 7第 2 段只有 [1]和为 1第 3 段是剩下的 [3,6,4,2]和为 15。三个和都是奇数所以输出 YES然后输出右端点1 2 6。第一段结束在 1第二段结束在 2第三段结束在 6。再看一个反例体会条件不满足时的感觉3 2 1 1 1奇数总数 c 3目标段数 k 2。直观上看3 个奇数分给 2 段每段分到的奇数个数只能是 1 和 2或者 2 和 1。但每一段要想得到奇数和段内的奇数个数必须是奇数。分到 2 个奇数的段和一定会变成偶数。因此无论怎么切都切不出两段奇数和。事实上两个奇数段的和相加是偶数而整个数组总和是 3属于奇数这本身就互相矛盾。所以答案只能是 NO。这两个例子基本揭示了题目想考察的性质奇数的总数以及奇数总数和段数之间的奇偶关系。1.3 从样例中带出两个疑问看完上面两个例子自然会冒出两个问题。第一奇数总数少于段数时一定不行吗第二奇数总数够但恰好和段数“一奇一偶”时为什么也不行这两个问题其实就是整道题的解法核心。每一个问题对应一个必要条件而神奇的是这两个必要条件合在一起之后就变成了充分条件。下一节我一步步推给你看。2. 核心思路为什么这道题不需要动态规划2.1 把数组压缩成 0/1 串遇到“子段和满足某种性质”的题目很多人第一反应是前缀和。前缀和当然强大但它把每个元素的具体数值都记下来了而这个题目只关心奇偶性。偶数是完全不影响和的奇偶性的真正能改变奇偶性的只有奇数。所以完全可以先把数组做一次抽象偶数记为 0奇数记为 1。于是问题变成了把一个只含 0 和 1 的序列切成 k 段要求每一段里 1 的个数都是奇数。这个抽象不是抖机灵它直接把问题的维度压了下来。原数组的值域可能很大数值本身也可能很复杂但抽象之后只留下“奇数出现在哪些位置”这一条信息。0 相当于填充材料它不影响奇偶性只影响这段是否非空。真正决定怎么切分的是那些散落在数组里的奇数。举一个生活类比可能更好懂把一堆硬币分成 k 摞要求每摞包含奇数个正面朝上的硬币。反面朝上的硬币放在哪一摞、放多少都不会影响这一摞是否满足要求只要这一摞本身非空就行。于是问题就化简成了“如何把若干枚正面硬币分配到 k 个非空摞里而且每摞的正面硬币数为奇数”。2.2 两个必要条件数量够奇偶配得上设数组里奇数总数为 c。第一必须满足 c k。因为每一段的和要为奇数每一段内部至少要包含一个奇数。如果某一段一个奇数都没有这一段里全是偶数和必然是偶数直接违反要求。这是典型的抽屉原理k 个盒子都要至少放入一个球球总数就不能少于盒子数。第二c 和 k 的奇偶性必须相同也就是 c % 2 k % 2。理由可以这样看假设确实切成了 k 段第 i 段内的奇数个数记为 oi。因为每段和是奇数所以每个 oi 都是奇数。那么全局奇数总数 c o1 o2 ... ok。k 个奇数相加奇偶性是什么奇数个奇数相加为奇数偶数个奇数相加为偶数所以右边整体的奇偶性恰好等于 k 的奇偶性。于是 c 的奇偶性必须等于 k 的奇偶性。换个角度从总和看会更直观如果切割可行整个数组的总和就是 k 个奇数相加。奇数个奇数相加为奇数偶数个奇数相加为偶数所以总和的奇偶性等于 k 的奇偶性。而数组总和的奇偶性又等于奇数个数 c 的奇偶性。两边对应起来立刻得到 c 和 k 必须同奇偶。这两个条件缺一不可。前面举过的反例“3 2 / 1 1 1”就是 c 3、k 2数量够但奇偶性不匹配而“4 3 / 2 4 6 8”则是 c 0、k 3数量不够直接出局。2.3 充分性与构造取前 k-1 个奇数位置就行必要条件是“必须如此”但竞赛题往往还会要求输出具体方案所以我们还得回答这两个条件满足时一定存在合法切法吗答案是可以而且方案异常简单把前 k-1 个奇数出现的位置依次作为前 k-1 段的右端点最后一段自然延伸到 n。具体来说先找到第 1 个奇数出现的位置 p1、第 2 个奇数出现的位置 p2、……、第 k-1 个奇数出现的位置 p(k-1)。然后这样切第 1 段[1, p1]第 2 段[p11, p2]第 3 段[p21, p3]...第 k-1 段[p(k-2)1, p(k-1)]第 k 段[p(k-1)1, n]先检查前 k-1 段第 i 段恰好包含第 i 个奇数也就是说每段的奇数个数都是 11 是奇数所以每段和一定是奇数。段内无论混入多少偶数结果都不会变。再看最后一段它包含从第 k 个到第 c 个所有剩余的奇数数量为 c - (k - 1)。这个数是奇数吗利用 c 和 k 同奇偶的性质就可以证明。分两种情况如果 c 和 k 都是奇数那么 c - (k-1) 奇数 - 偶数 奇数如果 c 和 k 都是偶数那么 c - (k-1) 偶数 - 奇数 奇数。两种情况的结果都是奇数所以最后一段也满足“包含奇数个奇数”和就是奇数。最后确认非空c k 意味着第 k 个奇数一定存在而且它落在了最后一段里所以最后一段至少有一个元素。前 k-1 段更是由构造方式天然保证非空。因此这个构造方案在且仅在前述两个条件下成立。之所以选“前 k-1 个奇数位置”是因为它让每段恰好分到一个奇数逻辑最清爽。如果换一种切法就需要额外保证前 k-1 段每段的奇数个数是奇数最后一段剩下的奇数个数也是奇数校验起来麻烦也容易漏。竞赛中抢时间最简单直接的构造方法往往就是最稳的。2.4 用编号理解把奇数排好队为了加深理解可以换一个视角把所有奇数按在数组中的先后顺序编号1 号、2 号、……、c 号。切割方案本质上是把这 c 个编号分到 k 个段里并且每段拿到的编号个数是奇数。我的构造方案其实就是前 k-1 段各领 1 个编号最后一段领走剩余的所有编号。前 k-1 段每段 1 个是奇数最后一段领走 c - (k - 1) 个因为 c 和 k 同奇偶这个数恰好也是奇数。所以问题完全变成了一个“分配数量奇偶性”的问题和元素的具体值彻底无关。3. 完整解法与代码实现3.1 算法流程照这个顺序写不容易错整个解法可以总结成五步。按照这个顺序实现逻辑会非常清晰。读入 n、k 和整个数组。从头到尾扫描数组遇到奇数就把它的下标从 1 开始记录到列表 oddPos 中同时统计总数 c。判断可行性如果 c k或者 c 和 k 的奇偶性不同直接输出 NO。否则输出 YES然后构造答案列表取 oddPos 的前 k-1 项最后补一个 n。答案列表正好有 k 个数。把答案列表在一行内用空格分隔输出。如果有多组测试数据每组之间正常换行即可。第 5 步的“补一个 n”非常关键。它保证了最后一段从上一个断点的下一个位置延伸到数组末尾。如果这里漏了 n或者错误地用了 oddPos[k-1]也就是第 k 个奇数所在位置最后一段就不能完整覆盖数组要么段数不对要么覆盖范围不对都会导致 WA。3.2 C 参考实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin q; while (q--) { int n, k; cin n k; vectorint oddPos; for (int i 1; i n; i) { int x; cin x; if (x 1) { oddPos.push_back(i); } } int c (int)oddPos.size(); if (c k || ((c 1) ! (k 1))) { cout NO\n; continue; } vectorint ans; for (int i 0; i k - 1; i) { ans.push_back(oddPos[i]); } ans.push_back(n); cout YES\n; for (int i 0; i k; i) { if (i) cout ; cout ans[i]; } cout \n; } return 0; }这段代码的每个分支都在做简单的事。唯一要提醒的是判定条件里用的是“或者”不是“并且”。只要 c k 成立或者奇偶性不匹配就无解。用 and 连接两个非法条件会让本该无解的用例漏过去这是比较常见的笔误。3.3 Python 参考实现import sys def solve(): data list(map(int, sys.stdin.read().split())) q data[0] idx 1 out [] for _ in range(q): n, k data[idx], data[idx 1] idx 2 odd_pos [] for i in range(1, n 1): x data[idx] idx 1 if x 1: odd_pos.append(i) c len(odd_pos) if c k or (c 1) ! (k 1): out.append(NO) else: ans odd_pos[:k - 1] [n] out.append(YES) out.append( .join(map(str, ans))) sys.stdout.write(\n.join(out)) if __name__ __main__: solve()Python 版本里我用了sys.stdin.read()一次性读入这比循环 input() 快很多尤其当测试数据组数多、数组长度大的时候。odd_pos[:k-1] [n]这一行直接构造答案列表思路清晰想写错都难。这种“最后统一输出答案列表”的写法建议记住。3.4 复杂度为什么 O(n) 就是天花板这个解法的时间开销是一轮线性扫描加一轮答案输出整体 O(n)。空间上用一个向量存所有奇数位置最坏情况下数组全是奇数oddPos 长度等于 n空间 O(n)。有些选手会追求 O(1) 空间思路是第一遍扫描先数出奇数总数 c判断可行性第二遍扫描再输出前 k-1 个奇数位置最后补 n。这样确实可以把存位置的数组省掉但代码会多一次循环而且第二遍扫描需要重新访问数组通常还是要先把数组原样存下来空间反而没省多少。用 oddPos 记录位置信息是时间空间最均衡的方案。对这道题的数据规模来说O(n) 空间完全不是问题不要为了省一点内存把代码写得复杂。竞赛里面正确性和可读性的优先级永远高于微小的常数优化。4. 样例走读把切割过程一点点推给你看4.1 可行例三奇三段直接分配回到刚才的用例6 3 7 1 3 6 4 2模拟一遍算法。扫描数组7 是奇数位置 pos 11 是奇数pos 23 是奇数pos 3后面的 6、4、2 都是偶数不记录。于是 oddPos [1, 2, 3]c 3。c k 成立c % 2 1k % 2 1奇偶性相同输出 YES。答案取 oddPos 的前两个位置 [1, 2]再补上 n 6得到 [1, 2, 6]。验证三段第 1 段 [1, 1]也就是元素 7和是奇数第 2 段 [2, 2]也就是元素 1和是奇数第 3 段 [3, 6]也就是元素 3、6、4、2和为 15奇数。全部满足答案正确。可以看到只要奇数个数和段数匹配前 k-1 段各拿一个奇数最后一段收尾是所有方案里最好实现的一种。4.2 反例数量够但奇偶不匹配用例3 2 1 1 1oddPos [1, 2, 3]c 3。c k 成立但 c % 2 1k % 2 0奇偶性不同输出 NO。这里有一个非常直观的解释如果想把数组切成 2 段且两段和都是奇数那么这两段的和加起来必然是奇数加奇数结果是偶数。可整个数组的和是 1 1 1 3是奇数前后矛盾。所以无论怎么切都不存在满足条件的分割。这类反例建议在推导思路时经常使用它能帮你快速确认奇偶性条件不是多余的。如果只看 c k这道题就会误判成 YES但真正的限制在于奇偶性。很多选手的第一次 WA就是栽在这里。4.3 边界情况k1 时会发生什么k1 意味着不需要切割整个数组就是唯一的子段。此时奇偶条件要求数组里的奇数总数 c 必须是奇数因为整个数组和要为奇数。我们的通用逻辑会怎么跑呢输入5 1 1 2 3 4 5oddPos [1, 3, 5]c 3。c 1 成立c % 2 1k % 2 1判定为 YES。答案取 oddPos 的前 0 个位置再补上 n 5得到 [5]。输出 YES 和一个数字 5表示整个数组作为一段从 1 到 5总和是 15奇数正确。如果你在代码里对 k1 单独做特判反而容易在特判分支里漏掉输出格式。通用构造逻辑天然覆盖了 k1 的情况这正是我喜欢这套推导的原因条件写清楚之后边界情况会自动归入同一套处理流程不需要记忆额外细节。4.4 边界情况奇数个数恰好等于段数当 c k 时每段必须恰好分到 1 个奇数。此时构造方案也自动成立。看这个用例4 2 1 2 3 4oddPos [1, 3]c 2k 2。条件满足答案取 oddPos 前 1 个位置 [1]补 n 4得到 [1, 4]。第一段只有 [1]和为 1第二段是 [2,3,4]和为 9奇数。合法。如果把输出改成 [3, 4] 呢第一段 [1,2,3] 里有两个奇数 1 和 3和为 6偶数不合法。这说明为什么构造时取的是“前 k-1 个奇数位置”而不是随便挑 k-1 个奇数位置。只要按前 k-1 个奇数位置切每一段恰好只吞进一个奇数逻辑不会出任何意外。5. 常见错误与调试指南5.1 五个典型翻车现场这道题代码很短但 WA 率却不低。我整理了几个最常见的翻车点基本覆盖了新手能踩到的坑。编号错误现象原因分析修正方法1只判断 c k 就输出 YES漏掉奇偶性条件比如 3 个奇数切 2 段会误判加上 c % 2 与 k % 2 不等的判 NO 逻辑2判定非法时用c k c % 2 ! k % 2用 and 连接两个非法条件导致只满足一个条件时漏判改成 or 运算只要任一条件不满足就是 NO3输出时用了 0-based 下标题目要求下标从 1 开始记录位置时没从 1 计起记录奇数位置时从 1 开始计数4答案列表忘了补 n只输出 oddPos 前 k-1 项段数少一段答案列表最后强制加入 n5多组数据之间输出格式混乱每组数据第二行单独输出答案格式没有组织好先把答案收集起来统一输出第二种错误尤其隐蔽因为样例常常刚好同时满足两个条件问题暴露不出来。写判定时心里默念“不合法如果数量不够或者奇偶配不上。”用“或者”连接两个非法条件就不会搞错。5.2 暴力对拍小数据验证思路遇到这类构造题最稳的验证方式是和暴力解法对拍。给一个非常简单的 Python 对拍思路暴力枚举所有可能的切割点判断是否存在合法方案快速解法是上面的贪心构造。在小数据范围内随机生成数组反复比对两者结论是否一致。from itertools import combinations def valid(a, cuts, k): cuts [0] list(cuts) [len(a)] for i in range(k): s sum(a[cuts[i]:cuts[i 1]]) if s % 2 0: return False return True def brute(a, k): n len(a) for cuts in combinations(range(1, n), k - 1): if valid(a, cuts, k): return True return False def fast(a, k): odd [i 1 for i, x in enumerate(a) if x 1] c len(odd) return c k and (c 1) (k 1)然后用类似下面的循环去跑随机数据import random for _ in range(10000): n random.randint(1, 8) k random.randint(1, n) a [random.randint(1, 20) for _ in range(n)] if brute(a, k) ! fast(a, k): print(mismatch!, n, k, a) break如果跑一万组随机数据都没发现不一致这个快速解法的正确性就非常可信了。注意上面的暴力函数里枚举的是 Python 的切片位置相当于 0-based 的断点而题目要求输出 1-based 的右端点。做对拍时只需要比较有无解不需要比较具体输出如果要比对具体构造方案记得把 fast 的结果转成 Python 切片位置再验证。5.3 想出题可以从这道题扩展出什么这道题反映的是一大类“奇偶性质 分段计数”的题目。把它稍微改一改就能变成几个新问题。第一把“每段和为奇数”改成“每段和为偶数”。此时每段里的奇数个数必须是偶数。如果整个数组的奇数总数为奇数直接无解如果为偶数则可以把奇数两两配对放入某些段其他段全部放偶数。只要可用的“段容量”足够即 k 不超过偶数个数加上 c/2就有解。构造的时候同样可以让前若干段各含 2 个奇数或各含 0 个奇数思路一脉相承。第二把奇偶条件升级为“每段和对某个模数 m 取余为特定值”。这时候 0/1 抽象就失效了需要依靠前缀和在模 m 意义下的分类计数题目难度会明显上一个台阶。不过“压缩类别、关注计数”的思想仍然是通用的。第三把“分割成 k 段”变成“选择任意段数”问最少切成多少段能让每段和为奇数。这其实是对每个奇数单独成段需要的段数就是奇数个数除非奇数个数为 0。同样建立在奇偶性分析之上。想通过这类题锻炼思维建议每次读完题先花两分钟问自己三个问题关键性质能把数据压缩成什么必要的计数条件是什么构造方案能不能找一个最简单的固定模式养成这个习惯以后很多思维题会变得非常顺手。5.4 一些朴素的比赛实用建议最后给几点实际比赛里的经验。第一这类输出方案的题目一定要先把答案收集到 vector 或 list 里最后统一输出。边判断边输出很容易在某个分支里漏换行、多空格而且出错后很难定位。第二写完后自己构造两个极端用例验证一个是 k1一个是奇数总数恰好等于 k。这两个用例能把输出格式和边界条件暴露得最彻底。第三如果交上去 WA 了先别急着改算法极少数情况下是思路错更多时候是输出少了一个数或者多了一个数。用肉眼对照题目给定的样例格式往往比读代码更快发现问题。另外一个细节是多组数据时如果用的 C记得每一组循环里都使用局部变量。上面的代码因为每组都新建 oddPos 和 ans天然规避了上一组残留数据的影响。如果你习惯把变量定义在循环外一定要记得在每组开始时 clear否则下一组会读到上一组留下的奇数位置产生非常难查的灵异 WA。我在实际刷题时明显感觉到这类 B 题考察的永远不是“算法有多高级”而是“你能不能抓住问题的核心约束”。Odd Sum Segments 的核心约束就是奇偶性。一旦意识到子段和的奇偶性只与奇数个数相关题目就会从“区间规划”变成“数字计数”难度断崖式下降。个人习惯上我喜欢在做完一道这样的题之后顺手把条件改一改写成变体再推一遍。比如把奇数改成偶数、把固定段数改成最少段数、把 mod 2 改成 mod 3。这样一轮下来奇偶性这个考点基本上就吃透了。下次再遇到类似题可能别人还在画状态转移表你已经把答案构造出来了。