1. 题意精读小苯在染什么第六届传智杯程序设计国赛B组T4小苯的字符串染色这道题在考场上卡了我一阵子。题目本身不长但真正把操作次数想清楚需要一点经典的边界思维。如果你准备打传智杯这类偏应用的算法竞赛这道题的思考路径非常值得单独拿出来复盘。先说清楚题意我们手里有一个长度为 n 的01字符串字符 0 和 1 可以理解成两种颜色。每次操作可以任选一个连续区间把区间内所有字符的颜色全部取反0 变成 11 变成 0。要求用最少的操作次数把整个字符串变成全 0。传智杯B组T4的难度定位一般是“有一定思维量但代码实现非常短”的题目这道题就是典型代表正解核心代码不超过十行难的是你怎么想到那十行。我在考场上的第一反应是这是个区间翻转问题。因为它和常见的“区间整体赋值”不一样取反操作会让区间内部原本连续的 0 在取反后变成 1所以直接用贪心扫一遍“把当前 1 段翻掉”并不一定最优。举个简单例子01010如果见到第一个 1 就翻 [2,2]字符串变成 00010再翻 [4,4] 变成 00000看似 2 次搞定。但另一个串 0101010如果还用这种“见 1 就翻单点”的贪心需要 3 次而实际上可以先翻 [2,6]再翻 [4,4]我们后面会算这个串其实 2 次就能解决。这里的反直觉点正是整道题的题眼。1.1 题目定位与考场直觉把传智杯B组T4放在整套题里看它属于“思维题偏算法实现”的类型。考场上你不需要写复杂的数据结构也不需要套高级算法模板但需要具备一种能力把对字符串的区间操作抽象成另一种更容易统计的数学对象。我在读完题后先列了几个已知信息字符串只包含 0 和 1所以任何一次区间取反影响的是区间内所有字符的“颜色属性”。目标状态是固定的全 0。操作区间可以任意长甚至可以选整个串。要求的是最小操作次数而不是方案数。这里最关键的直觉是如果只关注“当前字符串长什么样”你会被 2^n 种状态淹没但如果把目光放到“相邻两个字符之间是否相同”上取反操作的影响会变得非常局部。这个转变我后面会详细展开。1.2 输入输出与操作定义按这类题目的常规输入格式第一行通常是一个正整数 n表示字符串长度第二行是一个长度为 n 的字符串 s字符只包含 0 和 1。输出一个整数表示最少操作次数。例如输入 n4s1111输出 1。因为直接选择整个区间 [1,4] 取反一次就变成 0000。输入 n3s010输出 1。选择区间 [1,3] 取反得到 101不对正确做法是选择 [2,2] 取反得到 000。这说明单点操作在有些情况下就是最优解。输入 n5s01010输出 2。先选区间 [2,4] 取反01010 变成 00100再选区间 [3,3] 取反变成 00000。这比逐个翻 1 要少一次。小细节操作区间的下标从 1 开始还是从 0 开始不影响算法但写代码时要注意循环边界和字符串下标习惯避免差一错误。1.3 一个必须牢记的观察我做完这道题后最大的体会是区间取反操作有一个“内部不变”的性质。什么意思一个区间内部如果原本就存在颜色变化的边界比如相邻两个字符一个是 0 一个是 1那么区间整体取反之后这两个字符依然不同只是颜色交换了。换句话说区间内部的“相邻不同”关系不会因为取反而消失或新增取反改变的只有区间两个端点与外部相邻位置的关系。这个观察看起来平淡但它直接决定了答案只和“边界数量”有关和字符串具体的排列没有太大关系。想明白这一点题目就完成了一大半。2. 从暴力到正解的思维推导2.1 为什么不直接BFS我理解题意的第一版思路是搜索把每个字符串看成状态每次枚举所有区间做一次取反然后广搜找最短步数。这个思路对于 n10 的小数据完全可行但传智杯T4的 n 不可能这么小一旦 n 到几千状态数是指数级的BFS 瞬间爆炸。还有同学会想到动态规划比如用 dp[i][j] 表示前 i 个字符已经全 0 且最后一次操作覆盖到 j 的最小次数。这确实能做但状态定义很容易绕进去而且这道题的操作和“当前后缀状态”之间的关系不够直观DP 写起来繁琐还容易漏状态。实际上这种“区间取反求最少次数”的题通常有一个共同套路把连续相同字符压缩成一个段然后只关心段与段之间的边界。一旦你从“字符视角”切到“边界视角”DP 反而是多余的。2.2 把“染色”看成“取反”题目叫“字符串染色”但操作本质是取反0 染成 11 染成 0。为什么要强调这个因为如果你把它理解成“把一段染成某个颜色”你可能会想成覆盖操作那问题会变得非常简单全串染 0 一次就完成没什么可考的。正是因为取反会保留区间内部的相对差异问题才变得有趣。取反操作的另一个特点是连续操作两个相同区间会互相抵消所以最优解里不会出现对同一个区间做偶数次取反的情况而连续两次取反不同区间如果它们的覆盖关系可以调整往往也能合并或优化。因此在讨论最少次数时我们只需要考虑每次操作都能“减少一些东西”的贪心方案而不是盲目枚举状态。2.3 边界这道题的真正主角我在纸上画了几个例子之后发现真正和被取反区间相关的不是“哪些位置是 1”而是“相邻位置颜色是否不同”。举个例子s 001100逐对比较0-0 相同0-1 不同1-1 相同1-0 不同0-0 相同。共有 2 个相邻不同点。s 01010相邻不同点有 4 个。s 111相邻不同点有 0 个。目标状态 000 的相邻不同点也是 0 个。于是问题可以重新描述为初始字符串有一组“边界”每次区间取反最多只能改变两个边界区间左端和右端区间内部的边界数量不变最终目标要求边界全部消失。那么最少操作次数显然不会少于“边界总数的一半”。这个“至少”的直觉很关键它把最优化问题转化成了下界证明问题。但这里有一个隐含问题111 的相邻不同点是 0可它明明需要 1 次操作这不就让“至少 0 次”下界失效了吗我一开始也在这里卡住。解决方法是引入“虚拟边界”把字符串的左右两端都想象成颜色 0。于是 111 的左端虚拟边界是 0-1 不同右端虚拟边界是 1-0 不同总边界数是 2答案下界就变成了 1和真实答案吻合。加虚拟边界这个操作在区间问题里非常常见。它本质上是把“串外”也定义成一个固定颜色这样任何取反区间都会在左右两个端点处与外部形成新的相邻关系边界变化紧紧贴着操作端点内部的自由边界不影响统计。3. 核心结论与数学证明3.1 虚拟边界定义先给出严谨定义。设字符串 s 长度为 n我们额外规定 s[0] 0s[n1] 0。对于位置 i 从 0 到 n如果 s[i] ! s[i1]就称这里有一个“边界”。注意这里 s[0] 和 s[n1] 是虚拟字符不是真实字符。于是全 0 串的边界数为 0。全 1 串的边界数为 2左虚拟边界和右虚拟边界各一个。01010 的边界数s[0]0 与 s[1]0 相同0-1 不同1-0 不同0-1 不同1-0 不同s[5]0 与 s[6]0 相同共 4 个边界。001100 的边界数虚拟左边界相同0-1 不同1-0 不同虚拟右边界相同共 2 个边界。这个定义可以把所有情况统一起来也方便我们证明。3.2 答案公式推导一次区间取反操作选择区间 [l, r]会对哪些边界产生影响注意区间内部的相邻关系取反后依然“不同性”不变所以内部边界数量不变。变化的只有两个位置l-1 与 l 之间的相邻关系因为 s[l] 取反了s[l-1] 没取反。r 与 r1 之间的相邻关系因为 s[r] 取反了s[r1] 没取反。也就是说一次操作最多影响两个边界最少也可能影响 0 个边界比如取的区间刚好和前后状态一致取反后没有改变不同性。但从减少边界的角度看一次操作最多让边界总数减少 2。最终目标边界数是 0初始边界数记为 cnt那么操作次数一定有下界ceil(cnt / 2)。再证明这个下界可以达到。我们把 cnt 个边界按照从左到右的顺序编号为第 1、2、...、cnt 个。取第 1 个边界和第 2 个边界令操作区间为“这两个边界之间的真实字符区间”进行一次取反。这次操作会同时消除这两个边界并且不会影响其他边界。为什么因为第 1 个边界和第 2 个边界之间的字符被整体取反区间左端与左侧外部的关系被修正区间右端与右侧外部的关系也被修正而区间内部原本可能存在的边界在取反后依旧存在但由于我们取的是“相邻两个边界之间”区间内部恰好没有其他边界。所以一次操作干净利落地消掉两个边界。随后再取剩下的第 1 个和第 2 个边界重复操作直到没有边界。如果 cnt 是偶数需要 cnt/2 次如果 cnt 是奇数最后一次只剩一个边界这时选择从该边界到字符串某一端的区间取反一次就能消掉它。因此总次数是 ceil(cnt / 2)。所以最终答案就是虚拟边界总数的一半向上取整即答案 (cnt 1) / 2用整数除法表示就是 (cnt 1) / 2。如果你不想引入虚拟边界也可以这样写统计从第一个字符到最后一个字符之间的相邻不同次数记为 c但注意最左侧如果从 0 开始已经计算实际上我们写代码时统一用“上一个字符”初值为 0来遍历整个串如果当前字符不等于上一个字符cnt遍历结束后如果最后一个字符不是 0 再 cnt。这个写法最不容易漏。3.3 构造性上界如何配对边界上面证明里提到的配对操作我建议你在纸上手动推一遍尤其是 01010 这个串。01010 的虚拟边界位置分别在位置 1 和 2 之间0-1 不同位置 2 和 3 之间1-0 不同位置 3 和 4 之间0-1 不同位置 4 和 5 之间1-0 不同共 4 个边界配对为第 1 和第 2 个操作区间是 [2,2]再配对第 3 和第 4 个操作区间是 [4,4]。这样需要 2 次是我们之前见过的答案。也可以换一种配对第 1 和第 4 个配对操作区间 [2,5]我试着操作取反 [2,5]01010 变成 00101边界变成 2 个再操作 [3,5] 变成 00110这样更乱。所以最优配对方式是“相邻边界两两配对”也就是从左到右相邻边界之间的区间直接取反。这种配对方式保证每次消除的是两个连续边界不会引入新的间隔。你可能会有疑问为什么不能一次消除超过两个边界因为区间内部的边界取相反转后仍然存在不会消失所以一次操作无法直接影响内部边界。这个“区间内部边界不可消除”的特性是本题最核心的限制条件。理解了这个你就能明白为什么答案不是“连续 1 段的数量”而是“边界数的一半”。3.4 为什么不是“连续1段数量”我最初写了一个贪心统计连续 1 的段数每段翻一次遇到全 1 串反而要翻一次答案就是连续 1 段数。这个做法能过一部分样例但错在“翻单点 1 段”并不是最优。看一个反例s 10101。连续 1 段有 3 段按段数答案是 3。但实际最优答案是多少用虚拟边界统计s[0]0s[1]1 边界1-0 边界0-1 边界1-0 边界0-1 边界s[6]0 与 s[5]1 边界一共 5 个边界我数一下位置0虚拟0和s11不同1s11和s20不同2s20和s31不同3s31和s40不同4s40和s51不同5s51和虚拟右0不同6实际是 6 个边界。答案 6 / 2 3。好像还是 3不构成反例。换个例子s 10001。连续 1 段只有 1 段段数答案是 1虚拟边界左虚拟0与s11不同1s11与s20不同2s20与s30相同s30与s40相同s40与s51不同3s51与右虚拟0不同4答案 4/2 2。而实际操作翻 [2,4] 把 000 变成 111串变成 11111再翻 [1,5] 变成 00000确实需要 2 次。所以段数贪心低估了答案。这个例子非常好地说明了“只翻 1 段”不是最优的中间连续 0 段在取反后会变成 1等于你把一个 1 段拆成两半甚至更多 1 段后面的操作次数不会减少反而可能增加。而借助边界配对我们能精确控制每次操作让每一步都恰好消掉两个边界保证最终步数等于理论下界。4. 代码实现与复杂度分析4.1 最简写法边读边算由于我们只需要统计边界数量根本不需要把整个字符串存下来。读入 n 之后可以一个字符一个字符地处理维护一个变量 last 表示上一个字符的颜色。为了处理左虚拟边界last 初始化为 0。伪代码逻辑如下初始化 last 0cnt 0。循环 n 次每次读入一个字符 ch如果 ch ! lastcnt。last ch。循环结束后如果 last ! 0cnt。输出 cnt / 2。这里有一个细节题目给的 n 是字符串长度但实际处理时不需要依赖 n 的数值只需要知道读入 n 便于控制循环。如果题目有多组测试数据注意每组都要重置 cnt 和 last。4.2 完整参考代码下面是一份可以 AC 的 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 0; char last 0; // 左虚拟边界想象字符串左边还有一个0 for (int i 0; i n; i) { if (s[i] ! last) { cnt; } last s[i]; } // 右虚拟边界如果最后一个字符不是0说明和右边假想的0不同 if (last ! 0) { cnt; } cout cnt / 2 \n; return 0; }这段代码的时间复杂度是 O(n)空间复杂度 O(1)存字符串也只用了 O(n)如果你用流式读入可以做到 O(1) 额外空间。对于传智杯B组T4的数据范围来说这个效率非常充裕。如果你希望彻底省掉字符串数组可以改成下面这种写法#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; char last 0; int cnt 0; char ch; for (int i 0; i n; i) { cin ch; if (ch ! last) { cnt; } last ch; } if (last ! 0) { cnt; } cout cnt / 2 \n; return 0; }两种写法都行。第一种更容易读第二种更能体现“流式处理”的思路。如果题目要求输入输出文件重定向自己在本地调试时加上 freopen 就行。4.3 目标变体的扩展代码如果题目把目标改成“变成全 1”答案一样吗我的结论是完全一样。因为目标全 0 和全 1 之间只差一次整体取反而整体取反等价于选择区间 [1,n] 操作一次。如果全 0 的最优解是 k 次那么先整体取反一次再按照原来的策略操作就能用 k1 次把串变成全 1反过来也一样。所以答案不变。如果你在考场上拿不准可以直接把虚拟边界两侧的颜色都设成目标颜色。比如目标是全 1就把 last 初始化为 1最后判断 last ! 1。这样代码几乎不用改。还有一种变体题目不是一次性给一个串而是多组测试数据。那只要把上面主循环包一层 while 循环每组读入 n 和 s重置 cnt 和 last 即可。int T; cin T; while (T--) { int n; string s; cin n s; int cnt 0; char last 0; for (char ch : s) { if (ch ! last) cnt; last ch; } if (last ! 0) cnt; cout cnt / 2 \n; }多组测试时注意 n 和实际字符串长度可能不匹配最好以实际读入的字符串为准。如果你用流式读字符就严格循环 n 次。4.4 复杂度与常数优化时间复杂度 O(n) 是这道题的理论最优因为每个字符至少要看一次。空间复杂度方面如果流式读入是 O(1)存字符串是 O(n)。对于竞赛环境O(n) 内存通常足够但能用流式读入减少内存时我会更倾向于流式因为遇到 n 特别大的题目时少踩一次内存坑。有人可能会想用“统计相邻不同”再除以 2实际上就是这段代码在做的事。唯一需要注意的常数优化是不要在每个字符循环里做除法答案最后算一次就好。另外ios::sync_with_stdio(false) 和 cin.tie(nullptr) 能显著加快 cin 读入传智杯这类比赛虽然不一定卡常但养成习惯没坏处。5. 常见问题与调试技巧5.1 边界样例自查表我把这个题容易出错的边界情况整理成了一张表你可以对照自查输入串虚拟边界数期望答案说明0000000已经是目标状态1111121一次整体取反000单字符已经是0121单字符1取反一次01021翻中间一个字符0101042交替串的经典情况1000142中间连续0段会变成11010163三个孤立1仍是3次11100011142两个1块中间000翻掉后整体再翻你把这些样例全部跑过一遍基本可以确定代码没大问题。尤其是“111000111”这个例子我考场上差点算错先翻 [4,6] 把中间的 000 变成 111此时整个串全是 1再翻全串变 0两次搞定。边界数确实是 4。5.2 考场上的三个坑第一个坑忘记右虚拟边界。很多人统计完相邻不同点直接输出 cnt / 2结果全 1 串输出 0。这个错误非常典型。解决办法就是我在代码里做的循环结束后一定要检查最后一个字符是不是 0。第二个坑把答案写成连续 1 段数。前面已经讲过段数贪心在 10001 这种样例上会出错。如果你只写完代码、跑两个常规样例就提交很容易踩坑。建议在提交前多构造几个 0 和 1 交错、中间有长 0 段的测试。第三个坑没搞清楚下标的 0 基和 1 基。虽然算法不依赖具体下标但如果你在实现“相邻边界配对”的构造方案时下标差一就会导致区间左右端点错误。只用计数答案时不必真的输出操作方案所以这类题一般不太容易差一但如果你在本地自己加打印调试要注意字符串下标从 0 开始。5.3 从TLE/RTE到AC的排错思路如果提交后 TLE先看是不是用了搜素或 DP而不是线性扫描。这道题正解就是 O(n)如果你写的是 O(n^2) 或更糟果断重写。如果 RTE多半是数组越界或者使用 string 但没有判空。传智杯这类比赛一般不会给空串但保险起见n 为 1 的情况也要测。如果 WA优先检查虚拟边界的处理。把样例 111、010、10001 全部跑一遍大概率能定位问题。还有一个调试思路自己写一个 O(n^2) 的 BFS 或区间 DP 作为对拍器随机生成小 n 字符串验证线性算法的答案是否一致。这个方法适合赛后复盘也适合在本地测试时用。6. 由这道题延伸出去的思考6.1 如果操作变成区间覆盖染色原题是取反但传智杯题面里用的是“染色”。有些同学会把它理解成“把区间染成统一颜色”。如果操作真变成“区间覆盖染色”问题会变成另一个样子每次可以选一个区间把区间内字符全部染成 0 或 1求全变 0 的最少操作次数。这种情况下答案不再是边界数的一半而是更简单如果原串全 0答案是 0否则答案是 1因为直接全串覆盖染 0 一次就完成了。当然如果加上“每次染色的颜色必须与区间原左端点颜色相同”之类的限制题目又会复杂起来。所以读题时一定要确认操作到底是“覆盖”还是“取反”这是天壤之别。6.2 如果只允许奇数长度区间这个变体很有意思如果每次只能选择长度为奇数的区间取反答案会怎么变化这时候一次操作影响左右边界的组合会受到奇偶限制可能无法像原题那样任意配对相邻边界。这时通常需要引入差分或 DP答案也可能变成另一个公式。我在赛后组织训练时会让队员思考这个问题作为对“边界视角”的加深练习。具体来说奇数长度区间取反会改变区间端点的奇偶性进而影响虚拟边界配对方式。这种变形题在百度之星、牛客小白月赛里偶尔能看到核心思维还是“一次操作影响两个边界”但多了奇偶约束。如果你能把原题理解透这个变体只是多加一个状态维度。6.3 这类题的通用思维模型我复盘过很多“区间操作 最少步数”的题目发现它们都有一个共同点操作对字符串内部的相对关系影响很小真正改变的是端点与外部的关系。因此你可以把字符串压缩成若干个连续段甚至只保留段的颜色和数量然后在这些“宏观状态”上做贪心或 DP。遇到一个陌生题时我建议按这个顺序思考操作会不会改变区间内部的“相邻不同”关系如果不会边界数量就是核心。目标状态有没有虚拟边界的意义如果有就把它补上。一次操作最多改变几个边界这个数量直接给出下界。能不能构造出每一步都达到下界的方案能答案就是下界不能再考虑 DP。这个思维模型不局限于字符串也适用于数组、棋盘、环状结构。比如环形 01 串变成全 0答案会略有不同因为环没有左右虚拟边界相邻不同点数为偶数答案直接是 cnt / 2。感兴趣的同学可以自己推导一下。7. 写在最后一点竞赛经验小苯的字符串染色这道题我个人在考场上犯过“连续1段贪心”的错误也花了不少时间才绕回边界视角。赛后我把这个结论反复推了几遍才发现它本质上是一个“下界可达”的经典证明先说明一次操作最多消两个边界再构造每次都消两个边界的方案于是答案就锁定了。很多思维题都是这个套路难的不是代码而是你敢不敢把问题简化成边界问题。以后遇到字符串操作题我建议你先别急着写代码在草稿纸上画几个小例子看看操作到底改变了什么、没改变什么。如果能找到一个“操作前后保持不变”的量题目往往就迎刃而解。如果你在比赛里实在想不出正解可以先写一个 O(n^2) 的暴力拿部分分再用暴力跑几个小样例去猜结论。传智杯的测试点通常比较友好猜出规律后线性扫描拿满分的机会很大。最后再分享一个小技巧这类题目的样例输出往往藏着答案公式的影子。你拿 01010、10001、111000111 去对比多算几组虚拟边界很快就能摸清规律。做题别怕动手推样例越是看起来“代码短到不敢相信”的题越值得在草稿纸上认真推导。
字符串区间取反最小操作次数的边界思维与竞赛解法
1. 题意精读小苯在染什么第六届传智杯程序设计国赛B组T4小苯的字符串染色这道题在考场上卡了我一阵子。题目本身不长但真正把操作次数想清楚需要一点经典的边界思维。如果你准备打传智杯这类偏应用的算法竞赛这道题的思考路径非常值得单独拿出来复盘。先说清楚题意我们手里有一个长度为 n 的01字符串字符 0 和 1 可以理解成两种颜色。每次操作可以任选一个连续区间把区间内所有字符的颜色全部取反0 变成 11 变成 0。要求用最少的操作次数把整个字符串变成全 0。传智杯B组T4的难度定位一般是“有一定思维量但代码实现非常短”的题目这道题就是典型代表正解核心代码不超过十行难的是你怎么想到那十行。我在考场上的第一反应是这是个区间翻转问题。因为它和常见的“区间整体赋值”不一样取反操作会让区间内部原本连续的 0 在取反后变成 1所以直接用贪心扫一遍“把当前 1 段翻掉”并不一定最优。举个简单例子01010如果见到第一个 1 就翻 [2,2]字符串变成 00010再翻 [4,4] 变成 00000看似 2 次搞定。但另一个串 0101010如果还用这种“见 1 就翻单点”的贪心需要 3 次而实际上可以先翻 [2,6]再翻 [4,4]我们后面会算这个串其实 2 次就能解决。这里的反直觉点正是整道题的题眼。1.1 题目定位与考场直觉把传智杯B组T4放在整套题里看它属于“思维题偏算法实现”的类型。考场上你不需要写复杂的数据结构也不需要套高级算法模板但需要具备一种能力把对字符串的区间操作抽象成另一种更容易统计的数学对象。我在读完题后先列了几个已知信息字符串只包含 0 和 1所以任何一次区间取反影响的是区间内所有字符的“颜色属性”。目标状态是固定的全 0。操作区间可以任意长甚至可以选整个串。要求的是最小操作次数而不是方案数。这里最关键的直觉是如果只关注“当前字符串长什么样”你会被 2^n 种状态淹没但如果把目光放到“相邻两个字符之间是否相同”上取反操作的影响会变得非常局部。这个转变我后面会详细展开。1.2 输入输出与操作定义按这类题目的常规输入格式第一行通常是一个正整数 n表示字符串长度第二行是一个长度为 n 的字符串 s字符只包含 0 和 1。输出一个整数表示最少操作次数。例如输入 n4s1111输出 1。因为直接选择整个区间 [1,4] 取反一次就变成 0000。输入 n3s010输出 1。选择区间 [1,3] 取反得到 101不对正确做法是选择 [2,2] 取反得到 000。这说明单点操作在有些情况下就是最优解。输入 n5s01010输出 2。先选区间 [2,4] 取反01010 变成 00100再选区间 [3,3] 取反变成 00000。这比逐个翻 1 要少一次。小细节操作区间的下标从 1 开始还是从 0 开始不影响算法但写代码时要注意循环边界和字符串下标习惯避免差一错误。1.3 一个必须牢记的观察我做完这道题后最大的体会是区间取反操作有一个“内部不变”的性质。什么意思一个区间内部如果原本就存在颜色变化的边界比如相邻两个字符一个是 0 一个是 1那么区间整体取反之后这两个字符依然不同只是颜色交换了。换句话说区间内部的“相邻不同”关系不会因为取反而消失或新增取反改变的只有区间两个端点与外部相邻位置的关系。这个观察看起来平淡但它直接决定了答案只和“边界数量”有关和字符串具体的排列没有太大关系。想明白这一点题目就完成了一大半。2. 从暴力到正解的思维推导2.1 为什么不直接BFS我理解题意的第一版思路是搜索把每个字符串看成状态每次枚举所有区间做一次取反然后广搜找最短步数。这个思路对于 n10 的小数据完全可行但传智杯T4的 n 不可能这么小一旦 n 到几千状态数是指数级的BFS 瞬间爆炸。还有同学会想到动态规划比如用 dp[i][j] 表示前 i 个字符已经全 0 且最后一次操作覆盖到 j 的最小次数。这确实能做但状态定义很容易绕进去而且这道题的操作和“当前后缀状态”之间的关系不够直观DP 写起来繁琐还容易漏状态。实际上这种“区间取反求最少次数”的题通常有一个共同套路把连续相同字符压缩成一个段然后只关心段与段之间的边界。一旦你从“字符视角”切到“边界视角”DP 反而是多余的。2.2 把“染色”看成“取反”题目叫“字符串染色”但操作本质是取反0 染成 11 染成 0。为什么要强调这个因为如果你把它理解成“把一段染成某个颜色”你可能会想成覆盖操作那问题会变得非常简单全串染 0 一次就完成没什么可考的。正是因为取反会保留区间内部的相对差异问题才变得有趣。取反操作的另一个特点是连续操作两个相同区间会互相抵消所以最优解里不会出现对同一个区间做偶数次取反的情况而连续两次取反不同区间如果它们的覆盖关系可以调整往往也能合并或优化。因此在讨论最少次数时我们只需要考虑每次操作都能“减少一些东西”的贪心方案而不是盲目枚举状态。2.3 边界这道题的真正主角我在纸上画了几个例子之后发现真正和被取反区间相关的不是“哪些位置是 1”而是“相邻位置颜色是否不同”。举个例子s 001100逐对比较0-0 相同0-1 不同1-1 相同1-0 不同0-0 相同。共有 2 个相邻不同点。s 01010相邻不同点有 4 个。s 111相邻不同点有 0 个。目标状态 000 的相邻不同点也是 0 个。于是问题可以重新描述为初始字符串有一组“边界”每次区间取反最多只能改变两个边界区间左端和右端区间内部的边界数量不变最终目标要求边界全部消失。那么最少操作次数显然不会少于“边界总数的一半”。这个“至少”的直觉很关键它把最优化问题转化成了下界证明问题。但这里有一个隐含问题111 的相邻不同点是 0可它明明需要 1 次操作这不就让“至少 0 次”下界失效了吗我一开始也在这里卡住。解决方法是引入“虚拟边界”把字符串的左右两端都想象成颜色 0。于是 111 的左端虚拟边界是 0-1 不同右端虚拟边界是 1-0 不同总边界数是 2答案下界就变成了 1和真实答案吻合。加虚拟边界这个操作在区间问题里非常常见。它本质上是把“串外”也定义成一个固定颜色这样任何取反区间都会在左右两个端点处与外部形成新的相邻关系边界变化紧紧贴着操作端点内部的自由边界不影响统计。3. 核心结论与数学证明3.1 虚拟边界定义先给出严谨定义。设字符串 s 长度为 n我们额外规定 s[0] 0s[n1] 0。对于位置 i 从 0 到 n如果 s[i] ! s[i1]就称这里有一个“边界”。注意这里 s[0] 和 s[n1] 是虚拟字符不是真实字符。于是全 0 串的边界数为 0。全 1 串的边界数为 2左虚拟边界和右虚拟边界各一个。01010 的边界数s[0]0 与 s[1]0 相同0-1 不同1-0 不同0-1 不同1-0 不同s[5]0 与 s[6]0 相同共 4 个边界。001100 的边界数虚拟左边界相同0-1 不同1-0 不同虚拟右边界相同共 2 个边界。这个定义可以把所有情况统一起来也方便我们证明。3.2 答案公式推导一次区间取反操作选择区间 [l, r]会对哪些边界产生影响注意区间内部的相邻关系取反后依然“不同性”不变所以内部边界数量不变。变化的只有两个位置l-1 与 l 之间的相邻关系因为 s[l] 取反了s[l-1] 没取反。r 与 r1 之间的相邻关系因为 s[r] 取反了s[r1] 没取反。也就是说一次操作最多影响两个边界最少也可能影响 0 个边界比如取的区间刚好和前后状态一致取反后没有改变不同性。但从减少边界的角度看一次操作最多让边界总数减少 2。最终目标边界数是 0初始边界数记为 cnt那么操作次数一定有下界ceil(cnt / 2)。再证明这个下界可以达到。我们把 cnt 个边界按照从左到右的顺序编号为第 1、2、...、cnt 个。取第 1 个边界和第 2 个边界令操作区间为“这两个边界之间的真实字符区间”进行一次取反。这次操作会同时消除这两个边界并且不会影响其他边界。为什么因为第 1 个边界和第 2 个边界之间的字符被整体取反区间左端与左侧外部的关系被修正区间右端与右侧外部的关系也被修正而区间内部原本可能存在的边界在取反后依旧存在但由于我们取的是“相邻两个边界之间”区间内部恰好没有其他边界。所以一次操作干净利落地消掉两个边界。随后再取剩下的第 1 个和第 2 个边界重复操作直到没有边界。如果 cnt 是偶数需要 cnt/2 次如果 cnt 是奇数最后一次只剩一个边界这时选择从该边界到字符串某一端的区间取反一次就能消掉它。因此总次数是 ceil(cnt / 2)。所以最终答案就是虚拟边界总数的一半向上取整即答案 (cnt 1) / 2用整数除法表示就是 (cnt 1) / 2。如果你不想引入虚拟边界也可以这样写统计从第一个字符到最后一个字符之间的相邻不同次数记为 c但注意最左侧如果从 0 开始已经计算实际上我们写代码时统一用“上一个字符”初值为 0来遍历整个串如果当前字符不等于上一个字符cnt遍历结束后如果最后一个字符不是 0 再 cnt。这个写法最不容易漏。3.3 构造性上界如何配对边界上面证明里提到的配对操作我建议你在纸上手动推一遍尤其是 01010 这个串。01010 的虚拟边界位置分别在位置 1 和 2 之间0-1 不同位置 2 和 3 之间1-0 不同位置 3 和 4 之间0-1 不同位置 4 和 5 之间1-0 不同共 4 个边界配对为第 1 和第 2 个操作区间是 [2,2]再配对第 3 和第 4 个操作区间是 [4,4]。这样需要 2 次是我们之前见过的答案。也可以换一种配对第 1 和第 4 个配对操作区间 [2,5]我试着操作取反 [2,5]01010 变成 00101边界变成 2 个再操作 [3,5] 变成 00110这样更乱。所以最优配对方式是“相邻边界两两配对”也就是从左到右相邻边界之间的区间直接取反。这种配对方式保证每次消除的是两个连续边界不会引入新的间隔。你可能会有疑问为什么不能一次消除超过两个边界因为区间内部的边界取相反转后仍然存在不会消失所以一次操作无法直接影响内部边界。这个“区间内部边界不可消除”的特性是本题最核心的限制条件。理解了这个你就能明白为什么答案不是“连续 1 段的数量”而是“边界数的一半”。3.4 为什么不是“连续1段数量”我最初写了一个贪心统计连续 1 的段数每段翻一次遇到全 1 串反而要翻一次答案就是连续 1 段数。这个做法能过一部分样例但错在“翻单点 1 段”并不是最优。看一个反例s 10101。连续 1 段有 3 段按段数答案是 3。但实际最优答案是多少用虚拟边界统计s[0]0s[1]1 边界1-0 边界0-1 边界1-0 边界0-1 边界s[6]0 与 s[5]1 边界一共 5 个边界我数一下位置0虚拟0和s11不同1s11和s20不同2s20和s31不同3s31和s40不同4s40和s51不同5s51和虚拟右0不同6实际是 6 个边界。答案 6 / 2 3。好像还是 3不构成反例。换个例子s 10001。连续 1 段只有 1 段段数答案是 1虚拟边界左虚拟0与s11不同1s11与s20不同2s20与s30相同s30与s40相同s40与s51不同3s51与右虚拟0不同4答案 4/2 2。而实际操作翻 [2,4] 把 000 变成 111串变成 11111再翻 [1,5] 变成 00000确实需要 2 次。所以段数贪心低估了答案。这个例子非常好地说明了“只翻 1 段”不是最优的中间连续 0 段在取反后会变成 1等于你把一个 1 段拆成两半甚至更多 1 段后面的操作次数不会减少反而可能增加。而借助边界配对我们能精确控制每次操作让每一步都恰好消掉两个边界保证最终步数等于理论下界。4. 代码实现与复杂度分析4.1 最简写法边读边算由于我们只需要统计边界数量根本不需要把整个字符串存下来。读入 n 之后可以一个字符一个字符地处理维护一个变量 last 表示上一个字符的颜色。为了处理左虚拟边界last 初始化为 0。伪代码逻辑如下初始化 last 0cnt 0。循环 n 次每次读入一个字符 ch如果 ch ! lastcnt。last ch。循环结束后如果 last ! 0cnt。输出 cnt / 2。这里有一个细节题目给的 n 是字符串长度但实际处理时不需要依赖 n 的数值只需要知道读入 n 便于控制循环。如果题目有多组测试数据注意每组都要重置 cnt 和 last。4.2 完整参考代码下面是一份可以 AC 的 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 0; char last 0; // 左虚拟边界想象字符串左边还有一个0 for (int i 0; i n; i) { if (s[i] ! last) { cnt; } last s[i]; } // 右虚拟边界如果最后一个字符不是0说明和右边假想的0不同 if (last ! 0) { cnt; } cout cnt / 2 \n; return 0; }这段代码的时间复杂度是 O(n)空间复杂度 O(1)存字符串也只用了 O(n)如果你用流式读入可以做到 O(1) 额外空间。对于传智杯B组T4的数据范围来说这个效率非常充裕。如果你希望彻底省掉字符串数组可以改成下面这种写法#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; char last 0; int cnt 0; char ch; for (int i 0; i n; i) { cin ch; if (ch ! last) { cnt; } last ch; } if (last ! 0) { cnt; } cout cnt / 2 \n; return 0; }两种写法都行。第一种更容易读第二种更能体现“流式处理”的思路。如果题目要求输入输出文件重定向自己在本地调试时加上 freopen 就行。4.3 目标变体的扩展代码如果题目把目标改成“变成全 1”答案一样吗我的结论是完全一样。因为目标全 0 和全 1 之间只差一次整体取反而整体取反等价于选择区间 [1,n] 操作一次。如果全 0 的最优解是 k 次那么先整体取反一次再按照原来的策略操作就能用 k1 次把串变成全 1反过来也一样。所以答案不变。如果你在考场上拿不准可以直接把虚拟边界两侧的颜色都设成目标颜色。比如目标是全 1就把 last 初始化为 1最后判断 last ! 1。这样代码几乎不用改。还有一种变体题目不是一次性给一个串而是多组测试数据。那只要把上面主循环包一层 while 循环每组读入 n 和 s重置 cnt 和 last 即可。int T; cin T; while (T--) { int n; string s; cin n s; int cnt 0; char last 0; for (char ch : s) { if (ch ! last) cnt; last ch; } if (last ! 0) cnt; cout cnt / 2 \n; }多组测试时注意 n 和实际字符串长度可能不匹配最好以实际读入的字符串为准。如果你用流式读字符就严格循环 n 次。4.4 复杂度与常数优化时间复杂度 O(n) 是这道题的理论最优因为每个字符至少要看一次。空间复杂度方面如果流式读入是 O(1)存字符串是 O(n)。对于竞赛环境O(n) 内存通常足够但能用流式读入减少内存时我会更倾向于流式因为遇到 n 特别大的题目时少踩一次内存坑。有人可能会想用“统计相邻不同”再除以 2实际上就是这段代码在做的事。唯一需要注意的常数优化是不要在每个字符循环里做除法答案最后算一次就好。另外ios::sync_with_stdio(false) 和 cin.tie(nullptr) 能显著加快 cin 读入传智杯这类比赛虽然不一定卡常但养成习惯没坏处。5. 常见问题与调试技巧5.1 边界样例自查表我把这个题容易出错的边界情况整理成了一张表你可以对照自查输入串虚拟边界数期望答案说明0000000已经是目标状态1111121一次整体取反000单字符已经是0121单字符1取反一次01021翻中间一个字符0101042交替串的经典情况1000142中间连续0段会变成11010163三个孤立1仍是3次11100011142两个1块中间000翻掉后整体再翻你把这些样例全部跑过一遍基本可以确定代码没大问题。尤其是“111000111”这个例子我考场上差点算错先翻 [4,6] 把中间的 000 变成 111此时整个串全是 1再翻全串变 0两次搞定。边界数确实是 4。5.2 考场上的三个坑第一个坑忘记右虚拟边界。很多人统计完相邻不同点直接输出 cnt / 2结果全 1 串输出 0。这个错误非常典型。解决办法就是我在代码里做的循环结束后一定要检查最后一个字符是不是 0。第二个坑把答案写成连续 1 段数。前面已经讲过段数贪心在 10001 这种样例上会出错。如果你只写完代码、跑两个常规样例就提交很容易踩坑。建议在提交前多构造几个 0 和 1 交错、中间有长 0 段的测试。第三个坑没搞清楚下标的 0 基和 1 基。虽然算法不依赖具体下标但如果你在实现“相邻边界配对”的构造方案时下标差一就会导致区间左右端点错误。只用计数答案时不必真的输出操作方案所以这类题一般不太容易差一但如果你在本地自己加打印调试要注意字符串下标从 0 开始。5.3 从TLE/RTE到AC的排错思路如果提交后 TLE先看是不是用了搜素或 DP而不是线性扫描。这道题正解就是 O(n)如果你写的是 O(n^2) 或更糟果断重写。如果 RTE多半是数组越界或者使用 string 但没有判空。传智杯这类比赛一般不会给空串但保险起见n 为 1 的情况也要测。如果 WA优先检查虚拟边界的处理。把样例 111、010、10001 全部跑一遍大概率能定位问题。还有一个调试思路自己写一个 O(n^2) 的 BFS 或区间 DP 作为对拍器随机生成小 n 字符串验证线性算法的答案是否一致。这个方法适合赛后复盘也适合在本地测试时用。6. 由这道题延伸出去的思考6.1 如果操作变成区间覆盖染色原题是取反但传智杯题面里用的是“染色”。有些同学会把它理解成“把区间染成统一颜色”。如果操作真变成“区间覆盖染色”问题会变成另一个样子每次可以选一个区间把区间内字符全部染成 0 或 1求全变 0 的最少操作次数。这种情况下答案不再是边界数的一半而是更简单如果原串全 0答案是 0否则答案是 1因为直接全串覆盖染 0 一次就完成了。当然如果加上“每次染色的颜色必须与区间原左端点颜色相同”之类的限制题目又会复杂起来。所以读题时一定要确认操作到底是“覆盖”还是“取反”这是天壤之别。6.2 如果只允许奇数长度区间这个变体很有意思如果每次只能选择长度为奇数的区间取反答案会怎么变化这时候一次操作影响左右边界的组合会受到奇偶限制可能无法像原题那样任意配对相邻边界。这时通常需要引入差分或 DP答案也可能变成另一个公式。我在赛后组织训练时会让队员思考这个问题作为对“边界视角”的加深练习。具体来说奇数长度区间取反会改变区间端点的奇偶性进而影响虚拟边界配对方式。这种变形题在百度之星、牛客小白月赛里偶尔能看到核心思维还是“一次操作影响两个边界”但多了奇偶约束。如果你能把原题理解透这个变体只是多加一个状态维度。6.3 这类题的通用思维模型我复盘过很多“区间操作 最少步数”的题目发现它们都有一个共同点操作对字符串内部的相对关系影响很小真正改变的是端点与外部的关系。因此你可以把字符串压缩成若干个连续段甚至只保留段的颜色和数量然后在这些“宏观状态”上做贪心或 DP。遇到一个陌生题时我建议按这个顺序思考操作会不会改变区间内部的“相邻不同”关系如果不会边界数量就是核心。目标状态有没有虚拟边界的意义如果有就把它补上。一次操作最多改变几个边界这个数量直接给出下界。能不能构造出每一步都达到下界的方案能答案就是下界不能再考虑 DP。这个思维模型不局限于字符串也适用于数组、棋盘、环状结构。比如环形 01 串变成全 0答案会略有不同因为环没有左右虚拟边界相邻不同点数为偶数答案直接是 cnt / 2。感兴趣的同学可以自己推导一下。7. 写在最后一点竞赛经验小苯的字符串染色这道题我个人在考场上犯过“连续1段贪心”的错误也花了不少时间才绕回边界视角。赛后我把这个结论反复推了几遍才发现它本质上是一个“下界可达”的经典证明先说明一次操作最多消两个边界再构造每次都消两个边界的方案于是答案就锁定了。很多思维题都是这个套路难的不是代码而是你敢不敢把问题简化成边界问题。以后遇到字符串操作题我建议你先别急着写代码在草稿纸上画几个小例子看看操作到底改变了什么、没改变什么。如果能找到一个“操作前后保持不变”的量题目往往就迎刃而解。如果你在比赛里实在想不出正解可以先写一个 O(n^2) 的暴力拿部分分再用暴力跑几个小样例去猜结论。传智杯的测试点通常比较友好猜出规律后线性扫描拿满分的机会很大。最后再分享一个小技巧这类题目的样例输出往往藏着答案公式的影子。你拿 01010、10001、111000111 去对比多算几组虚拟边界很快就能摸清规律。做题别怕动手推样例越是看起来“代码短到不敢相信”的题越值得在草稿纸上认真推导。