UVA 1585 Score：连续段状态累加与多组输入处理

UVA 1585 Score 这道题我在带新人练手的时候几乎每次都会拿出来原因很简单它的代码量不到二十行却能把“字符串遍历”“状态累加”“多组输入处理”这三件入门阶段最容易翻车的事情一次性暴露出来。题意非常直白——给一串只由O和X组成的字符O表示答对X表示答错每答对一题得 1 分但如果前面已经连续答对了若干题这一题的得分就要等于当前连续答对的题数。比如OOO得 1236 分OXO得 112 分。这道题适合谁看如果你刚学完循环和数组正在找一道“能完整跑通输入输出”的题目建立信心它是最合适的入门题之一如果你已经写过不少题但每次遇到“连续段”这类描述还是习惯性套双重循环那这篇里的状态建模思路可能正好补上你缺的那块。下面我不打算只贴一份能过的代码而是把从读题到 AC 的每一步推理、每一种写法的取舍、以及我在本地反复调试时踩到的坑完整摊开讲。1. 这道题真正考的不是遍历而是“连续”二字的建模方式1.1 把自然语言规则翻译成可执行的计算过程初学者最容易犯的错误是直接把题面里的“连续答对 k 题得 k 分”照抄成代码然后开始纠结“我怎么知道前面连续答对了几题”。这个纠结不是能力问题而是没把自然语言翻译成程序语言。程序的思维方式是任何一个位置上的得分只取决于当前位置的字符和上一位置累积的状态。我们不需要回头去数只需要让一个变量替我们记住“到目前为止连续答对了多少题”。这个变量我叫它run也就是“当前连续 O 的连击数”。规则就此变成两条读到O连击数加一本次得分等于新的连击数累加进总分读到X连击中断连击数清零本次得分是 0。用表格把逐字符的过程摊开比读十遍文字描述都清楚。以OOXOXOO为例位置字符连击数 run本位置得分累计总分1O1112O2233X0034O1145X0046O1157O227走完一遍得到 7。手工验算第一段OO贡献 3中间O贡献 1末尾OO贡献 3合计 7对得上。这张表的价值在于它证明了一个关键结论每个位置只需要 O(1) 的额外信息就可以算出该位置的贡献。既然每个位置的信息量是常数级的那么整串扫一遍就是线性的不存在“必须回头看”的必要。这就是状态累加类算法的共同特征——用一个变量承载历史用更新规则推演未来。1.2 为什么很多人的第一反应是双重循环我见过太多第一版代码长这样外层循环遍历每个字符一旦遇到O就内层循环往回数连续有多少个O。这个思路从直觉上完全说得通因为题目描述里有“前面连续答对了几题”这种回头看式的表述。但它的代价是 O(n²)。这道题字符串长度只有 80双重循环跑 6400 次操作评测机上连一毫秒都花不到所以它同样能 AC。真正的问题在于这种写法会让人形成一种错误的解题肌肉记忆遇到“连续”就条件反射地回溯扫描。这里要分清两个概念“连续”是一个状态而不是一段区间。当你把它当状态看就得到单层循环当你把它当区间看就得到双重循环。两者的差距在 n80 时看不出来在 n10⁵ 时就是 0.001 秒和 10 秒的差距。我通常会给新人建议这道题先用双重循环写一版跑通确认自己理解了规则然后强制自己用单层循环重写一遍体会那个run变量是怎么把 O(n²) 压成 O(n) 的。同一道题写两遍比写两道不同的题收获更大。顺带说一个容易被忽略的细节题目说的是“连续答对”而从X之后的第一个O开始连击数重新从 1 算起。这一点在代码里体现为run 0的重置动作。如果重置写成run 1或者干脆忘写就会出现“X之后的第一个O得 2 分”这种诡异结果——这类 bug 在本地小数据上极难发现因为看起来总分只差了一点点。2. 三种解法的取舍从 O(n²) 到 O(n) 再到闭式公式2.1 双重循环版本直观但重复扫描先把最朴素的写法放出来它是最贴近人类语言描述的版本#include iostream #include string using namespace std; int main() { string s; cin s; int score 0; for (int i 0; i (int)s.size(); i) { if (s[i] ! O) continue; // 从 i 往回数看连续有多少个 O int j i; while (j 0 s[j] O) --j; score i - j; // i - j 就是这一段里 i 是本段的第几个 } cout score endl; return 0; }i - j这个表达式的含义值得掰开讲j最终停在本段O左边第一个X的位置或者 -1而i是当前位置。两者之差正好等于“当前位置是本段连续 O 中的第几个”也就是本题要求的分值。这个技巧很多人在写的时候只是照抄实际上理解它能帮你以后做前缀和、区间长度这类题时少绕弯路。它的缺点是明显的每个O都要再往回扫一遍遇到全O的串内层循环平均要跑 n/2 次总复杂度 O(n²)。另外还有个小陷阱——while (j 0 s[j] O)里的j 0千万不能省否则s[-1]是越界访问行为未定义在本地可能侥幸不崩换台机器直接段错误。2.2 单次遍历 计数器最通用的状态累加这是本题的标准解法也是我实际写题时的默认选择#include iostream #include string using namespace std; int main() { int T; if (!(cin T)) return 0; while (T--) { string s; cin s; int score 0, run 0; for (char c : s) { if (c O) { run; score run; } else { run 0; } } cout score \n; } return 0; }核心只有五行。run承担了“当前连击数”这个状态score承担了“历史累加和”。每一次更新只依赖前一个时刻的状态这叫在线算法——数据边读边算不需要保存整串的历史理论上甚至可以把string换成一个字符一个字符地读空间从 O(n) 降到 O(1)。这里的run; score run;顺序不能颠倒。如果写成score run; run;第一个O就只贡献 0 分整串都会少算。这种顺序依赖型 bug 在阅读代码时几乎看不出来因为你看到的是两个正确的语句只是顺序错了。我的习惯是把它合成一行score run;前缀自增先执行语义上就是“先把连击数推进一步再用新的连击数计分”减少了出错的可能。Java 里这么写很自然C 里也有人觉得可读性差看你个人偏好但一定要确定自己清楚它的求值顺序。如果把run理解得更抽象一点它其实表示“如果当前位置是 O它应该得多少分”。有了这层理解以后遇到“连续上涨天数”“连续签到天数”“连续错误次数”这类变体你就知道该维护哪个变量了。2.3 按段统计的公式法k(k1)/2 的由来第三种解法换个角度先把串切成若干段连续的O每段长度记作 k这段贡献就是 12…k也就是等差数列求和公式 k(k1)/2。int i 0, n s.size(), score 0; while (i n) { if (s[i] X) { i; continue; } int j i; while (j n s[j] O) j; long long k j - i; score (int)(k * (k 1) / 2); i j; }这种写法的复杂度仍然是 O(n)因为每个字符只会被外层跳过或被内层扫过一次不存在真正的嵌套。从代码量上看它比第二种更长但它的好处是把“段”这个概念显式表达了出来遇到需要同时输出“最长段长度”“段的数量”“每段起止下标”的变体时这套骨架直接就能改。三种解法的对比解法时间复杂度空间复杂度优点适用场景双重循环回溯O(n²)O(n)最贴近题面描述容易想出来n ≤ 1000 的小数据或教学演示单次遍历计数O(n)O(n) 或 O(1)代码最短通用性最强绝大多数“连续段”类问题按段公式统计O(n)O(n)段信息显式便于扩展输出需要段长度、段个数等附加信息我个人的取舍标准是如果只需要一个总分用第二种如果需要输出段的额外信息用第三种双重循环只在新人第一遍练习时允许出现。还有一个必须提醒的溢出问题这道题字符串长度不超过 80全O时得分是 80×81/2 3240int绰绰有余。但如果题目把长度放大到 10⁵全O的得分是 5×10⁹ 左右已经超过 32 位有符号整数的上限约 2.1×10⁹这时候score必须用long long。很多人在原题上从不考虑溢出换个数据范围就莫名其妙 WA根子就在这里。养成习惯看到累加类题目先估算一下最大值再决定变量类型。3. 输入处理是这道题真正的隐形难点3.1 多组测试数据的读入模式这道题的第一行是一个整数 T表示后面有 T 组数据。这属于经典的“先读组数再循环”模式骨架非常固定int T; cin T; while (T--) { // 处理一组 }while (T--)的意思是“先用 T 的当前值判断真假再自减”。当 T 从 1 变成 0 时循环结束正好执行 T 次。这个写法在入门题里出现频率极高值得刻进肌肉记忆里。不习惯的话写for (int k 0; k T; k)也完全没问题语义更直白我个人在正式项目里更倾向后者。真正容易出事的地方是每组的变量重置。我见过的最典型 bug 是把score和run定义在循环外面int score 0, run 0; while (T--) { string s; cin s; for (char c : s) { /* ... */ } cout score \n; }这样第二组数据的输出会叠加上第一组的分数。本地只测一组数据的时候一切正常一提交就全错。这类错误的排查成本很高因为代码逻辑本身没错错的是作用域。给个防御性的建议所有与单组数据相关的变量一律定义在处理该组数据的循环体内部。宁可每次重新分配也不要图省事提到外面。C 里局部变量的构造销毁成本极低为这点性能冒 WA 的风险不值当。3.2getline与cin 混用时的换行残留这是输入处理章节里最经典的坑。当你先用cin T读组数再想用getline(cin, s)读整行字符串时第一组会读到一个空串。原因不复杂cin T只把数字从缓冲区里取走末尾的回车符\n原封不动留在缓冲区。紧接着的getline看到这个\n立刻认为“这一行结束了”于是返回一个空字符串。于是你的循环第一次执行直接空转输出一个 0后面的数据全部错位。解决方式有三种都能用// 方式一读完后手动吃掉换行 cin T; cin.ignore(); // 或 cin.ignore(numeric_limitsstreamsize::max(), \n); while (T--) { string s; getline(cin, s); // ... }// 方式二干脆全用 cin 本题字符串不含空格完全够用 int T; cin T; while (T--) { string s; cin s; /* ... */ }// 方式三先整体读入再按空白切分Python 里很常见这道题的字符串只由O和X组成不含空格所以我一般直接用cin s绕开整个问题。这里有一个判断原则字符串里可能出现空格就用getline不可能出现空格就用。用的时候不用操心换行残留用getline的时候必须处理。如果题目真的要求读整行比如字符串里含空格cin.ignore()那行千万不能漏。而且要放在cin T之后、第一次getline之前位置错了同样白搭。3.3 长度边界、数组大小与字符字面量题目明确字符串长度不超过 80。如果用字符数组而不是string数组至少开到 81留一个给\0保险起见开到 100 或 105。我看到有人开char s[80]短一个字符遇到恰好 80 长度的用例就会越界写入表现可能是答案错误也可能是运行时错误调试起来极其费劲。另一类更隐蔽的错误是把大写字母O写成数字0if (c 0) { // 错这是空字符永远不成立O是字符字面量ASCII 码 790是整数零赋给char后是空字符。两者在视觉上几乎一样编译器也不会报错结果就是所有字符都被判定为X输出恒为 0。这种错误我至少见过五六次包括我自己早年也犯过。避免的方式很简单字符比较一律加单引号且注意字体里 0 和 O 的区分写代码时把字号调大一点。同理判断X的时候写c X别写成c ! O之外的奇怪组合。虽然else分支天然覆盖了非O的情况但如果题目将来扩展到第三种字符else就不安全了。我倾向于显式判断if (c O) {...} else if (c X) {...}多打几个字换来的是逻辑上的明确。4. 排查链路实录连续 WA 之后的定位顺序4.1 先怀疑输入还是先怀疑逻辑拿到一个 WA新手最常见的动作是盯着核心循环反复看越看越觉得没问题然后开始怀疑评测环境。实际上排查是有优先级的我的固定顺序是这样的第一步确认程序输出的组数对不对。把输出改成每组先打印一个标记如果组数不对问题百分百在输入处理上跟计分逻辑一点关系都没有。这一条能挡掉大约一半的 WA。第二步用极小用例验证核心逻辑。手算O得 1、X得 0、OO得 3、OXO得 2。四个用例跑下来如果其中有错问题在状态更新如果全对问题在边界或输入。第三步才去看边界数据全O、全X、单字符、长度取最大值。这些用例专门用来打越界、未初始化、溢出。按这个顺序走绝大多数问题在五分钟内能定位。反过来如果一上来就盯着主循环看很可能看半小时也看不出所以然因为 bug 根本不在那儿。4.2 五类高频错误的定位对照表现象最可能的原因快速验证方法修复方式输出组数少于 Tgetline读到空行或循环条件写错每组前打印组号加cin.ignore()或改用第一组就错后面全错O写成了0打印读到的字符串改成字符字面量从第二组开始答案累加score/run定义在循环外手动跑两组数据移进循环体结果比预期小score run写在run之前用单字符O测试调换顺序最后一个字符丢失 / 崩溃数组长度不够或越界访问用最长用例测试数组开到 105这张表我基本是照着实际踩坑经历列的。其中“从第二组开始答案累加”这一条我印象最深——当年第一次做这类多组输入的题本地只测了一组就提交连着 WA 三次最后把中间变量打印出来才发现第二组的初始值是上一组留下来的。从那以后我形成了习惯本地测试至少跑两组数据哪怕题目的样例只有一组。4.3 自造测试用例的正确姿势学会自己造用例比刷十道题都管用。针对这道题我固定会跑这么一组6 O X OOO OXO OOOOOOOOOO XOXOXOXOXO预期输出依次是 1、0、6、2、55、5。这组用例覆盖了最短串、纯 X、纯 O、交替、以及较长纯 O顺手验证 10×11/2 55 这个公式。再加两个边界长度为 80 的全O预期 3240长度为 80 的全X预期 0。这两个用例专门验证数组边界和溢出。写完这些用例把它们存成一个文本文件用重定向一次性喂进去./a.out test.txt对比输出和预期一眼就能看出哪一组挂了。这个习惯我从入门一直保持到现在无论是刷题还是写业务代码先跑一组覆盖边界的用例能省掉大量回头返工的时间。还有一个容易被忽略的点输出末尾的换行。有的评测系统对行末空格和多余空行不敏感有的极其敏感。用endl还是\n都能过但\n不会每次都刷新缓冲区在大数据量下快不少。这道题数据量小两者无差别但从一开始就养成用\n的习惯将来能省下不少 TLE。5. 换个语言写一遍理解会更深一层5.1 Python 版本读入方式的差异同样的逻辑用 Python 写核心部分几乎逐行对应import sys def main(): data sys.stdin.read().split() if not data: return t int(data[0]) out [] for i in range(1, t 1): s data[i] score 0 run 0 for ch in s: if ch O: run 1 score run else: run 0 out.append(str(score)) print(\n.join(out)) main()这里的关键差异是读入方式。sys.stdin.read().split()一次性把整个输入按空白切开得到一个列表第一项是 T后面依次是各组字符串。这种写法在评测环境里非常稳因为它不依赖行结构也不怕行末有多余空格或者 Windows 换行符。很多人习惯用input()一行一行读在这道题上也能过但在大数据量的题目里input()的调用开销会明显拖慢速度。我的建议是只要是多组数据的题目Python 一律用sys.stdin.read().split()养成习惯之后基本不会在输入上栽跟头。另外print(\n.join(out))一次性输出比在循环里逐行print快得多在数据量大时差距能达到几倍。5.2 Java 版本Scanner之外的选项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 score 0, run 0; for (int i 0; i s.length(); i) { if (s.charAt(i) O) { score run; } else { run 0; } } sb.append(score).append(\n); } System.out.print(sb); } }Java 这边有两个细节值得提。第一while (t-- 0)和 C 里写法一致但 Java 的Scanner方法名是next()而不是读字符串和读整数分开得更明确。第二用StringBuilder收集输出再一次性打印而不是在循环里System.out.println这在多组数据的题目里能省下可观的 I/O 时间。Scanner本身比较慢如果题目数据量大到几十万组需要换成BufferedReader加StringTokenizer。这道题只有几组数据Scanner完全够用没必要为了炫技上复杂写法。三个语言版本对比下来核心循环的逻辑一字未改变的只是输入的读取方式和输出的缓冲策略。这恰好说明一个道理算法部分想清楚了语言只是壳。新手在选择语言上纠结的时间远不如花在把状态模型想透上。5.3 一个变体如果字符集扩大假设题目改成有三种字符O得分X清零?既不算对也不算错连击暂停但不清零。这时候问题就从一个简单的计数器变成了一个真正的有限状态机for (char c : s) { if (c O) { run; score run; } else if (c X) { run 0; } // ? 什么都不做run 保持不变 }改动只有一行但这行改动揭示了一件重要的事run不只是一个计数变量它承载的是“状态”。当状态转移规则变复杂时只要把每个输入字符映射到一次状态转移代码结构就稳如磐石。这个思路往大了说就是编译器词法分析器扫描字符流的方式、日志系统统计连续异常次数的方式、游戏里计算连击倍率的方式。它们的骨架跟这道题没有任何区别。我经常跟人说入门题的价值不在于题目本身而在于你从里面抽出来的那个模式能复用到什么地方。6. 从这道题带走的三样东西6.1 状态变量的命名与职责单一run这个变量名是我刻意选的不是随手写的cnt或者tmp。cnt太泛看到名字完全猜不到它在数什么tmp更糟等于告诉读者“我也不知道它是干嘛的”。run明确表示“当前连续长度”读代码的人一眼就懂。这道题里只有两个变量还体现不出命名的重要性。但当你在业务代码里维护十几个中间变量时一个语义模糊的名字会让后来接手的人多花半小时。我的经验是变量的名字应该能回答“它记录的是什么”而不是“它是什么类型”。run比cnt好consecutiveCorrect又太啰嗦找一个长度和语义的平衡点。职责单一同样重要。score只负责累加run只负责记录当前连击两者不交叉。如果图省事用score兼职做连击计数比如用score % 10反推代码会立刻变得不可读而且几乎必然出 bug。6.2 复杂度意识要从第一道题开始建立这道题数据规模小三种解法都能过所以很多人写完就不管了。但复杂度意识恰恰是在这种“怎么写都能过”的题里建立起来的因为等数据规模变大时你已经没有机会重新训练这个思维了。我的建议很具体每写完一版能过的代码问自己三个问题——最坏情况下的操作次数是多少如果数据规模放大一百倍还行不行有没有多余的重复扫描这三个问题花不了两分钟但坚持几十道题之后你对复杂度的手感会明显强于同龄人。6.3 一组必须自己动手跑过的用例集最后再强调一次本地测试的价值。这道题的样例通常只给一两组远不足以覆盖所有情况。我固定会跑的那组用例在上面第 4.3 节列过了建议你自己动手敲一遍别看现成的敲的过程本身就是在训练“什么样的边界容易出错”这种直觉。跑完之后把这份用例文件保存下来下次遇到类似的连续段题目直接改一改字符串内容就能复用。我自己维护了一个edge_cases目录按题型分类存放这些用例好几年前的还留着偶尔还能派上用场——这种积累看起来笨实际回报率很高。