Score题解：用字符串遍历与状态累加吃透连续O段计分

Score 这道题在入门阶段的地位很特殊它几乎不考算法却能把“字符串遍历”和“状态累加”这两个最基础的动作讲透。题目要求给定若干串只含 O 和 X 的字符串按“连续 O 段中第 k 个 O 记 k 分、X 记 0 分并打断连续”的规则求总分——听起来像小学算术但真正动笔写代码时你会发现自己在“当前连续长度”和“总分累加器”之间反复横跳。这篇内容面向刚接触编程入门题的朋友也面向带新人时想找一道“状态变量”教学案例的同行。我会从题意拆解讲到三种写法对比再给出手算推演、边界用例、逐行注释和一份真实踩坑速查表把这道 1585 号 Score 题变成一个可以反复复用的思维模板。1. 题目档案与核心需求拆解1.1 一句话说清题意与样例核算先把规则翻译成人话给定 T 组数据每组一个长度不超过 80 的字符串字符只有O和X两种。遍历这个串遇到O时它的得分等于“它在当前连续 O 段里排第几”遇到X时得 0 分并且把连续计数清零。最后把整串所有 O 的得分加起来输出。拿最常见的样例组来核对一遍五组输入与输出对应关系如下表这几组数据我建议你直接抄下来当自测集序号输入串分段拆解各段得分总分1OOXXOXXOOOOO / XX / O / XX / OOO3 0 1 0 6102OOXXOOXXOOOO / XX / OO / XX / OO3 0 3 0 393OXOXOXOXOXOXOX七个独立 O1 × 774OOOOOOOOOO一整段 10 个 O12…10555OOOOXOOOOXOOOOXOOOO / X / OOOO / X / OOOO / X10 10 1030第一组数据最能说明问题同样一个O出现在段首得 1 分出现在段尾得 3 分。分数不是由字符本身决定的而是由“它前面已经连续出现了几个 O”决定的。这句话就是整道题的题眼后面所有的代码写法都只是在表达这件事。第四组数据值得单独记一下连续 n 个 O 的得分是 n(n1)/210 个 O 就是 55。这个闭式公式在验证大用例时非常好用比如你写了一个生成器随机造一串 80 个 O答案必然是 80×81/2 3240一秒就能判断程序对不对。1.2 这道题真正的考点不是算法而是状态很多人一看这题觉得“太简单了不就是个循环吗”然后交上去 WA。原因往往不是不会写循环而是脑子里没有“状态”这个概念——他不知道在遍历过程中需要同时维护哪几个量也不知道哪个量在什么时候必须清零。从工程角度看这道题考的是三个东西。第一是遍历的完整性每个字符都要被访问且只被访问一次。第二是状态的正确迁移遇到 O 时状态如何增长遇到 X 时状态如何归零。第三是累加与状态的分离总分是只增不减的“累积量”连续长度是会被打断的“瞬时量”两者绝不能混成一个变量。我见过太多新人在草稿纸上写“用一个变量记分数遇到 O 就加一遇到 X 就清零”然后发现 OO 这段算出 1 分而不是 3 分。因为这个写法把“瞬时状态”和“累积结果”塞进了同一个变量加一的时候是累加器语义清零的时候又变成了状态语义两种语义打架结果必然是错的。这个区分就是本道题最大的收获。1.3 输入输出规格与天然坑点预判按常见的题目描述输入第一行是一个整数 T表示数据组数接下来 T 行每行一个由 O 和 X 组成的字符串长度不超过 80。输出为每组数据一行一个整数表示该串得分。表面上的规格很干净但实际上有几个坑在等着。第一字符串长度上限 80这意味着如果你用字符数组存开 100 以上才安全开 80 恰好会在最后一组数据上因为结尾符越界而出现诡异行为有些编译器下不报错但会踩坏相邻变量。第二T 行数据之间可能存在空行如果你用逐行读取的方式需要判断并跳过空行否则会把空串当成一组数据算成 0 分导致输出行数错位。第三某些版本会在最后一行没有换行符用getline读最后一行时要留意读取返回值。还有一个不太容易想到的点如果题目允许多组数据连续输入直到文件结束有些改编版会这么改那么cin T之后的所有数据要一次性读完不能依赖 T 的准确性。我的习惯是无论题目怎么说都先把读取层写稳再考虑逻辑层因为这类入门题的评测机往往对格式比对你算法更敏感。2. 三种写法与选型考量2.1 单循环加双变量主力写法这是我最推荐的写法也是绝大多数标准答案的形态。核心只需要两个整型变量cur表示“当前连续 O 的个数”ans表示“到目前为止的总得分”。遍历字符串的每个字符遇到O就让cur加一然后ans加上cur遇到X就让cur归零ans不动。这个写法的妙处在于ans cur这一句把“第 k 个 O 得 k 分”翻译成了“每次把当前连续长度整个加进去”。第 1 个 O 时cur是 1加 1第 2 个 O 时cur是 2加 2第 3 个 O 时cur是 3加 3。累加起来正好是 123。这个等价转换是整道题最漂亮的地方也是为什么它适合当作教学案例它把一个“位置相关”的规则转成了“状态值直接累加”的规则。选它的理由很实在只有一层循环没有任何边界判断不需要额外空间写完之后肉眼就能看出正确性。对于长度 80 的输入时间复杂度 O(n)、空间复杂度 O(1)评测机连热身都算不上。2.2 分段扫描双指针思路第二种写法是“先找出所有连续的 O 段再对每段求 1 到 len 的和”。用两个下标i和ji找段的开头j往后扫到第一个 X 或者串尾段长L j - i往答案里加L*(L1)/2然后i跳到j继续。这个写法的优势是“语义直白”它和人类读题的方式完全一致先切段再算分。缺点是边界处理变多——j扫到串尾时不能越界、i跳过 X 时不能死循环、空段要跳过。我试过让几个刚学编程的朋友分别用这两种写法实现双变量版本通常 5 分钟写完一次过双指针版本平均要改两三轮才过。所以从“稳定交付”的角度主力写法应该是前一种。但分段扫描并非没有价值。当题目变形为“求最长连续 O 段”“求连续 O 段的个数”“求每段长度分布”时分段扫描的框架可以直接复用而双变量写法就得重写。所以我的建议是主力写法用来交题分段扫描用来理解结构两者都过一遍手你对“段”这个概念的理解会扎实很多。2.3 一行流写法Python 演示用Python 里有个非常短的写法纯当思维体操看把字符串按X切开得到若干段 O对每段长度L计算L*(L1)//2再求和。用列表推导写出来就是sum(len(seg)*(len(seg)1)//2 for seg in s.split(X))。这个写法优雅得让人想直接交上去但我不建议新手把它当作首选。原因有三一是它隐藏了遍历过程你没法在这个写法里练习“状态迁移”这个核心技能二是split会产出空串连续两个 X 之间就是空串虽然len为 0 时公式结果也是 0 不影响正确性但这个“恰好正确”很容易让人产生误解三是比赛环境下如果输入规模变大切分会产生额外的字符串对象。把它当作一个“验算工具”倒是很合适写完主力写法之后用这一行在本地跑几百组随机数据对拍一分钟就能确认逻辑无误。工具和主力的定位要分清这是我带人时反复强调的一点。2.4 三种写法的横向对比把关键维度列成表格方便你按场景选维度双变量单循环双指针分段切分一行流代码行数约 6 行约 12 行1 行边界处理难度低中高极低首写通过率高中高状态思维训练价值高中低可迁移到变形题中高低额外空间O(1)O(1)O(n)适合场景交题、教学理解段结构、变形题对拍验算、脚本看完这张表你应该能明白我的取舍逻辑入门阶段优先选“能一次写对”的方案把正确性拿稳再回头补结构理解。反过来先啃双指针很容易在边界上耗掉热情。3. 代码实现与逐行拆解3.1 C 版本与逐行注释下面是我平时用的模板注释写得比较密方便你对照理解每一句的意图#include iostream #include string using namespace std; int main() { int T; if (!(cin T)) return 0; // 读组数读不到直接退出 while (T--) { string s; cin s; // 串内无空格用 最省事 int cur 0; // 当前连续 O 的个数 int ans 0; // 总分 for (size_t i 0; i s.size(); i) { if (s[i] O) { cur; // 连续长度加一 ans cur; // 把当前长度整个计入总分 } else { cur 0; // 遇到 X连续中断 } } cout ans \n; // 每组一行 } return 0; }第 8 行和第 9 行的cur和ans必须放在循环内部每次处理新字符串时重新初始化为 0。这是整段代码里最容易出错的位置我后面会专门用一节讲。第 12 行的cur必须在ans cur之前顺序反了的话第一个 O 会加 0 分整串结果整体偏小。第 13 行的写法用s[i] O判断也可以写成else分支显式判断X但考虑到题目保证只有这两种字符用else更省一次比较。如果哪天遇到含其他字符的变体题这里就要改成显式判断否则会把非法字符当成 X 处理虽然结果碰巧一样但语义上不严谨。3.2 Python 版本import sys def main(): data sys.stdin.read().split() if not data: return t int(data[0]) out [] for k in range(1, t 1): s data[k] cur 0 ans 0 for ch in s: if ch O: cur 1 ans cur else: cur 0 out.append(str(ans)) sys.stdout.write(\n.join(out)) main()这里我用sys.stdin.read().split()一次性把所有 token 读进来好处是完全不受换行和空行的干扰坏处是如果输入规模极大比如上百万行会吃内存。对这道长度 80、组数一般不超过几十的题来说这个写法非常省心也避免了input()和readline()混用导致的读串位问题。Python 里for ch in s直接迭代字符比用下标更 Pythonic也更快。out列表收集结果最后一次性输出比循环里反复print快得多这个习惯在数据量大的题上能救你一命。3.3 Java 版本import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int t sc.nextInt(); StringBuilder sb new StringBuilder(); while (t-- 0) { String s sc.next(); int cur 0, ans 0; for (int i 0; i s.length(); i) { if (s.charAt(i) O) { cur; ans cur; } else { cur 0; } } sb.append(ans).append(\n); } System.out.print(sb); } }Java 用Scanner.next()读字符串注意不要用nextLine()因为前面的nextInt()会留下一个换行符nextLine()会立刻读到空串这是 Java 入门者最常见的输入陷阱之一。输出用StringBuilder拼接避免每组都调一次System.out.println带来的 IO 开销。逻辑部分和 C 完全一致这说明这道题的核心与语言无关。如果你发现自己在三种语言里写出了三套不同逻辑那说明还没抓住“状态加累加”这个本质。3.4 状态重置的时机最容易写错的一行cur 0这一句看起来平平无奇但它的位置错了整道题就废了。我把几种典型错位列出来你可以对照自己的代码检查写法现象原因cur定义在 while 外不重置第一组之后全错上一组残留值带进下一组遇 X 时cur 0写在if内只有 O 时才可能被清零分支写反逻辑失效遇 X 时同时ans 0分数被反复清空把累积量和状态量混用循环结束后再ans cur结果偏大每次 O 已经加过末尾重复计入先ans cur再cur结果整体偏小第一个 O 贡献了 0 分最后一条我要重点提醒。很多人觉得“先加后加不都一样吗”在这道题里差得很明显。假设串是O正确流程是cur变 1、ans加 1、输出 1如果你先加再变就是ans加 0、cur变 1、输出 0。两个字符的OO会从 3 变成 2误差随段长线性增长。写的时候把这两句的顺序当成肌肉记忆固定下来别在比赛现场靠推理。3.5 多组输入的读取细节C 里cin s会自动跳过空白字符包括空格、制表符和换行。所以只要题目保证串内没有空格这个读法就是最稳的不用管两个字符串之间隔了几个空行。这也是我在第一节说“读取层先写稳”的实际落点能用 token 级读取就不要用行级读取。但有一种情况cin s会出问题如果某个字符串允许为空串。此时cin s会跳过这个空串去读下一个非空 token导致后续所有数据错位一位。判断方法是看题目约束里有没有“长度至少为 1”。这道题的串至少有 1 个字符所以安全。如果你遇到变形题允许空串就得切回getline并按行处理同时要处理行尾的\r不同系统换行符差异用erase或者判断最后一个字符要不要丢弃。Python 里同理split()按任意空白切分天然免疫空行问题这也是我偏爱它作为验算脚本的原因。Java 的Scanner.next()行为和cin s一致注意别用nextLine()即可。4. 手工推演与测试用例设计4.1 把过程画在纸上跑一遍我建议每个新手在写代码之前先拿OOXXOXXOOO这串手算一遍把每一步的cur和ans记在表格里。这个过程花不了三分钟但能帮你把“状态”这件事刻进脑子里步骤字符cur 变化ans 变化说明1O0 → 10 → 1段内第 1 个2O1 → 21 → 3段内第 2 个3X2 → 03段被打断4X0 → 03连续两次 X5O0 → 13 → 4新段第 1 个6X1 → 04段被打断7X0 → 04空转8O0 → 14 → 5新段第 1 个9O1 → 25 → 7段内第 2 个10O2 → 37 → 10段内第 3 个最终 10和样例一致。手工推演的价值在于你能看到ans在 X 处完全静止这一点很多人第一次写代码时会下意识地“遇 X 也加点什么”。表格里第 3、4、6、7 步的 ans 都保持不动这个“不动”本身就是规则的一部分。4.2 边界用例清单光靠样例过题是不够的评测机的隐藏数据往往打在边界上。下面这份清单我每次做这类题都会过一遍用例输入期望输出考察点全 XXXXX0ans 初始值、全程不累加单字符 OO1最小非零用例单字符 XX0最小零用例全 O 长串O × 803240无 X 干扰、公式验证头尾都是 OOOXOO1123 分段核算段边界恰好 80 字符构造 80 个混合字符手算或对拍数组越界连续多组混合上述用例逐行对应变量复位全 O 长串那条特别有用80 个 O 的期望值是 80×81/2 3240这个数你可以闭着眼睛写出来不需要手算。如果程序输出 3160 或 3320基本能判断是差一错误或者多加了一段。4.3 随机对拍验证写完之后我最习惯的做法是写个暴力对拍脚本造 1000 组随机串长度 1 到 80字符各 50% 概率分别用主力写法和那一行split写法跑比对结果。Python 里几行就能写完import random def fast(s): cur ans 0 for ch in s: if ch O: cur 1 ans cur else: cur 0 return ans def slow(s): return sum(len(seg) * (len(seg) 1) // 2 for seg in s.split(X)) for _ in range(1000): n random.randint(1, 80) s .join(random.choice(OX) for _ in range(n)) if fast(s) ! slow(s): print(diff, s, fast(s), slow(s)) break else: print(all pass)对拍的意义不在于“我的代码肯定对”而在于“两种独立思路互不相同的实现给出了相同答案”。如果两个都错那说明你对题意的理解本身就偏了这时候该回去重读题目而不是继续调代码。我遇到过有人在两种写法里都把“连续段长度”理解成“从串首开始计数”对拍全过交上去全 WA就是因为错在了理解层而不是实现层。5. 常见错误与排查实录5.1 高频错误速查表下面这些错误我在带新人时几乎每年都会见一遍表格按“现象—根因—修法”组织遇到问题直接对照查现象最可能的根因修法第一组对后面全错cur 或 ans 在循环外未复位把初始化挪进每组处理的开头结果比正确值小一半先加后自增把cur移到ans cur之前结果恒为 0ans 被写在 if 外部且只加 cur 未累加检查 ans 是累加还是赋值结果只等于 O 的个数只加了 1 没加 cur改成ans cur输出行数不对用行级读取把空行当数据改用 token 级读取最后一组答案异常大循环结束后又加了一次删掉循环外的二次累加全 O 用例接近但不等于 3240数组越界或长度截断容器开 100 以上5.2 三类错误的深入解剖未复位型错误是最迷惑人的因为它在单组数据下完全正常一交就错。根因是把int cur 0, ans 0;写在了while (T--)外面。修法很简单但更重要的是养成“状态变量就近声明”的习惯哪个变量服务于哪一次迭代就声明在那个迭代的作用域里。混用型错误是把累积器和状态器当成一个变量。典型写法是“遇 O 就score遇 X 就score 0”最后输出score。这种写法在OXOX上碰巧输出 0 和正确答案 2 差得不多容易被误判成“小问题”。修法是强迫自己用两个变量并在注释里写清各自的语义。重复累加型错误是在循环中已经加过了循环外又补一句ans cur。这通常来自“担心最后一段没加”的直觉而这份直觉其实是误解——最后一段的每一个 O 在遍历时都已经各自加过了不需要收尾补刀。这个坑我在第一次做这类题时就踩过当时盯着输出比正确值多了 3调了半小时还没想明白。5.3 现场调试手法调这道题的时候不要只打印最终结果。我的做法是在循环里裁一个临时打印输出i、s[i]、cur、ans四个值跑一个小用例看轨迹是否和手算表格对得上。用OO这种两字符的数据跑一眼就能看出第一个 O 是否加了 1 分。如果环境里不方便加打印还可以用“缩小输入”的策略把长串截成前 3 个字符单独跑。很多逻辑错误在小输入上会以极其明显的形式暴露出来比如输出 0 或者负数。这个技巧适用于所有遍历类题目。还有一个排查习惯值得养成把题目给的每组样例都单独跑一次而不是一次性跑全部。样例 1 考察段内累加样例 3 考察连续单字符样例 4 考察长段样例 5 考察多段拼接它们各自覆盖不同的逻辑分支一组一组过能最快定位问题出在哪个分支上。6. 状态累加思维的迁移路径6.1 从 Score 到状态机这道题的内核是一个极简状态机只有两个状态“处在 O 段中”和“不在 O 段中”迁移条件是当前字符状态附带一个计数。当你把cur理解成“状态值”把cur 0理解成“状态重置”把ans cur理解成“状态值向累积器的输出”这三个动作就变成了一套通用模式。这套模式在更复杂的题里反复出现统计最长连续相同字符、判断一段序列里最长平台、统计括号嵌套深度、计算连续打卡天数等等。它们的共同点是“当前状态依赖前一个字符且会因某个字符而中断”。遇到这类题先问自己三个问题状态是什么什么时候增长什么时候重置回答完这三个问题代码基本就成型了。6.2 同类型题目的对照如果你想把这种思维练扎实可以按下面的顺序做几道同类题。第一类是“统计最长连续段”只需要把累加改成取最大值其余结构不变。第二类是“统计连续段的个数”状态重置时顺便给计数器加一。第三类是“带权连续段”每个 O 的分值不再是位置而是某个给定的递增序列。这三类变形的共同点是主循环骨架完全一样只有状态迁移的动作和输出形式在变。我建议你不要一道一道从零写而是先写好 Score 的骨架然后每次只改一行观察结果怎么变。这种“最小改动实验”对理解代码结构的帮助远大于刷十道互不相干的题。6.3 给入门者的练习节奏我给刚学编程的朋友的建议是第一天把 Score 用主力写法写三遍不看笔记直到能默写第二天用双指针写法重写一遍重点琢磨边界怎么处理第三天写一份对拍脚本用随机数据验证自己的两种实现第四天去做两道变形题。这个节奏看起来慢但磨刀不误砍柴工。很多人急着刷题量结果每道题都是“照着题解抄一遍跑通就走”碰到稍微变形的题立刻懵。而把一道极简题彻底吃透你获得的是一个可复用的模板和一套自查流程后面几十道同类题的效率反而更高。提醒一句不要在没想清楚状态定义的情况下开始敲代码。先在纸上列出变量清单和迁移规则哪怕只有三行也比边写边改强。最后分享我在实际带人过程中最有用的一个经验每次有人问“为什么我的代码不对”我第一句话都问“你的 cur 定义在哪一行”。十个里有六个答完自己就发现问题了。这道 Score 题的所有坑几乎都能归结到“状态变量的作用域和复位时机”这一个点上把这个点彻底想通它就不只是一道入门题而是你写所有遍历类逻辑时的一个底层检查项。