Codeforces Round #661 (Div. 3) 的 D 题 Binary String To Subsequences标签写得很直白思维。我一直觉得这个标签比很多题的贪心构造更准确因为题面绕样例也有一点迷惑性但把包装撕掉之后核心其实就一句话把 01 串按原顺序拆成尽量少的子序列每个子序列内部必须 0 和 1 交替。这篇文章我会从题目理解开始讲到贪心为什么成立、代码怎么写、容易踩的坑最后再聊聊这类题的通用解法。无论你是刚开始打 CF 的选手还是想加强构造题思路的人这篇应该都能给你一些启发。1. 题面到底在说什么子序列、拆分与交替限制1.1 子序列不是子串最关键的第一认知第一次读题的时候很多人容易把子序列看成子串这两个概念在字符串题里是完全不同的。子串原串里连续的一段。比如 s 01001子串 100 就是取第 2 到第 4 个字符。子序列从原串里挑一些字符保持它们在原串中的相对顺序但不需要连续。比如 001 就是 01001 的一个子序列因为可以跳过原串第 2 个字符 1。这道题说的拆分成若干子序列意思是把原串的每个字符都分配到某个子序列里一个字符不能重复使用也不能被漏掉。也就是说最后不能像普通的找最长交替子序列那样扔掉一些字符而是要把整个串全部覆盖。然后还有个限制每个子序列内部要交替。交替指相邻的两个字符不同也就是每个子序列必须是 0101... 或者 1010... 这种形式。同一子序列里的两个 0 之间必须隔至少一个 1两个 1 之间必须隔至少一个 0。题目要求最小化子序列的数量并输出每个字符被分配到了哪个编号的子序列。这个拆分 覆盖 交替的组合决定了暴力做法会非常复杂因为分配方案是指数级别的。但理性分析之后会发现整个过程只需要维护一个很小的状态。1.2 为什么要按原串顺序编号先手推一个简单样例很多同学卡住不是因为不会贪心而是不知道输出到底是什么东西。题目要求输出一个长度为 n 的数组 pos[i]表示第 i 个字符分到了第几个子序列。子序列的编号从 1 开始编号顺序可以任意只要能还原出一个合法的拆分方案即可。举个例子s 000111。如果只是随便拆我们可以这么做第 1 组位置 1 的 0 和位置 4 的 1组成 01。第 2 组位置 2 的 0 和位置 5 的 1组成 01。第 3 组位置 3 的 0 和位置 6 的 1组成 01。所以答案是 3输出编号数组就是 1 2 3 1 2 3。这里注意第 3 个字符虽然和第一个字符一样都是 0但它所在的子序列编号是 3不是 1。因为我们不能把三个 0 塞进同一个子序列不然子序列内部就会出现 000 这种连续相同的情况。再试一个稍微复杂点的例子s 001011。你会发现答案不是 3而是 2第 1 组位置 1 的 0、位置 3 的 1、位置 4 的 0、位置 6 的 1组成 0101。第 2 组位置 2 的 0、位置 5 的 1组成 01。输出编号1 2 1 1 2 1。从这个例子能看出一个子序列可以穿插使用多个相同字符只要中间有相反的字符隔开就行。所以每个相同字符必须单开一组这个直觉是错的正确答案往往比这种直觉估计的小。2. 贪心的直觉与正确性为什么能接就接2.1 从末尾字符看所有已完成组的状态如果把所有子序列看成正在生长的链那么判断一个新字符能不能接上某个子序列只看这个子序列当前最后一个字符是什么。末尾是 0 的组只能接 1末尾是 1 的组只能接 0。这就带来一个非常重要的简化我们根本不需要关心每个子序列之前长什么样只需要知道当前有哪些组的末尾是 0哪些组的末尾是 1。处理到某个新字符时如果它是 0那么能接它的只有一个条件存在末尾是 1 的组。如果存在随便挑一个把 0 加到它后面这个组的末尾就变成 0 了。如果不存在说明所有组的末尾都是 0那就必须新开一组新组末尾也是 0。同理如果新字符是 1就看是否存在末尾是 0 的组。这个过程特别像把字符卖给合适的组一个组是 0 结尾还是 1 结尾决定了它的可用性。我们要做的就是维护这两类组的清单。2.2 交换论证局部最优为什么能成为全局最优这一步往往是思维题重点。为什么能接就接一定最优为什么不能出现这次接了反而导致后面需要更多组的情况可以用交换论证来证明。假设当前正在处理字符 c并且存在一个末尾字符不等于 c 的旧组 A。如果某个最优解选择把 c 放进新组 B组数会增加 1。现在我们改成把 c 放进 A那么 A 的末尾就变成了 c而 B 完全不需要存在。关键在于A 变成以 c 结尾之后它跟 B 在未来能接什么这个问题上是完全等价的。无论是 A 还是 B之后都只能接不等于 c 的字符。所以把这个字符从 B 挪到 A不会让任何后续字符更难安放只是减少了一个组或者让某个 c 结尾的组多了一个可选项。重复这个交换过程总能得到一个不劣的解而且这个解满足能接就接。所以贪心算法的结果就是最优解的组数。这个论证在正式题解里叫交换论证是证明贪心构造问题常用的方法。很多 CF 思维题看起来是靠直觉但竞赛选手在短时间内能判断贪心正确靠的往往就是这样简洁的推理。2.3 一个常见的错误直觉答案等于某个字符的出现次数我见过不少人对这道题的答案是出现次数最多的字符的数量理由是每个相同字符之间必须被不同字符隔开所以相同字符不能全塞进一个组。这个结论对一部分数据成立比如 s 000111出现最多的字符出现 3 次答案确实是 3。但整体上并不对。取 s 001011 再来看1 出现了 3 次是最多的字符但答案只有 2。因为三个 1 可以分布到两个交替链里第一个链 0101 里面有第 1、3、4、6 个字符其中包括两个 1第二个链 01 里面有一个 1。同一个子序列里两个 1 中间被 0 隔开了所以合法。如果你想用一个简单的下界判断答案正确的角度不是出现次数而是某种递推扫描过程里的同时存在多少个以 0 结尾的组、以 1 结尾的组。这也就是贪心过程里真正会动态变化的东西。3. 代码实现两个栈维护末尾集合3.1 数据结构的选择过程从暴力扫描到双栈知道贪心策略之后第一版代码很容易写成这样开一个数组 last[i] 表示第 i 组当前末尾是什么字符然后每次遇到一个新字符线性扫描所有组找第一个末尾字符不同的组接上去。这样做虽然正确但最坏情况下组数可能达到 n总复杂度是 O(n^2)。当 n 到 2e5 级别的时候会稳稳超时。所以要更快地找到一个可用组。注意条件里说的是一个并不是特定哪一个。因为所有末尾是 0 的组对于下一个要接的 1 来说完全等价所有末尾是 1 的组对于下一个要接的 0 来说也完全等价。那我们只需要维护一个容器里面装着当前所有末尾是 0的子序列编号。一个容器里面装着当前所有末尾是 1的子序列编号。遇到 0 时如果末尾是 1的容器非空就随便取出一个编号把 0 接上去然后把这个编号放进末尾是 0的容器里否则新建一个组放进末尾是 0的容器。由于任意一个可用编号都行所以用栈就够了后进先出不会影响正确性。用两个 vector 当栈是最直接的写法。3.2 C 完整代码#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; vectorint ans(n); vectorint st0, st1; // st0: 末尾是 0 的组编号st1: 末尾是 1 的组编号 int cnt 0; // 当前已经开了多少个组 for (int i 0; i n; i) { if (s[i] 0) { if (!st1.empty()) { int id st1.back(); st1.pop_back(); ans[i] id; st0.push_back(id); } else { int id cnt; ans[i] id; st0.push_back(id); } } else { if (!st0.empty()) { int id st0.back(); st0.pop_back(); ans[i] id; st1.push_back(id); } else { int id cnt; ans[i] id; st1.push_back(id); } } } cout cnt \n; for (int i 0; i n; i) { if (i) cout ; cout ans[i]; } cout \n; } return 0; }代码看起来很短但实际信息量不小。关键是理解两个栈之间的搬运取出来的组一定是另一个末尾状态的接上当前字符后它的末尾状态就切换了所以要放到另一边去。这有点像把一张卡片从一个盒子移动到另一个盒子盒子里存的是组编号不是字符本身。3.3 Python 完整代码与注意点import sys def solve() - None: 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]) idx 1 s data[idx].strip() idx 1 ans [0] * n st0 [] # 末尾是 0 的组编号 st1 [] # 末尾是 1 的组编号 cnt 0 for i, ch in enumerate(s): if ch 0: if st1: gid st1.pop() ans[i] gid st0.append(gid) else: cnt 1 ans[i] cnt st0.append(cnt) else: if st0: gid st0.pop() ans[i] gid st1.append(gid) else: cnt 1 ans[i] cnt st1.append(cnt) out.append(str(cnt)) out.append( .join(map(str, ans))) sys.stdout.write(\n.join(out)) if __name__ __main__: solve()Python 注意点用 sys.stdin.read() 一次性读入避免多次调用 input() 在数据量大时拖慢速度。list 的 pop() 默认从末尾弹出一个元素正好当栈用。数据里有多个测试用例记得重置 st0、st1 和 cnt。两个版本的复杂度都是 O(n)空间也是 O(n)。对 Codeforces 的 2e5 数据量来说完全够用。4. 容易踩坑的地方与边界测试4.1 输出格式数量、编号、换行这道题输出有两行。第一行是子序列的数量 k第二行是 n 个数表示每个位置分配到哪个组。我第一次交的时候因为少输出一个换行被 Presentation Error 过后来学乖了所有测试样例的输出之间不要有多余空格行尾可以有一个换行但不要多输出空行。写完代码可以本地跑一遍样例肉眼对比一下格式。还有一个容易忽略的点组编号必须从 1 开始连续编号到 k。编号顺序虽然没有硬性要求但如果你自己实现的是先给所有 0 编一组编号再给所有 1 编另一组编号就可能在编号连续性上出问题。上面的双栈写法每次新建组都用 cnt所以天然连续。4.2 边界数据全 0 串、全 1 串、交替串构造题最怕边界情况想不全。这道题有几个容易测的极端数据。s 0 或 s 1只有一个字符不需要交替答案就是 1输出 1 和 1。s 000三个 0 不能进同一组答案是 3。每个组只有一个 0。s 111同理答案是 3。s 010101整串本身已经交替可以全部放进一组答案是 1。s 00110011答案是 2。分组方式可以是第一组取每个 01 对第二组取每个 01 对输出会交替出现 1 和 2。把这些边界数据跑一下能帮你快速发现 bug。比如如果实现时忘记把编号从 st1 转移到 st0全 0 串会输出错误结果。4.3 写一个验证函数贪心做完后如何自检很多时候题目 AC 了但你不确定自己的构造到底合不合法。一个很实用的习惯是本地写一个 check 函数把答案重新还原成若干组然后检查每组是否满足交替。验证逻辑很简单按 ans[i] 把每个字符归类到对应的组。对每一组遍历内部字符如果相邻两个字符相同就说明构造非法。用 C 或 Python 都可以写。这个 check 函数不用提交纯粹给自己吃定心丸。特别是自己改了编号分配逻辑之后跑一遍全随机的小数据比肉眼检查可靠得多。我当时做这道题的时候就是先写了贪心再用 check 函数随机生成了几万组小数据对拍确认没有问题之后才敢放心提交。4.4 为什么随便取一个可用组不会破坏后续有人可能会问栈里的编号顺序会影响答案吗回顾 2.2 的证明所有末尾字符相同的组在未来能接什么这个维度上是完全等价的。所以从栈里取出哪一个编号都不影响之后任何字符的选择。唯一可能影响的是最终输出数组长什么样但题目只要求合法不要求唯一。这也是为什么可以用栈而不是必须用队列。如果用队列效果也没问题只是多写几行代码。栈更简洁因为在逻辑上后进入的组先被复用没有任何副作用。5. 这题的思维在哪同类问题与升级方向5.1 一个更好玩的模型双盒子交换如果你打过不少构造题可能会发现这道题本质上是一个双盒子交换模型。想象有两个盒子Box0 里放着所有当前末尾是 0的组编号。Box1 里放着所有当前末尾是 1的组编号。遇到 0 时从 Box1 里摸一个编号出来用完放回 Box0遇到 1 时从 Box0 里摸一个编号出来用完放回 Box1。没有可摸的编号时就新建一个组把新编号放进对应的盒子。这个模型非常像括号匹配里的栈操作也像某些维护状态集合的贪心题。一旦你把题目转化成这种状态搬运模型后面所有操作都变得机械而可靠。这也是思维题最常见的套路之一把看似复杂的分配过程压缩成状态机式的小操作。5.2 如果字符种类不是 0/1而是多种字符怎么办一个自然的扩展如果字符串里不是只有 0 和 1而是有很多种字符要求每个子序列的相邻字符也不同该怎么处理思路是一样的。对每种字符 c 开一个容器 st[c]里面存所有当前末尾是 c的组编号。遇到字符 ch 时在除了 ch 之外的所有容器里找一个非空容器取出编号然后把该编号放进 st[ch]。如果所有其他容器都为空就新建组。差别在于如果字符集很小比如 26 个字母每次扫一遍其他容器判断有没有货复杂度是 O(26n)完全可行。如果字符集很大可以用一个集合维护所有非空容器的字符种类每次只需要从集合里随便拿一个种类操作仍是 O(1) 摊销。这个扩展能帮你加深理解核心不在于两个栈而在于维护若干状态且同状态的组彼此等价。题目从 0/1 变成多字符只是状态从 2 个变成更多个贪心骨架没变。5.3 后续可以做的同类练习题如果你觉得这道题很有意思想顺着这个方向练我建议重点练两类题第一类是序列拆分类构造题比如把一个串拆成若干合法子序列要求最小化数量。这种题的关键都是找组会处于哪些状态再贪心地复用状态。第二类是状态维护 双栈/多队题表面上和数据机构有关实际核心是贪心证明。你能在题解里看到任意一个可用即可状态等价这类字眼就说明可以套用这个思维。做题不要只看 AC 数量我自己的体会是把一道题从暴力到优化、从正确性证明到边界测试完整走一遍比刷三题都管用。最后分享一点个人经验我一开始做这道题第一版写的是线性扫描找可用组交了之后才意识到 O(n^2) 会超时。后来复盘发现真正让我进步的不是那个用栈优化的代码而是想清楚为什么所有同末尾的组等价的那几分钟。如果你也是刚开始接触 CF建议遇到这类思维题先别急着看题解拿样例手推几遍再用交换论证检验自己的贪心收获会大得多。