01子序列构造题怎么做？贪心+前后缀判断与边界处理

今天在OJ上刷到一道题编号 HJ117名字叫“小红的01子序列构造easy”。题目很简短但里面藏了不少容易踩的坑。核心是给一个01串让你按顺序挑一些字符组成子序列最终形态要求是若干个0后面跟着若干个1而且0的数量和1的数量都有硬性指标。要求输出任意一组可行下标构造不出来就输出 -1。这类“子序列构造”题在机试、面试里其实非常常见本质是贪心前后缀判断难度不高但特别能区分“会写代码”和“真懂边界”的人。我自己第一次写的时候也翻过车不是思路不对而是卡在“全局够不够”和“顺序对不对”这两件事上。这篇文章就把整道题的思考过程、正解推导、代码实现和避坑经验一次性讲清楚适合刚刷算法题的同学也适合想快速掌握子序列构造类题目套路的人。1. 先把题意掰开揉碎1.1 题意还原题目给了一个长度为 n 的 01 串 s下标从 1 开始。再给两个非负整数 a 和 b要求从 s 中选出一个子序列。子序列的意思是可以跳过任意字符但不能改变剩下字符的相对顺序。选出来的字符拼在一起后必须满足两个条件恰好包含 a 个字符 0恰好包含 b 个字符 1所有选出的 0 都必须排在所有选出的 1 前面第三个条件很关键它决定了选出的子序列长成 00...0011...11 这种样子也就是前段全是 0、后段全是 1。如果 a 或 b 为 0子序列可以全是 1 或全是 0。输出时要求输出你选中的那些位置的下标下标按原串顺序递增。如果不存在任何合法方案就输出 -1。1.2 输入输出格式按照竞赛常见的输入方式第一行是三个整数 n、a、b第二行是一个长度为 n 的 01 串 s。如果题目有多组测试数据一般会先给一个 T再循环处理每组。这里我们先按单组输入来写多组的变形后面会额外说明。举例来说5 2 1 01011这组数据里n5a2b1目标是从01011中选出一个001样子的子序列。一个可行方案是选第 1、3、4 个字符得到子序列001所以输出可以是1 3 4。1.3 这道题到底想考什么英文名带 easy说明它不考高级数据结构也不考复杂 DP。核心考点是三点你能不能把“子序列构造”转化成“找一个分界位置”的思维你能不能正确处理 a 或 b 为 0 的边界你能不能写出 O(n) 的线性扫描构造方案很多人第一眼觉得这题特别简单因为“只要原串里 0 的总数不少于 a、1 的总数不少于 b不就行了吗” 这个直觉只对了一半。如果题目不要求 0 全部在 1 前面那确实只看总数即可。但一旦加了顺序限制总数够并不代表能构造得出来。2. 暴力枚举为什么最先被淘汰2.1 子序列组合数爆炸拿到这种题很多人的第一反应是枚举所有子序列。给定一个长度为 n 的串每个位置都有“选”和“不选”两种可能一共 2 的 n 次方种子序列。n 取 20 就已经超过一百万n 取 30 就已经到了十亿级别更别说常见的 n 能到 10 万甚至更大。即使你写回溯剪枝剪枝也只能在很小范围的数据上有效一旦遇到全是 0 或者全是 1 的串剪枝几乎没用因为任何选法都可能满足数量要求。你会在递归栈里越陷越深最后换来一个超时。用书架来打比方一排书架上有很多红色书和蓝色书让你从里面挑特定数量的红书和蓝书要求挑出来的红书必须全部在蓝书左边。如果你挨个试“每一种挑法”书架只有几层还能忍哪怕书多到几百本组合数量就已经超出人力范围了。你需要找规则而不是拼力气。2.2 从“选哪些位置”到“找一刀切在哪里”关键观察是因为最终子序列的形态是 0^a 1^b那么所有被选中的 0 一定来自原串中的某一个前缀段所有被选中的 1 一定来自剩余的后缀段。我们可以理解为在原串里切一刀切点左边负责提供 0切点右边负责提供 1。这样一来问题发生了本质变化。原来要决策 n 个位置选不选是一个组合问题现在只需要找到一个切分点 i使得左段 s[1..i] 里至少有 a 个 0右段 s[i1..n] 里至少有 b 个 1找到切分点之后左段挑够 a 个 0右段挑够 b 个 1方案就构造出来了。这就是对问题的一次“降维”把组合枚举变成了线性扫描。2.3 全局数量足够就一定存在吗很多人在这里会踩坑。举个例子s 1100a 1b 1。原串中 0 的总数是 21 的总数也是 2数量上完全够。但是你有没有发现所有 0 都在所有 1 的后面。你不可能从1100里选出一个 0 在前、1 在后的子序列因为最右边的 1 的下标是 2最左边的 0 的下标是 3还没等选出 01 就已经出现了。如果只统计全局 0 和 1 的数量然后直接输出答案遇到1100这种数据一定会 WA。这说明“数量够”只是必要条件不是充分条件。真正严格的条件是要么 a 或 b 为 0不需要考虑顺序要么第 a 个 0 出现的位置必须早于倒数第 b 个 1 出现的位置。3. 正解一前缀 0 加后缀 1直观且好写3.1 先预处理两个关键数组第一种正解思路是预处理。定义 pre0[i] 表示 s[1..i] 中字符 0 的个数定义 suf1[i] 表示 s[i..n] 中字符 1 的个数。用 Python 代码写的话n 5 s 01011 s s # 变成 1-indexed pre0 [0] * (n 2) suf1 [0] * (n 3) for i in range(1, n 1): pre0[i] pre0[i - 1] (1 if s[i] 0 else 0) for i in range(n, 0, -1): suf1[i] suf1[i 1] (1 if s[i] 1 else 0)这里有一个很容易忽略的细节suf1 数组要多开一位因为后面可能会访问 suf1[i1]当 i 取到 n 的时候访问的是 suf1[n1]这个位置必须存在且初始为 0。3.2 枚举分界点预处理完成后枚举切分点 i范围是 0 到 n。i 0 表示左段为空i n 表示右段为空。分界点合法需要同时满足两个条件pre0[i] a 且 suf1[i 1] b从左往右找第一个满足条件的位置即可因为题目只要求任意一种方案不要求最优。比如前面的例子01011n5a2b1i1 时pre0[1]1不够 a2跳过i2 时pre0[2]1不够i3 时pre0[3]2suf1[4] 是第 4 位和第 5 位中 1 的个数为 2满足条件所以切分点可以选在 i3。这意味着左段是010右段是11。3.3 按分界点构造答案找到分界点之后构造方案非常简单在左段s[1..i]里从左往右扫描拿到前 a 个字符 0 的下标在右段s[i1..n]里从左往右扫描拿到前 b 个字符 1 的下标把两段下标按顺序拼起来输出为什么取“前 a 个 0”和“前 b 个 1”就够因为分界点条件已经保证了左段至少有 a 个 0、右段至少有 b 个 1。取左边前 a 个 0下标一定都小于等于 i取右边前 b 个 1下标一定都大于 i所以两组位置天然满足“0 在前、1 在后”的顺序。3.4 复杂度与正确性论证这种解法的时间复杂度是 O(n)空间复杂度也是 O(n)因为要存两个长度为 n 的数组。正确性可以从两个方向证明如果需要选出的子序列是 0^a1^b那么它必然存在一个分界点你可以把选出的最后一个 0 的位置当作 i所有选中的 0 都在 i 左边所有选中的 1 都在 i 右边。此时 pre0[i] 至少是 asuf1[i1] 至少是 b。也就是说只要方案存在我们一定能在这个枚举循环里找到至少一个合法分界点。反过来如果找到了一个合法分界点按照“左段取前 a 个 0、右段取前 b 个 1”的构造方法一定能取出恰好 a 个 0 和 b 个 1并且所有 0 的下标都小于所有 1 的下标。因此构造结果合法。逻辑是闭环的这个解法可以直接交。4. 正解二推导公式O(1) 空间完成构造4.1 关键变量拆解前缀后缀做法虽然直观但需要开两个数组。实际上题目还有一个更简洁的数学版本只需要记住几个关键位置。定义cnt0整个串中 0 的总数cnt1整个串中 1 的总数pos0_a第 a 个 0 出现的位置注意 a 从 1 开始数如果 a0这个位置不存在pos1_lb倒数第 b 个 1 出现的位置也就是正数第 cnt1-b1 个 1如果 b0这个位置不存在举一个例子s01011cnt02cnt13。a2 时第 2 个 0 出现在位置 3所以 pos0_a3。b1 时倒数第 1 个 1 出现在位置 5所以 pos1_lb5。4.2 存在性判断公式有了这几个变量整个题目的判定可以压缩成一条公式cnt0 a cnt1 b 并且 (a 0 或 b 0 或 pos0_a pos1_lb)前面两个条件保证数量足够第三个条件保证顺序可行。为什么只要比较第 a 个 0 和倒数第 b 个 1 的位置就够了因为我们构造时会取前 a 个 0 和最后 b 个 1。前 a 个 0 中下标最大的是 pos0_a最后 b 个 1 中下标最小的是 pos1_lb。只要 pos0_a 严格小于 pos1_lb就说明所有选中的 0 都在所有选中的 1 左侧一定可以构造出一个合法的 0^a1^b 子序列。反过来看如果 pos0_a 大于等于 pos1_lb说明第 a 个 0 出现的时候倒数第 b 个 1 已经出现完了或者两者位置交叠。这种情况下不可能找到 a 个 0 全部位于 b 个 1 左侧的选法。4.3 按公式构造方案判定通过之后构造方案也直接照搬公式从左往右扫描整个串依次收集第 1 到第 a 个 0 的位置从右往左扫描整个串依次收集倒数第 1 到第 b 个 1 的位置注意输出顺序不能简单地“左边收集完再输出右边”如果把右侧从右往左收集到的下标直接倒序放入答案可能打乱升序一个稳妥做法是先从左往右收集 0 的位置放进答案然后再从左往右扫描只收集那些下标大于等于 pos1_lb 的 1 的位置放进答案。这样答案天然是升序的。4.4 O(1) 空间版本代码下面是 Python 的 O(1) 空间版本def solve(): n, a, b map(int, input().split()) s input().strip() s s cnt0 s.count(0) cnt1 s.count(1) if cnt0 a or cnt1 b: print(-1) return pos0_a -1 seen0 0 if a 0: for i in range(1, n 1): if s[i] 0: seen0 1 if seen0 a: pos0_a i break pos1_lb -1 seen1 0 need cnt1 - b 1 if b 0: for i in range(1, n 1): if s[i] 1: seen1 1 if seen1 need: pos1_lb i break if a 0 and b 0 and pos0_a pos1_lb: print(-1) return ans [] take0 0 for i in range(1, n 1): if take0 a: break if s[i] 0: ans.append(i) take0 1 take1 0 if b 0: for i in range(pos1_lb, n 1): if take1 b: break if s[i] 1: ans.append(i) take1 1 print( .join(map(str, ans)))这个版本只用了常数个额外变量非常适合内存限制极小的场景。5. 完整代码与样例手跑5.1 推荐的前后缀完整代码我自己在比赛环境里更喜欢第一种前后缀写法因为思路清晰不容易漏边界。推荐代码放在这里直接可以提交import sys def solve(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) a int(data[1]) b int(data[2]) s data[3] pre0 [0] * (n 2) suf1 [0] * (n 3) for i in range(1, n 1): pre0[i] pre0[i - 1] (1 if s[i] 0 else 0) for i in range(n, 0, -1): suf1[i] suf1[i 1] (1 if s[i] 1 else 0) cut -1 for i in range(0, n 1): if pre0[i] a and suf1[i 1] b: cut i break if cut -1: print(-1) return ans [] cnt0 0 for i in range(1, cut 1): if cnt0 a: break if s[i] 0: ans.append(i) cnt0 1 cnt1 0 for i in range(cut 1, n 1): if cnt1 b: break if s[i] 1: ans.append(i) cnt1 1 print( .join(map(str, ans))) if __name__ __main__: solve()5.2 手跑一个能过的样例用样例5 2 1 / 01011跑一遍pre0[1]1, pre0[2]1, pre0[3]2, pre0[4]2, pre0[5]2suf1[1]3, suf1[2]3, suf1[3]2, suf1[4]2, suf1[5]1, suf1[6]0枚举 i当 i3 时 pre0[3]2 满足 asuf1[4]2 满足 b所以 cut3。左段取到两个 0 的位置是第 1 位和第 3 位右段取到一个 1 的位置是第 4 位。输出1 3 4对应子序列001合法。5.3 边界用例汇总有些边界情况特别值得单测用例ab期望结果4 1 1 / 110011-13 0 1 / 01001输出任意一个 1 的下标比如 24 2 0 / 010120输出两个 0 的下标比如 1 33 3 0 / 01030-1因为 0 的数量不够2 1 1 / 0111输出 1 22 1 1 / 1011-1这些用例全部通过代码就可以放心提交了。特别注意010中 a0 的情况说明不需要 0所以切分点可以直接取在 0 位置右边整个串里找 1 就行。5.4 多组输入的改动如果题目给的是多组测试只需要在外层套一个 Tdef solve(): data sys.stdin.read().strip().split() if not data: return t int(data[0]) idx 1 out [] for _ in range(t): n int(data[idx]); a int(data[idx1]); b int(data[idx2]); idx 3 s data[idx]; idx 1 # 中间逻辑相同 out.append( .join(map(str, ans))) sys.stdout.write(\n.join(out))注意每次处理完一组后ans 和 cut 要重置不能沿用上一组的状态。6. 踩坑记录与排查技巧6.1 字符常量写错这个错误听起来低级但真会出现。有人写if s[i] 0在 Python 里s[i]是字符串0而0是整数永远不相等导致统计结果全是 0判断结果全是 -1。在 C 里如果不小心写成if (s[i] 0)同样有问题。建议统一写成s[i] 0并且盯住单引号。6.2 1-indexed 和 0-indexed 混用机试里字符串经常按 0-indexed 给出但题目要求输出 1-indexed。如果只写代码不测试很容易输出整体偏移一位。我的习惯是读入字符串后立刻在前面加一个占位符变成 1-indexed后面所有下标逻辑都统一这样基本不会错。有时候前缀数组也会踩坑如果用 0-indexedpre0[i] 表示前 i 个字符判断时容易把“前 i 个”和“第 i 个”搞混。为了避免这种问题建议用 1-indexed数组下标直接对应原串位置。6.3 a 或 b 为 0 时的漏判如果 a0左段可以为空切分点可以直接取 0如果 b0右段可以为空切分点可以直接取 n。我的第一版代码里对这两个边界没有单独处理结果遇到 a0 时循环找切分点把 i0 排除掉了一直输出 -1。正确的做法是保证枚举范围包含 0 和 n并且 pre0[0]0、suf1[n1]0。只要数组开到位a0 或 b0 都能自然处理。6.4 输出顺序必须升序输出下标时很多人都能找对位置但输出顺序可能乱。有些代码先收集右边的 1再收集左边的 0结果输出成4 1 3OJ 会判格式错误。虽然子序列的内容还是100但要求的输出一般按原串顺序也就是先输出 0 的下标再输出 1 的下标。解决方案就是先收集 0再收集 1最后统一输出不要边收集边反着输出。6.5 如果题目要求字典序最小的下标序列上面的构造法只保证“存在一个合法方案”但不保证下标字典序最小。如果题目升级成 hard要求输出所有合法方案中下标序列字典序最小的那个思路就要调整。核心还是贪心但每次决定“当前位置选不选”之前必须确认选了它之后剩余部分仍然能完成剩下的需求。比如扫描到某个位置如果当前还在选 0 阶段你可以尝试选这个 0但如果选了它之后后面剩余的 1 不够了就不能选。这种时候需要先统计后缀的 0 和 1 数量再结合剩余需求做判断。比 easy 的任意构造复杂不少但正好是这个 easy 题的延伸。6.6 扩展子序列匹配和 DFA 的关系子序列构造题的底层逻辑其实和自动机很接近。如果题目给的不是 0^a1^b 这种固定形态而是要求选出某个正则语言对应的子序列比如匹配1(0|1)*101那就不只是前后缀计数能解决的了。常规做法是把目标正则表达式转成一个 DFA然后扫描原串每扫到一个字符都有两个选择忽略它或者选它并让自动机状态发生转移。最终只要有一个状态落在接受态就说明存在合法子序列。这就是子序列自动机和模式自动机结合的思想。不过对于这道 easy 题0^a1^b本质上也是一个最简单的自动机先匹配 a 个 0再匹配 b 个 1。理解了前后缀分界点就等于理解了自动机的状态切换以后遇到更复杂的构造题思路也会顺很多。最后说点个人体会这道题让我印象最深的并不是公式推导而是“数量足够”这个直觉陷阱。我自己第一次提交时就想着“全局 0 和 1 都够直接输出不就行了”结果被一组1100教做人。从那以后凡是看到子序列构造我都会先问一句顺序上的限制到底是什么能不能在 O(n) 时间内检查完其实这类题目套路很固定要么找分界点要么维护最靠前和最靠后的候选位置要么用自动机状态压缩。把这些套路练熟后面遇到 hard 版本也不会慌。最后建议你自己动手把前缀后缀版本和 O(1) 版本各写一遍再跑一跑边界用例保证下次看到“01子序列构造”这几个字心里已经有底了。