UVa 1585这道题很多人刷OJ的第一步就是它。题目给一个由O和X组成的字符串O表示回答正确X表示回答错误计分规则一句话就能说清连续正确时得分从1开始递增遇到X就归零最后输出总分。网上很多地方把它归类为“简单统计”代码确实不超过二十行但我带新人刷题这几年发现越是这种简单的题目越能暴露出读题、输入处理、边界测试这些基本功的差距。这篇文章就把Uva1585 Score从题意拆解、代码实现、常见坑到思维扩展完整讲一遍适合刚接触算法竞赛的初学者也适合想把这题讲给别人的学长学姐参考。1. 拆题为什么说这是最简单的状态统计1.1 题意还原连续答对如何累进计分先明确输入输出格式。题目会先给一个正整数T表示测试用例数量随后每行给一个字符串字符串只包含O和X长度不超过80。对于每组输入输出一个整数代表总得分。计分规则看起来简单但必须准确理解“累进”两个字。比如字符串OOXXOXXOOO手动算一遍前两个O第一个得1分第二个因为是连续第二个得2分累计3分遇到X连续状态清零后面跟了一个O得1分此时累计4分又遇到两个X状态再次归零最后三个O分别得1、2、3分最终总分是120010012310。这里最核心的不是加法本身而是“当前的连续正确答案数”这个状态。它决定了本次答对能拿多少分并且会在遇到X的瞬间被重置。用生活里的例子打比方这很像很多App的连续签到奖励连续签到的第1天给1个积分第2天给2个积分中间断签一天下次又从1个积分重新开始。只要想清楚这个类比代码逻辑就顺了。还有一个小细节字符串里只有O和X两种字符没有大小写问题也不会出现空格。所以读取的时候不用考虑复杂的分隔符用常规字符串读入即可。很多新人在这里会想多以为O和X之间可能有空格或者其他符号实际上题目保证只有这两个字符放心处理就好。1.2 “简单统计”简单在哪又难在哪说它简单是因为只需要一次从左到右的扫描。字符串长度即使取到上限80甚至扩展到十万也都能在O(n)时间内算完额外空间只用了几个整数变量属于典型的时间O(n)、空间O(1)单遍历统计。那难在哪难在“状态维护”的意识。很多新手一上来想的是“我要不要先数一数这串里有几段连续的O”然后对每段求等差数列和。这个思路也能做但先切分再逐段求和代码量明显更多还要小心段与段之间边界处理。而直接用一个滚动变量cnt记录“当前连续O的个数”读到O就cnt自增并把cnt累加到总分读到X就把cnt置零是更贴近题目描述的做法。我把这两种思路放在一起对比一下你就明白为什么滚动变量更优。笨办法大概是先遍历一遍找到每一段连续O的起点和长度存成若干区间再对每个区间算12...len累加。这个写法需要额外的数组存区间代码分支也多。而滚动变量写法不需要额外存储每读到字符当场决定怎么更新逻辑完全同步。所以这道题虽然被标注为“简单统计”其实暗含了一个很重要的思想能用一次性遍历解决的问题不要拆成多次扫描。这也是后来区间统计、滑动窗口题目的雏形。理解了这个再看其他统计类问题比如统计单词个数、统计行数思路都是先定义清楚状态再决定怎么更新状态。2. 代码落地C和Python双版本逐行拆解2.1 C语言版本OJ提交的稳妥写法在UVa这类老牌OJ上C语言依然是最常见的提交语言。我的首选写法如下#include stdio.h int main(void) { int T; scanf(%d, T); while (T--) { char s[100]; scanf(%s, s); int score 0; int streak 0; for (int i 0; s[i] ! \0; i) { if (s[i] O) { streak; score streak; } else { streak 0; } } printf(%d\n, score); } return 0; }几个值得抠的细节数组长度写成100因为题目说字符串长度不超过80开100留足余量。有人会问为什么不开刚好80因为C字符串末尾要有\0长度80的字符串实际需要81个字节的存储空间开80必越界。多留一点空间不会浪费多少内存也能避免某些版本题目描述微调后的越界风险。没有理由在这上面省几个字节。循环条件用s[i] ! \0而不是i strlen(s)。原因很简单strlen每次循环都要重新遍历一次字符串求长度虽然80个字符影响不大但一旦养成这个习惯将来处理几十万字符时就会白浪费性能。这个习惯很小却能在更复杂的题里帮你避开性能坑。用scanf(%s, s)读取字符串而不是gets()。%s会自动跳过一行开头的换行和空格gets()会把整个行读进来而且新版编译器对gets有安全警告。在需要逐行读字符串的老题里scanf(%s)是最省心的选择。变量名用streak和score而不是a和b。这个题逻辑简单变量名叫什么都对但在更复杂的场景里一个能准确表达含义的变量名可以帮你少掉一半头发。streak表示连续状态score表示总得分写完代码回头看时一目了然。2.2 Python版本逻辑更直接的写法Python刷这题会显得很直接字符串操作和输入处理都比较友好。一个完整可提交的版本t int(input()) for _ in range(t): s input().strip() score 0 streak 0 for ch in s: if ch O: streak 1 score streak else: streak 0 print(score)逻辑与C语言完全一致。唯一的注意点是input().strip()用来去掉字符串两端的空白字符防止行尾换行符影响判断。有的人或许会想用sum加生成器做一行流但可读性反而差。真到比赛或面试时清晰的逻辑比炫技重要得多。对于输入规模较大的情况可以用sys.stdin.read()一次性读入所有内容再切分import sys data sys.stdin.read().split() t int(data[0]) for i in range(1, t 1): s data[i] score 0 streak 0 for ch in s: if ch O: streak 1 score streak else: streak 0 print(score)这种写法在测试数据特别多、用input()逐行读频繁触发IO时会更稳。对这道题来说用不上但值得知道。很多人第一次接触这两种语言时会有个困惑同一道题为什么C语言要写这么多头文件和变量声明Python三五行就写完了答案很简单两种语言定位不同。C语言更贴近计算机底层适合培养对内存、边界的敏感度Python的抽象程度高适合快速验证思路。在刷题入门阶段我建议你至少用一种语言把这道题真正跑通同时知道另一种语言怎么实现这样才能在解题和工程应用之间来回切换。2.3 复杂度与内存为什么它能应对任意输入设每个字符串长度n代码只扫描一次每个字符做常数次加法或赋值因此时间复杂度是O(n)。对T组输入总时间是O(Σn_i)。全题只用了几个整型变量和一个长度100的字符数组额外空间O(1)。最坏情况可以算一下如果所有字符都是O且长度为80那么总分是12...8080*81/23240不会超出int范围。哪怕把长度扩展到一百万且全是O总分也只是500000500000C语言的int容易爆需要用long long但这是另一个话题。放在这道题里int足够。有些同学可能好奇为什么这道题不引入一个数组来记录“每个位置的当前得分”当然可以比如score_at[i]表示第i个字符处如果为O这个O贡献的分数。但这里不需要因为我们最终只要一个总和不需要知道某个具体位置的贡献。这也是单遍扫描的一个判断标准如果只需要最终结果通常可以用滚动变量如果需要随时回溯中间结果才考虑用数组或前缀和。3. 踩坑实录新人在这个题上最常见的失误3.1 输入输出坑scanf、gets与换行符这道题最常见的翻车现场之一就是输入处理。尤其C语言新手喜欢这么写gets(s);然后发现第一组数据总是读取到一个空串。原因是前面用scanf(%d, T)读完数字后缓冲区里还留着一个换行符gets会把换行符所在的空行读进来。解决办法有两个要么改用scanf(%s, s)读取因为它会自动跳过所有空白字符要么在scanf之后加一个getchar()把残留换行符吃掉。我的建议是直接统一用scanf(%s)最省心。还有一个问题是数组越界。有人写char s[80]但题目说长度“最多80”实际上当字符串长度为80时末尾的\0需要占用第81个字节所以至少开81开100更保险。在OJ上越界不一定会每次都报错但一旦发生就难以排查属于典型的“本地能过、提交RE”问题。我见过更极端的情况是输入输出方向搞反。有人把样例输出直接抄成输入或者把每组输出的顺序写错。这类低级错误虽然不涉及算法但在比赛中特别容易丢分。一个笨但有效的习惯是每次提交前把题目样例重新手动输入一遍对比输出是否完全一致包括空格和换行。3.2 统计逻辑坑streak和score职责混乱我在答疑时见过最多的错误是下面这种if (s[i] O) { score; score streak; }看起来像是“连续得分加1、总分加上连击数”但实际算出来全是错的。问题在于混淆了streak和score的职责streak只负责记录“当前连续O的个数”score负责累加每一次答对时拿到的分数。正确顺序必须是streak先自增再把streak的当前值累加到score。不能反过来更不能在score上叠加两个量。另外一个隐蔽错误是漏掉else分支。有人只写了遇到O时的加分逻辑X时什么都不做结果字符串末尾的连续O还算对了但中间被X断开后再出现的Ostreak没有归零导致后续每个O都继续用增长后的streak计分输出会明显偏大。调试这类统计逻辑最好的办法是打印中间值。在循环里临时加一行printf(i%d s[i]%c streak%d score%d\n, i, s[i], streak, score);对照手动算例看每一步是否与预期一致。这道题数据规模小手动验算很容易别嫌麻烦。我经常说会调试的人和不会调试的人差距往往就在这种“多看中间状态”的习惯上。一次性把整题写完直接提交出了问题两眼一抹黑一行打印就能定位问题省下的时间足够再做两道题。3.3 自测用例清单与提交前检查提交之前强烈建议至少跑一遍下面的用例表输入字符串期望输出说明OOXXOXXOOO10题目给出的样例O1单个字符且为OX0单个字符且为XXXX0全错streak永远保持0OOO6连续三个123OXOXO3每次答对都只拿1分OOXOO6被X断开后重新累进OOOXXOOO12多段连续中间断开两次每一种都覆盖了一个特征单字符、全X、全O、交替出现、中断后恢复。如果这些用例全部通过统计逻辑基本就没有问题。提交前再检查三件事数组是否越界、输出是否每组单独占一行、是否把临时调试用的printf删干净。还有一点容易被忽略有些地方练习平台的输入格式和UVa原始题略有不同比如第一行也可能没有T直接用EOF判断循环结束。遇到这种情况可以把外层循环改成while (scanf(%s, s) ! EOF) { // 处理逻辑 }这种写法在题目没有明确给出测试组数时非常实用。建议你两种输入形式都练一遍以后遇到类似于“统计行数”“统计单词个数”的题就不会被输入格式卡住。4. 从一道入门题看统计思维能走多远4.1 从cnt到dp动态规划的最简雏形只要把这道题的streak单独抽出来它就是一个递推关系令dp[i]表示以第i个字符结尾的连续O的个数如果s[i] O那么dp[i] dp[i-1] 1如果s[i] X那么dp[i] 0最终答案就是所有dp[i]之和。这和我们在代码里用一个streak滚动更新的方式完全等价。streak就是dp[i]的滚动版本因为我们不需要保留历史所有值只关心当前位置的值。所谓动态规划最朴素的理解就是“用递推关系记录状态并不断更新”这道题恰好就是最浅显的例子。理解了这一层以后再遇到“最长连续递增子数组”“最长无重复字符子串”这类问题你会似曾相识都是在一遍扫描中维护一个状态变量遇到破坏状态的条件就重置。很多看起来复杂的问题底层都是一个不断累积、不断清零的循环。这也是为什么有些老师会把Uva1585放在动态规划专题的入门位置。虽然它不需要数组、不需要记忆化、更不需要状态转移方程的形式化写法但它已经把“状态”这个动态规划的核心概念提前演示了一遍。你越早体会到状态变量的意义后面学DP就越顺畅。4.2 工程里的统计代码量统计、流式词频、埋点事件这道题叫“简单统计”但“统计”在实际工程里的地位远不止如此。举三个很常见的例子一是代码量和注释率统计。要统计一个项目的有效代码行数你必须逐行扫描同时维护一个“当前是否在注释块内”的状态。遇到/进入多行注释状态遇到/退出遇到//整行算注释。这个逻辑和本题中维护streak几乎一脉相承状态在扫描过程中被不断更新、切换有效代码行累加成总量。很多开源平台统计仓库代码量时底层就是这样一套状态机逻辑。二是Flink实时计算里的词频统计。流式数据不断进来你要对每个单词维护累计次数事件到了就更新对应计数。这本质上也是一个滚动累积过程只是统计键从O/X变成了各种单词存储结构从单个变量变成了哈希表。我见过不少同学初学流式计算时觉得概念抽象其实回想这道题就会发现所谓实时统计无非就是“来一条数据更新一次状态”。三是移动端埋点里的点击事件统计。用户每次点击某按钮计数加一如果还要统计连续点击、频繁点击行为就得额外维护一段连续状态。这个连续状态的维护逻辑跟本题的streak就是一个模子刻出来的。很多数据分析报表背后都是这样的基础统计逻辑。所以不要小看这道入门题。它虽然只有几行代码却几乎是所有“单遍扫描状态维护”统计问题的最小原型。把这道题吃透后面遇到统计符合多个条件的个数、统计行数、统计单词个数等场景第一反应就不会是“把所有内容存下来再慢慢数”而是“我能不能在扫描过程中就把状态算清楚”。4.3 后续还能怎么练从这题延伸出去如果你想顺着这个方向进一步巩固我建议按以下顺序找题练。先做几道同等级的统计题比如统计一个字符串中连续相同字符的最长长度或者统计一段文本中单词个数。它们都是单遍扫描维护状态的典型。再把统计思想升级到前缀和。比如这题如果把每个位置的“当前得分”也记录成数组那么查询任意区间的总得分时就能用前缀和一次算出。这是从“单次统计”到“区间统计”的重要跳跃也是后续线段树、树状数组的前置概念。最后可以挑战一点点动态规划入门题比如最长连续递增子序列、最大子段和。你会发现核心思路仍然是“用一个变量记录当前状态根据新元素决定继续累加还是重置”。从Uva1585起步这条路线非常顺滑。这类题还有一个共同特点代码量都很少但要想清楚并不容易。我建议你在草稿纸上把状态变化过程画出来不要上来就抄代码。画过一遍状态变化比你盲写十遍代码都有用。我个人在帮新人改这题的时候还有一个习惯让他们在提交前把代码里的变量名读出来一遍。streak就是“连续得分串”score就是“总分”。如果这两个词在自己嘴里都分不清谁是谁那代码大概率也有问题。这道题确实简单但它是很多算法思维的起点值得花上半小时慢慢咀嚼而不是三分钟抄完题解就关掉。把这种小题目真正吃透比赶着刷十道“水题”收获大得多。