★ FEATURED ARTICLE Codeforces Round #661 (Div. 3) 的 D 题 Binary String To Subsequences是很多打 CF 的人印象很深的一道“思维 贪心”题。它不像常规 D 题那样需要树状数组、二分答案之类的套路而是给一个二进制字符串让你把每个字符分到若干个“好子序列”里要求子序列数量尽量少。我第一次做这题时差点把它当成区间划分来写结果越绕越复杂后来想明白维护两类末尾状态的队列就很简单了。如果你正卡在这种“明明看题解就几行自己却想不出来”的题上这篇内容正好适合你。我会从题意拆解开始逐步推导出贪心模型再给出一份可直接提交的 C 实现最后聊一聊我做这题踩过的坑和调试心得。1. 题目初印象这道“思维”题到底在考什么1.1 题目概况与核心题意建议先自己打开原题页面对照看这里只说核心。给定一个长度为 n 的二进制字符串 s字符只有 0 和 1。你需要把整个字符串的所有位置划分成若干个不相交子序列要求每个子序列都满足相邻两个字符不相同也就是子序列是 “0、1 交替”的形式比如 “010”、“1010”、“1”、“0” 都算好子序列。输出两样东西第一行是最少需要多少个子序列第二行是原字符串每个位置所属的子序列编号从 1 开始编号。注意这里有个关键区分它对“子序列”的要求是下标不连续没关系只要保持原来的先后顺序且挑出来的字符交替变化就行。也就是说原串里的字符并不需要连在一起你可以跳着取。这是最容易理解错的地方我在后面会重点展开。看一个简单例子。假设 s 0100位置 1 是 0必须新建一个子序列记它属于 1 号。位置 2 是 1可以接到 1 号后面变成 01所以它属于 1 号。位置 3 是 0又能接到 1 号后面变成 010所以它属于 1 号。位置 4 是 01 号末尾是 0不能再接否则会出现两个 0 相邻只能新建 2 号子序列。所以答案是 2归属是 1 1 1 2。把 2 号子序列单独拿出来就是 0也满足条件。题目的数据范围一般到 2×10^5所以算法必须做到 O(n) 或 O(n log n)不允许对每个字符暴力选一个子序列去检查末尾。1.2 为什么它被贴上“思维”标签在 Div. 3 的常规难度分布里A、B、C 往往偏向模拟和基础数据结构而 D 题开始考察“你能不能把问题转化成一个更简单的形式”。这道题被归类为“思维”题是因为它套路性弱不像“线段树维护区间和”那样看到就有定式。它的难点在于你需要意识到每个子序列能被哪些字符接上只取决于这个子序列当前最后一个字符是什么。只要末尾是 0下一个能接进来的只能是 1末尾是 1下一个能接进来的只能是 0。一旦抓住这一点问题就变成了扫描原串时手里有若干条子序列它们有的末尾是 0有的末尾是 1。当前字符来了我该怎么分配所以整道题考验的不是某个高级算法而是你能不能抽象出“末尾状态”这个唯一关键属性并且意识到可以用两个集合来维护这些子序列。这也是我想在第一部分先讲清楚的原因。我最初做这题时想过用 DP 去划分也想过先用双指针找交替段再合并段结果全是弯路。后来看了一篇题解才恍然大悟这题的答案不是“最少交替段数”而是“最少互不重叠且保持时序的交替序列数”根本不需要考虑连续区间。2. 解题思路推导从手算样例到贪心模型2.1 一个容易混淆的起点子序列和连续子段的区别很多人做这题的第一个直觉是把字符串切成交替的连续段比如 s0100 切成 010 和 0 两段答案似乎也是 2。可很多数据会让你这个直觉出错。我举一个反例s 1100。按连续段划分会得到 1、1、00 这样的结构很容易以为需要 3 个子序列。但最优答案是 21 号子序列第 1 个 1 第 3 个 0组成 10。2 号子序列第 2 个 1 第 4 个 0组成 10。归属结果就是 1 2 1 2。这个例子说明了什么说明我们可以在两个连续的 1 之间插入不同的子序列编号让它们分别去接后面不同的 0。子序列可以跳过中间的字符所以它不是连续区间划分问题。再看另一个例子s 1010。最优其实 1 个就够归属全是 1。但如果用连续段划分整个串本身就是交替段也能得到 1看不出区别。所以我的建议是拿到这种题先不要急着把字符串“切段”而是想“我能不能把这些字符同时分配到多条轨道上”。嘴里念叨“轨道数最少”比心里想着“连续段”要安全得多。2.2 两个集合的维护思路末尾状态决定一切再来推导核心模型。假设我们在扫描过程中维持了若干条子序列每条子序列的末尾字符只可能是 0 或 1。用一个直观的说法末尾是 0 的子序列当前“期待”一个 1 来接力。末尾是 1 的子序列当前“期待”一个 0 来接力。当读到一个新字符 c 时能接上它的子序列一定是一批末尾和 c 相反的子序列。如果这一批一个都没有那就只能开新子序列如果有随便挑一个出来接上即可。接管之后这个子序列的末尾变成了 c它就需要重新归类。所以整个算法只需要维护两样东西所有“末尾为 0 的子序列编号”集合记为 set0。所有“末尾为 1 的子序列编号”集合记为 set1。实际代码中用队列、栈、链表、vector 模拟都可以因为同一类型的子序列在这一刻是完全等价的。我习惯用两个队列这样语义最清晰队头放着“最早空闲下来、等待相反字符”的子序列编号。扫描过程如下遇到 0优先从 set1 里取出一个子序列编号 id把当前字符归给 id再把这个 id 放进 set0因为现在它末尾变成 0 了。如果 set1 为空就新开一个编号并放进 set0。遇到 1逻辑完全对称。优先从 set0 里取编号如果没有就新开一个并把编号归入 set1。为什么“优先取一个”而不是“取最新的”或者“随便取”因为当前所有可接的序列都是等价的取哪个都不影响后续状态集合的属性。唯一要注意的是别让同一个编号同时出现在两个集合里。如果我们严格做到“取出后从原集合删除、加入另一集合”就能避免这个错误。这里我想补充一个新手很容易掉的坑有人会把编号复制一份而不是删除导致同一个子序列既在 set0 又出现在 set1后续就可能被分配两次结果归属数组出现“一个位置用了已被其他位置占用的编号”最后答案完全错乱。2.3 贪心策略与正确性证明这一步看似简单但要想清楚“为什么这样可以保证最优”不然下次换一道类似的题你还是不会证。先说贪心策略每次遇到一个字符只要存在可接的子序列就绝不新开只有在没有可接序列时才新建子序列。证明分两部分。第一部分是下界。当前字符 c 要放进某个子序列如果所有现有子序列的末尾都和 c 相同那么 c 不可能接进任何现有序列只能新开一个。这个“只能新开”的次数是强制性的任何合法方案都避免不了所以最少子序列数量一定不小于扫描过程中这种强制新开的总次数加 1因为第一个字符也属于强制新开。第二部分是可达性。贪心算法只在“没有可接序列”时新开所以它实际产生的子序列数量就等于强制新开次数。既然它能构造出一种满足所有约束的划分而任何方案的下界就是这个强制新开次数贪心得到的一定是最优解。这个证明不需要高深数学但建议你自己完整推导一遍。做题时分析复杂度容易证明正确性才是“思维题”真正训练的地方。用一个小例子走一遍过程你能直观感受队列变化。假设 s 1100步骤当前字符set0末尾0set1末尾1分配动作归属数组11空空新建编号1加入set1[1]21空{1}set0为空新建编号2加入set1[1,2]30空{1,2}取set1队头1加入set0[1,2,1]40{1}{2}取set1队头2加入set0[1,2,1,2]最终 set1 为空set0 {1,2}答案 cnt 2归属数组 [1,2,1,2]和前面手动推的一致。再走一遍 s 0100步骤当前字符set0set1分配动作归属数组10空空新建编号1加入set0[1]21{1}空取set0队头1加入set1[1,1]30空{1}取set1队头1加入set0[1,1,1]40{1}空set1为空新建编号2加入set0[1,1,1,2]答案 2归属数组 [1,1,1,2]同样正确。3. 完整代码实现与关键参数解读3.1 参考实现C17我把代码写得直白一点方便照着理解而不是为了短而短。现实中打比赛可以精简但思维过程应该清晰。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; string s; cin n s; queueint q0; // 末尾为 0 的子序列编号集合 queueint q1; // 末尾为 1 的子序列编号集合 vectorint ans(n); int cnt 0; for (int i 0; i n; i) { if (s[i] 0) { if (!q1.empty()) { int id q1.front(); q1.pop(); ans[i] id; q0.push(id); } else { cnt; ans[i] cnt; q0.push(cnt); } } else { if (!q0.empty()) { int id q0.front(); q0.pop(); ans[i] id; q1.push(id); } else { cnt; ans[i] cnt; q1.push(cnt); } } } cout cnt \n; for (int i 0; i n; i) { if (i) cout ; cout ans[i]; } cout \n; } return 0; }这段代码提交到评测系统可以直接 AC。注意每组测试样例结束前不需要手动清空 q0、q1因为它们在 while 循环里是重新定义的局部变量每次都会重新构造。这也是为什么我建议把队列定义在 while 里面而不是全局变量能少很多清空操作。3.2 逐段解读核心代码代码分为三块输入与变量定义、主扫描循环、结果输出。变量定义部分ans 数组的长度是 n记录每个原字符串下标对应的子序列编号。cnt 负责给新子序列分配全局编号从 1 开始。这里有个容易搞错的地方题目要求输出编号从 1 开始有些人用 0 初始化后忘了加 1第一行和第二行就对不上所有编号少 1WA 得很冤枉。主扫描循环里判断条件没有太多可说的关键是理解 q0 和 q1 的同步变化当一个编号从 q1 取出来说明它原本是一个末尾为 1 的子序列现在并入了当前字符 0末尾变成 0所以马上 q0.push(id)。反之从 q0 取出来接上 1 之后末尾变成 1所以马上 q1.push(id)。这个过程保证了同一时刻每个 id 只会出现在一个队列里不会出现归属冲突。这种“从一边弹出、压入另一边”的操作本质上就是在维护子序列末尾状态的迁移。结果输出部分第一行输出 cnt它是当前测试样例的子序列总数。第二行按原顺序输出每个字符的子序列编号。输出格式上注意行尾不要多余空格。我写了个 if (i) cout 的小技巧比在每个字符后判断 i n-1 更简洁。3.3 复杂度分析时间复杂度是 O(n)。扫描每个字符时入队和出队各最多发生一次而 q0、q1 里的元素总数始终不超过 n。常数也很小就是两个队列的常规操作。空间复杂度也是 O(n)主要是 ans 数组和两个队列。实际最坏情况比如 s 全为 0每个字符都要新建子序列q0 最终会堆积 n 个不同编号q1 始终为空队列总元素数还是 O(n)。这道题的 n 上限是 2×10^5所以 O(n) 方案完全没问题。就算 n 去到 10^6这个算法照样能轻松跑过。需要注意别写复杂度 O(n^2) 的暴力方案比如每遇到一个字符就遍历所有子序列检查末尾状态。4. 常见问题与调试实录4.1 队列 vs 栈为什么我推荐队列实现很多题解用两个 queue也有用两个 stack 的还有人用 vector 模拟“空闲编号池”。我先说结论这道题里队列和栈都能 AC因为同类型子序列等价取哪个编号都不影响正确性。但我要推荐用队列而不是栈有实际原因。举一个例子s 1010。按队列写法遇到 1q0 为空新建 1 号进 q1遇到 0从 q1 取 1 号进 q0遇到 1从 q0 取 1 号进 q1遇到 0从 q1 取 1 号进 q0。归属全为 1正确。用栈写法遇到 1新建 1 号进栈 q1遇到 0从 q1 取出 1 号进 q0遇到 1从 q0 取出 1 号进 q1遇到 0从 q1 取出 1 号。也一样正确。区别只在多组子序列时。假设 q1 里有编号 {1,2}下一个字符是 0。队列会取 1栈会取 2。最后两个编号分别会接哪些字符可能会影响归属数组的具体形态但不会影响子序列总数。因为两个编号可接的字符类型完全一样本质上是同一个等价类。那我为什么更倾向队列因为调试时队列更符合直觉。你在纸上模拟这个贪心过程时通常会说“最早空闲的子序列来接力”队列的先进先出语义恰好匹配这种直觉。栈的后进先出则会让归属编号看起来“最近建的先用”虽然正确但打草稿时容易算乱。当然如果你已经习惯了栈写法也完全没问题。关键是别混着用一会儿队列一会儿栈自己都分不清到底取的是哪个。4.2 样例通过就完事边界情况自查清单我实际提交时遇到过几个比较典型的错误列出来给大家参照。第一种是答案编号从 0 开始。我没加 1 之前输出的行数和第二行的编号值整体差 1。当时样例输出可能不是 0 开头所以样例就会挂。排查思路很简单输出第一行 cnt 看看再手动验证几个位置。第二种是忘了把 id 从原队列弹出。如果只 push 到另一边、不 pop那么下一次遇到相反字符时队列里又出现同一个 id它会被再次分配。比如 s 11第一个 1 新建 1 号进 q1第二个 1 因为 q0 为空新建 2 号进 q1这时如果我只把 1 号复制到 q0 而没有从 q1 弹出来后续遇到 0 时 q1 里有 {1,2}q0 里也有 {1}就会导致编号 1 被两个队列重复持有构造出来的方案非法。这类 bug 通常在小样例上能跑出“归属数组里某编号重复出现且同时覆盖未交替的字符”肉眼比较难发现所以建议每次操作都严格遵循“从某个队列弹出再压入另一个队列”。第三种是忘记处理多个测试样例之间的向量残留。我建议将 ans、q0、q1 都定义在 while(T--) 内部这样每次重新构造天然没有残留问题。如果你习惯定义在外面一定要记得 clear。第四种是字符串输入混合了整数换行。cin 读取字符串时能自动跳过空白符所以直接 cin s 没问题。如果你用 getline就要小心上一行读 n 之后残留的换行符可能导致读入空串。这里推荐 scanf/printf 或 cin 的常规搭配不要混用 getline。我还整理了一个边界测试集自己在本地跑一遍就能覆盖大多数隐藏坑n 1s 0答案应为 1输出归属 1。n 1s 1答案应为 1输出归属 1。s 00答案应为 2归属可以 1 2。s 01答案应为 1归属 1 1。s 10答案应为 1归属 1 1。s 11答案应为 2归属 1 2。s 010答案应为 1归属 1 1 1。s 1010答案应为 1归属 1 1 1 1。s 1100答案应为 2归属可以 1 2 1 2。如果这些数据全过再提交基本稳了。4.3 打比赛时的实用建议说几个现场经验。第一这种构造类题目输出格式非常苛刻。很多人算法对了却因为行尾多一个空格或换行错误被 WA。虽然大多数评测系统能容忍行尾空格但稳妥起见输出前先写好“if(i) 空格”再输出数字能避免无谓罚时。第二如果你用的是 C记得加 ios::sync_with_stdio(false) 和 cin.tie(nullptr)。这道题数据量不大不加也能过但养成习惯后在后续题目里能帮你省很多不必要的超时。第三如果实在想不出来可以手写几个小样例用枚举暴力跑出最小子序列数再和自己的贪心结果对拍。对拍是最强的调试手段之一。我经常在本地写一个 O(2^n) 的枚举程序和小数据上的贪心程序对比输出能快速验证思路。第四也是我很想强调的竞赛题考察的是稳定的发挥而不是灵光一现。这种“思维题”之所以被放在 D 题位置就是因为有相当一部分选手只要时间够都能想通。关键不是智商而是平时有没有做过大量的“贪心 构造”训练能不能迅速识别“末尾状态唯一关键”这类抽象特征。5. 经验心得与延伸思考5.1 这类题在 Div. 3 里的定位Div. 3 的题目分布有个规律A 到 C 往往会给出比较明显的实现路径D 开始需要一层转化。Binary String To Subsequences 在 Round #661 的题目顺序里正好承担了“让新手体会思维题怎么做”的功能。它的难度设定并不高不需要任何高级数据结构甚至连排序都用不上。做它是为了训练三种能力从问题描述中提取最小充分特征这里就是“子序列末尾字符”。将问题转化为集合维护或贪心构造问题。快速用简单的反例验证直觉。我认为这三项能力比背一堆模板重要得多。很多选手刷几百道题以后遇到新题依然没思路问题往往不在题目难度而在“把问题翻译成可操作模型”这一步能力不足。这道题就是一个很标准的训练样本。5.2 从 D 题到思维训练我的一些体会我自己在多次比赛中体会到一件事所谓“思维题”解出来之后回看大部分都是把表面复杂的东西化简到只剩一个关键变量。Binary String To Subsequences 的关键变量就是末尾字符仅此而已。那么下一次遇到新的字符串构造题你是不是可以主动问自己当前状态的哪个信息是决定后续决策的是最后一个字符还是剩余可用次数还是某种最值带着这个习惯去看题思维题会变得亲切很多。再分享一个小技巧做这类题时不要在草稿纸上只画原串最好把“每一条子序列单独拎出来”画成一条轨道在上面填字符。比如 s 1100两条轨道分别是轨道一1(下1)、0(下3) 轨道二1(下2)、0(下4)这样视觉化后你会很直观地看到子序列之间是如何穿插的也就不容易再犯“连续段划分”的错误。我至今做很多字符串分配题都会下意识画轨道图。这道题的后续扩展也很有意思。如果把二进制字符串换成“括号序列”要求子序列是合法括号子序列做法会不一样如果把字符集扩大为 k 种颜色要求相邻颜色不同那么需要维护的就是 k 个集合。本质模型相似但都需要重新推导贪心策略和正确性证明。所以我建议读者别只抄代码最好能在这个题的基础上自己改一两个条件想一想收获会更大。我在实际写这题时踩过的最深的坑就是把编号从 0 开始连输出样例都懒得看直接提交结果 WA 了一发。后来学乖了第一行 cnt第二行编号数组这俩是对应关系先跑一遍样例再提交永远比上来就交更省时间。希望看到这里的你也能少走这一步弯路。
阅读完成 · 觉得有帮助？
区别)
