企业官网建设流程全解析

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; vector<int> ans(n); vector<int> 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，建议遇到这类思维题先别急着看题解，拿样例手推几遍，再用交换论证检验自己的贪心，收获会大得多。