CF603A《Alternative Thinking》是我做了几十道 CF 思维题之后仍然愿意单独拿出来写一篇的题目。题干短到一句话给你一个只含 0/1 的字符串允许最多翻转一个连续区间也可以选择不翻转问翻转之后整个串里最长的交替子序列有多长。很多第一次见这道题的人都会被连续区间翻转和子序列这两个词同时出现搞到不敢下手又是区间、又是子序列还要求最长第一反应就是上 DP、上线段树、上贪心模拟。但当你真正把问题拆开之后会发现整个答案只有一行min(n, 原串块数 2)。这篇文章把我的完整思考过程、证明细节、代码实现和踩坑记录都写出来适合刚接触 Codeforces 的入门选手也适合想弄明白结论题到底怎么想的中级选手。1. 先把题目审清楚别让子序列这个词骗了你1.1 原题到底在问什么CF603A 的核心操作非常少。输入一个长度为n的 01 串s你可以选择一个连续区间[l, r]把区间里的所有字符取反0 变 11 变 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 0cnt 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[i1]。我翻转整个前缀[1, i]。前缀内部整体取反原本交替的相邻关系不会变后缀本身也保持原样。唯一发生改变的是s[i]和s[i1]这一对字符。翻转前它们相同翻转后s[i]变成相反值所以s[i]与s[i1]必然不同。原来的一个相同对变成了一个交替边界。这就是一次翻转能够带来的最干净的 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 典型输入逐项验证下面这张表覆盖了绝大部分边界情况我建议初学者对照着亲手模拟一遍比单纯背代码有用得多原串ncnt公式答案一种最优翻转方式0111不用翻00212翻第一个字符变成10000313翻中间字符变成010010333无论怎么翻都不超过 30011424翻第 2 到第 3 位变成0101000111624翻第 3 到第 4 位得到00101100101545翻第 1 位变成101011001434翻第 1 位变成0101看几个容易出问题的行。010本身已经完全交替最长交替子序列就是整个串长度 3任何翻转都不能超过它。000111块数只有 2翻转后最多到 4也就是说你最多只能把最长交替子序列从 2 提升到 4达不到 6因为两个端点只能带来两次新增切缝。00101块数是 4cnt 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比如完全交替串0101cnt 4cnt 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 的坑不多但那种答案原来是一行公式的震撼感我到现在还记得。后来再遇到更复杂的区间操作题我都会下意识问自己一句这次真正被改变的地方到底有几个很多时候答案就藏在那两个端点里。