CF603A：翻转01串区间，最长交替子序列的结论与证明

CF603A《Alternative Thinking》是我做了几十道 CF 思维题之后，仍然愿意单独拿出来写一篇的题目。题干短到一句话：给你一个只含 0/1 的字符串，允许最多翻转一个连续区间（也可以选择不翻转），问翻转之后整个串里最长的交替子序列有多长。很多第一次见这道题的人，都会被"连续区间翻转"和"子序列"这两个词同时出现搞到不敢下手，又是区间、又是子序列，还要求最长，第一反应就是上 DP、上线段树、上贪心模拟。但当你真正把问题拆开之后会发现，整个答案只有一行：min(n, 原串块数 + 2)。这篇文章把我的完整思考过程、证明细节、代码实现和踩坑记录都写出来，适合刚接触 Codeforces 的入门选手，也适合想弄明白"结论题到底怎么想"的中级选手。

1. 先把题目审清楚，别让"子序列"这个词骗了你

1.1 原题到底在问什么

CF603A 的核心操作非常少。输入一个长度为n的 01 串s，你可以选择一个连续区间[l, r]，把区间里的所有字符取反（0 变 1，1 变 0）。可以选择不翻转，也就是把一个空区间看作合法的操作。翻转之后，你需要在新的字符串里找一个最长的"交替子序列"，也就是相邻字符都不同的子序列，形如0101...或1010...。

举个例子。s = 00101，如果翻转第 1 个字符，字符串变成10101，整个串本身就是交替的，所以答案是 5。如果不翻转，原串里能取到的交替子序列最长也只有 4，比如取0101。这里就能看出，翻转确实能带来收益。

这道题最迷惑人的地方在于：你只能翻转一段连续区间，但要求的是子序列。这两个概念放在一起，会让很多人误以为需要维护一个很复杂的结构，实际上并非如此。

1.2 子串、子序列、交替：三个概念一次分清

我见过不少人在评论区讨论这题时，说着说着就把"子序列"说成了"子串"。这两者差别非常大：

• 子串：原串里连续的一段。比如s = 00110，子串可以是011，因为它就是位置 2 到 4 的字符。
• 子序列：删除任意一些字符后，剩下的字符保持原来的相对顺序。它不要求连续。s = 00110中，010是一个合法的子序列，因为我可以取位置 1 的0、位置 3 的1、位置 5 的0。
• 交替：相邻两个字符不同，也就是不能出现00或11。

"最长交替子序列"本质上是一个很宽松的目标：它不要求你选出的字符在原串里紧挨着，只要你选的字符能形成0,1,0,1,...这种规律就行。宽松的目标往往意味着可以取到很多字符，甚至一整串。

1.3 为什么第一反应容易想复杂

如果你一上来就想着"我要枚举翻转哪个区间，然后对每种情况算最长交替子序列"，那复杂度直接起飞：枚举区间是O(n^2)，每次算子序列还要O(n)，在n到达十万级别时完全不可行。更麻烦的是，翻转一段区间会让中间一大段的字符整体取反，看起来好像破坏了所有局部关系，让人不敢轻易化简。

但请注意一个事实：取反操作对一段字符来说，内部相邻关系是不会变的。两个字符原本不同，同时取反后仍然不同；原本相同，同时取反后仍然相同。也就是说，翻转区间内部的"交替结构"其实原封不动。真正会被影响的，只有区间两端与外面相邻的那两个位置。这一个观察，就是解开整个题目的钥匙。

2. 把串压成"块"之后，答案就有了第一个抓手

2.1 什么是压缩表示

处理 01 串问题时，我常用的一个技巧是把连续相同的字符压缩成一个"块"。比如000111001，压缩成块序列就是0 1 0 1，完整写法是0^3 1^3 0^2 1^1。块的数量记为cnt，上面这个例子cnt = 4。

压缩后的性质非常干净：

• 每一块里的字符全部相同；
• 相邻两块的值必定不同；
• 整个串被划分成一段一段相互交替的块。

换句话说，不管一串是000还是1111，在"交替子序列"这个目标下，它内部所有字符都是等价的，因为从同一块里你最多也就能贡献一个字符给交替序列。

2.2 最长交替子序列恰好等于块数

这是一个非常核心的结论：原串的最长交替子序列长度 = 块数cnt。

先证明不会超过cnt。假设我从原串里选出了一个交替子序列。如果一个块里选了不止一个字符，因为这些字符值相同，且在整个块内部它们是连续出现的，那么它们在子序列里也必然相邻或几乎相邻，不可能中间插入其他块的值。一旦相邻，就会导致两个相同字符出现在交替序列里，违反交替规则。所以每个块最多只能贡献一个字符。最长交替子序列的长度，自然不可能超过块的数量。

再构造一个能达到cnt的方案：从每个块里随便挑一个字符，按原顺序排出来。因为相邻块的值不同，所以挑出来的序列一定是0,1,0,1,...这样交替的。于是下界也成立。

所以原题的第一步化简，其实是统计块数，而不是直接去算最长交替子序列。这个结论本身也解释了为什么这题不叫 DP 题，它根本不需要动态规划去枚举状态。

2.3 翻转在块层面的本质：只有端点在起作用

现在把翻转操作放到块视角下看。假设我翻转区间[l, r]，会经历两种情况：

第一种，区间完全覆盖了某些块。这些块整体取反后，块内字符依然全部相同，块与块之间的交替关系也不会被破坏。比如块序列是0 1 0，整体取反后变成1 0 1，仍然是交替的。所以中间这一段内部的块数不会因为翻转而改变。

第二种，区间的端点没有恰好落在块边界上，而是切进了某个块的中间。这时，那个被切开的块就变成了两半：一半没有翻转，继续保持原值；另一半被翻转，值变成相反的。举例来说，块是000，你翻转了中间那个0，它就变成0 1 0，一个块变成了三个块，块数净增 2。这就是翻转带来收益的唯一来源：在某个块的中间"切"出一条新边界，让原本相同的字符变成不同的字符。

同时，如果区间端点恰好落在块边界上，还可能发生"并块"：翻转后的第一个块或最后一个块，可能与外面的邻近块值相同，从而合并，导致块数减少。后面我会专门讨论这个损益关系。

3. 一次翻转为什么最多只能让块数 +2：完整推导

3.1 朴素想法的局限：先试几个例子找感觉

在给结论之前，先做几个小实验。

000，块数cnt = 1。翻转中间一个字符变成010，块数变成 3，增加了 2。

000111000，块序列是0 1 0，cnt = 3。翻转中间那个1，变成000 1 0 000，压缩后是0 1 0 1 0，块数变成 5，增加了 2。

0101，这是一个完全交替串，cnt = 4。你翻转任意一段，比如翻转第 2 个字符，得到0011，块数反而变成 2；翻转整个串得到1010，块数还是 4。无论如何，块数不会超过 4。

这些例子指向一个方向：翻转的收益最多是 2，而能不能拿到这 2 点收益，取决于原串里是否存在"可以切开的厚块"。

3.2 收益来自切缝，损失来自并块

把一次翻转看作两个端点的操作。区间左端点和右端点各能做两件事：

• 如果端点落在某个块的内部，它会把一个同值块切成两半，由于一半取反、一半不取反，中间出现新的交替分界，块数 +1。这个新边界我习惯叫"切缝"。
• 如果端点恰好落在块与块的边界上，且区间内第一个块整体取反后与区间外左侧块值相同，就会导致两个块合并，块数 -1。右端点同理。

一次翻转只有两个端点，所以最多产生两个切缝，最多产生两个并块损失。理论上净收益最多是 2。这里要注意的是，切缝和并块一般不会同时发生在一个端点上，因为如果一个端点切在块内部，那它左侧还存在同一个块的前半部分，与翻转后的后半部分值是相反的，不会并块。所以一次翻转能增加的块数，上限就是 2。

那能不能增加 2 以上呢？不可能。区间内部的完整块再怎么整体取反，相邻块的值差异依然保留，不会产生新的边界；只有两个端点能与外界交互。这是这道题最本质的上界证明。

3.3 构造 +2 的方法：找到厚块，切它一刀

上界是 2，接下来要确认这个上界真的可以达到。构造方法非常直观：只要存在一个长度至少为 3 的块，就翻转这个块正中间的一个字符，不要碰它的两个边界。

比如块是000，翻转中间那个0，块变成0 1 0，增加 2 个切缝，且左右两侧都不与相邻块发生合并。如果块更长，效果一样。块数从cnt变成cnt + 2。

如果不存在长度至少为 3 的块，但存在长度为 2 的块，也照样能构造。比如0011，翻转第 2 到第 3 个字符，得到0101，块数从 2 变成 4，同样加 2。这里的两个端点分别切在第一个块和第二个块的内部，收益对齐了。

那么什么时候完全无法增加？当原串完全交替，也就是每个块长度都恰好为 1 的时候。此时任意一块都薄得像纸一样，区间端点无论落在哪里，要么落在块边界上，要么落在字符串端点，根本无法在块内部切出新的边界。翻转一段区间只会让某些块合并，导致块数减少或保持不变。所以完全交替串的答案就是它本身，已经不可能再大了。

3.4 一个更直觉的表达：翻转前缀也能解释 +1 的收益

有时候我们不需要一次到位，可以先证明至少能加 1。假设原串里存在一处相邻相同，比如s[i] == s[i+1]。我翻转整个前缀[1, i]。

前缀内部整体取反，原本交替的相邻关系不会变；后缀本身也保持原样。唯一发生改变的是s[i]和s[i+1]这一对字符。翻转前它们相同，翻转后s[i]变成相反值，所以s[i]'与s[i+1]必然不同。原来的一个相同对，变成了一个交替边界。这就是一次翻转能够带来的最干净的 +1 收益。

进一步地，如果你能找到两个合适的切点，把它们放到同一段操作的左右两端，就能同时得到两个 +1，合成 +2。这正是前面讲的"切缝"思路。理解到这里，cnt + 2就不再是一个需要死记的公式，而是"两个端点各一次机会"的自然结果。

4. 公式落地与所有边界情况的一次性验证

4.1 完整公式：min(n, cnt + 2)

原因很简单：原串最长交替子序列已经能达到cnt，翻转最多把块数增加 2，所以上界是cnt + 2。但子序列再长也不能超过原串长度n，所以取一个min就得到最终答案。

实际统计块数时，不需要真的去划分字符串，一行循环就行：

• cnt从 1 开始；
• 每遇到一个s[i] != s[i-1]，就说明进入了一个新块，cnt++。

最后输出min(n, cnt + 2)。复杂度O(n)，额外空间O(1)。

4.2 典型输入逐项验证

下面这张表覆盖了绝大部分边界情况，我建议初学者对照着亲手模拟一遍，比单纯背代码有用得多：

看几个容易出问题的行。010本身已经完全交替，最长交替子序列就是整个串，长度 3，任何翻转都不能超过它。000111块数只有 2，翻转后最多到 4，也就是说你最多只能把最长交替子序列从 2 提升到 4，达不到 6，因为两个端点只能带来两次新增切缝。00101块数是 4，cnt + 2 = 6，但n = 5，所以答案封顶在 5，翻转一个字符让整个串变成完全交替即可。

4.3 为什么这个题的答案不是 DP

很多人会问：最长交替子序列不是可以用 DP 做吗？确实可以，在原串上求最长交替子序列，一个两状态 DP 就搞定了。但这题真正难的是"翻转一次之后"这个变数。如果用区间 DP 去枚举翻转区间，状态数会变成O(n^2)，高不可攀。

而通过块视角，我们发现翻转对最长交替子序列的影响，只是块数最多加 2。原本的动态规划问题被退化成了一个简单的计数问题，这就是思维题的精髓：不是让你硬算，而是让你找到操作背后的"不变量"和"局部变化"。

5. 代码实现：从公式到 O(n) 的几行

5.1 统计块数，而不是真的翻转

最终代码短得让人怀疑。核心就是统计cnt，然后套公式。不要真的去枚举区间、不要真的对字符串做取反，那是浪费算力。

有一个实现细节需要注意：cnt初始值设为 1 的前提是字符串长度至少为 1。CF603A 的题目约束里n不会为 0，所以可以放心写。如果你非要写一个万无一失的版本，可以在开头特判一下n == 0的情况，不过实际用不到。

5.2 C++ 实现与逐段解释

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; string s; cin >> n >> s; int cnt = 1; for (int i = 1; i < n; ++i) { if (s[i] != s[i - 1]) { ++cnt; } } cout << min(n, cnt + 2) << '\n'; return 0; }

这段代码里真正需要解释的只有cnt的统计逻辑。cnt = 1表示整个串至少是一块；从第 2 个字符开始扫描，只要当前字符和前一个不同，就说明进入了一个新块，计数器加 1。最后min(n, cnt + 2)把上界拦住，防止在完全交替串上输出超过 n 的错误答案。

5.3 Python 实现

def solve(): n = int(input()) s = input().strip() cnt = 1 for i in range(1, n): if s[i] != s[i - 1]: cnt += 1 print(min(n, cnt + 2)) if __name__ == "__main__": solve()

更 Pythonic 一点的写法是直接用生成器求和：

n = int(input()) s = input().strip() cnt = 1 + sum(s[i] != s[i-1] for i in range(1, n)) print(min(n, cnt + 2))

两种写法都一样，核心是理解sum(s[i] != s[i-1] for ...)统计的是相邻不同对的数量，也就是新增块的数量。

5.4 用暴力对拍确认结论

说实话，我第一次推出min(n, cnt + 2)这个结论时，自己也不是很放心，后来用暴力对拍验证了所有长度不超过 8 的 01 串，全部一致。这里把对拍代码贴出来，你可以直接复制跑一跑。

def longest_alt(t): dp0 = dp1 = 0 for ch in t: if ch == '0': dp0 = max(dp0, dp1 + 1) else: dp1 = max(dp1, dp0 + 1) return max(dp0, dp1) def brute_ans(s): n = len(s) best = longest_alt(s) for i in range(n): for j in range(i, n): t = list(s) for k in range(i, j + 1): t[k] = '1' if t[k] == '0' else '0' best = max(best, longest_alt(''.join(t))) return best def formula_ans(s): n = len(s) cnt = 1 + sum(s[i] != s[i - 1] for i in range(1, n)) return min(n, cnt + 2) for m in range(1, 9): for mask in range(1 << m): s = ''.join('1' if (mask >> i) & 1 else '0' for i in range(m)) assert brute_ans(s) == formula_ans(s), s print("all ok")

brute_ans里面有两个部分：longest_alt用 DP 计算一个串的最长交替子序列；枚举所有翻转区间并逐一更新答案。公式版只有两行。如果对拍能通过长度到 8 的所有串，这个结论在小范围内就是可靠的，再加上前面的数学推导，就可以放心提交了。

6. 关于 CF603A，高频翻车点集中复盘

6.1 把"子序列"当成"子串"来求

这是最经典的错误。如果你把题目理解成求"翻转后最长的交替子串"，你会发现答案完全不是min(n, cnt + 2)，而且样例可能直接过不去。交替子串要求连续，交替子序列允许跳着选，后者宽松得多，也因此才能和"块数"建立直接联系。审题阶段看到"subsequence"就要警惕，它不是"substring"。

6.2 试图真的去模拟翻转区间

我见过很多人的第一版代码是枚举所有[l, r]，然后真的把这段字符取反，再用 DP 求答案。这样在n很小时没问题，但到了n = 1e5的测试点，直接超时。而且模拟翻转会把你困在"区间内部变化"的细节里，很难跳出来想到"只需要看端点"。

真实竞赛里，这种暴力写法最多拿一点部分分，不是正解。建议以后遇到"区间取反/区间翻转/区间覆盖"的题，先问自己一句：这个操作对内部结构到底有没有影响？如果内部结构不变，那问题就简化为边界问题了。

6.3 输出忘记加min(n, ...)

cnt + 2在某些情况下会超过n，比如完全交替串0101，cnt = 4，cnt + 2 = 6，但答案显然不可能超过 4。如果忘记min(n, ...)，这类测试点会直接 WA。这个错误很隐蔽，因为小样例数据可能碰巧不超过 n，只有刻意构造完全交替串才会暴露。

提示：min(n, cnt + 2)的n不仅是为了防止输出非法答案，它还对应了一个事实——当原串几乎完全交替时，最多只要把串补成完全交替就到上限了，不需要再贪额外的 2。

6.4cnt统计错误

最常见的统计错误有两种。第一种是把cnt初始值写成 0，然后从i = 0开始扫描，最后发现n = 1时输出 0。第二种是把统计条件写成s[i] == s[i-1]，也就是统计的是"相邻相同对"，而不是"相邻不同对"。这样在000111上会得到 2 个相同对，但块数明明是 2 而不是 3。记住公式：块数 = 1 + 相邻不同对数。

另外还有一个值得注意的边界：n = 1时循环不执行，cnt保持 1，答案min(1, 3) = 1，完全正确。很多边界问题都会在这里暴露，所以提交前至少测一次长度为 1 的用例。

6.5 对"最多翻转一次"的理解偏差

原题是"最多"翻转一次，你可以选择不翻。如果强行理解成"必须翻转非空区间"，在完全交替串上答案会变差，比如0101翻哪里都不如不翻。虽然我印象里本题没有在这个点上卡人，但读题时把"最多"圈出来，能避免很多后续的混乱。

7. 从这一题里能带走的思维模板，比答案本身值钱

7.1 "任意区间操作"先想内部结构是否变化

CF603A 教给我的第一件事：不要看到区间操作就觉得要上数据结构。很多区间操作对区间内部是无影响的，真正的改变只发生在端点。比如把一段字符整体取反，内部相邻字符的相等关系完全不变。这时候把问题转换成"端点切缝"和"边界合并"，复杂度直接降一个维度。

这个套路不止这一题能用。类似地，区间加、区间翻转、区间异或，只要操作对区间内任意相邻对的"关系"不敏感，都可以先压缩再分析。

7.2 上界要证明，构造要落地

结论题最怕的是"猜一个公式然后碰运气"。min(n, cnt + 2)这个公式看着简单，但它是怎么来的？上界来自于"一次操作只有两个端点，每个端点最多贡献一个切缝"；下界来自于"存在厚块时切中间字符可以拿到 +2"。只有双向都成立，才敢放心提交。

如果你在赛场上推出一个结论，但构造不出达到上界的例子，那说明结论可能有问题。这时候最快的验证方法就是暴力对拍：枚举所有小规模输入，看看公式和暴力答案是否一致。对拍不是浪费时间，它是让你在刷题时少犯错的最有效工具。

7.3 把"压缩"当成 01 串题目的默认思路

连续相同字符压缩成块，这个技巧在大量 01 串题目里都有用。遇到涉及交替、翻转、连续段的题，先压缩，再观察块与块之间的关系。CF603A 里块数直接决定了最长交替子序列，而翻转的作用被压缩成"最多新增两个块边界"，这就是压缩带来的清晰度。

我在实际写题中还有一个习惯：当公式推完但不确定边界时，拿长度 1 到 5 的所有串快速手算一遍，再跑对拍。这个习惯帮我避免了很多次因为边界条件翻车的情况。CF603A 的坑不多，但那种"答案原来是一行公式"的震撼感，我到现在还记得。后来再遇到更复杂的区间操作题，我都会下意识问自己一句：这次真正被改变的地方，到底有几个？很多时候，答案就藏在那两个端点里。