洛谷P1125笨小猴：Python字符串统计与质数判断的边界陷阱

做洛谷P1125这道题的时候我第一反应是“这不就是个字符串统计加质数判断嘛”结果第一次提交就被WA打脸了。问题出在minn的取值上——我用了长度为26的数组统计每个字母出现次数然后直接对整组数求最小值完全没想过那些没出现过的字母计数值是0也会被算进最小值里。折腾了好一会儿才反应过来题目里说的“出现次数”指的是“该单词中实际出现过的字母”而不是26个字母全算上。这道题在洛谷的难度标签不高但它确实把新手最容易犯的几个错误集中到了一起计数方式、边界条件、质数判定。这篇文章就把我踩过的坑和最终理顺的完整思路记下来给刚开始用Python刷洛谷的朋友做个参考。1. 题目拆解笨小猴到底考什么1.1 从一段题面到一个清晰的算法模型P1125“笨小猴”的题面很简短给一个单词统计每个字母在单词中出现的次数找到出现次数最多的maxn和出现次数最少的minn如果maxn - minn是一个质数就输出“Lucky Word”和这个差值否则输出“No Answer”和0。抛开题面里那个小故事“笨小猴”本质上就是一个三段式的算法题输入一个只含字母的字符串原题说明保证输入的是小写字母组成的单词长度不超过100处理统计各字母出现频率求出频率最大值和最小值计算差值判断差值是否为质数输出按题目要求的格式分两种分支输出对应内容用一个具体例子走一遍就清楚了。比如单词是“error”字母出现次数是e:3、r:2、o:1最大值maxn3最小值minn1差值22是一个质数所以输出“Lucky Word”和“2”。整个过程没有任何高级算法全是基础操作但它把字符串处理和数论判断串起来了非常适合作为入门阶段的练习。很多人觉得这道题简单但细节非常容易翻车。最大的坑就是minn到底应该怎么取。我一开始用长度为26的数组记录所有字母的出现次数也就是把‘a’到‘z’每个位置都初始化为0没出现过的字母就一直是0循环更新单词里出现的字母。这么做看起来逻辑没问题但最后对整组数取min时那些0也被算进去了导致minn恒为0极差要么等于maxn要么出现奇怪的偏差。尤其在有些单词里某个字母出现了但它的次数并不是最小值时这个偏差会导致最终判断结果完全错误。正确的理解是minn只考虑“在单词中出现过的字母”中最小的那个次数。换句话说没有出现的字母不参与最小值的比较。理解了这一点这道题的核心算法模型就清楚了。1.2 为什么这道题简单却不该轻视我在给朋友讲这道题的时候打了这样一个比方它像学炒菜时的“番茄炒蛋”食材常见、步骤简单但每个人做出来的味道都不一样因为细节藏在火候、盐量和顺序里。P1125同样是“看起来都会一提交就错”的典型。这道题隐藏了三个考点第一字符频率统计的写法。是用字典还是Counter还是定长数组选择不同后面取min和max的方便程度完全不同。第二对“出现次数”这个概念的理解。题目明确说的是“每个字母在单词中出现的次数”对应的minn是所有非零计数里的最小值这一点题面没有特别强调但样例数据其实能帮你验证出来。第三质数判断的边界。质数定义是大于1的自然数中只能被1和它本身整除的数。所以1不是质数0也不是质数负数更不是。差值算出来之后如果等于1直接就是No Answer很多人在这一点上栽跟头。这三个考点单拎出来都不难组合在一起就特别容易互相干扰。老手看到这道题的题面脑子里会自动浮现“Counter max/min 质数函数”的完整框架新手则往往像我当初一样把注意力全放在“怎么统计字母”上忽略了取值范围的细节。这正是这道题作为入门题的价值所在。2. 用Python实现的完整思路2.1 数据读入与预处理洛谷的输入输出是非常标准的OI风格使用标准输入输出不要有多余的提示文本。Python里直接用input()读一行就够了。因为OJ的输入数据后面通常会带一个换行符所以读到字符串后先做一次strip()把首尾空白字符清掉避免后面因为隐藏的换行或空格导致统计结果异常。这里有个经验很多初学者会习惯写word input()后直接用大部分情况下没问题但如果输入数据末尾不小心带了空格或\rWindows环境下常见就会出现莫名其妙的错误。养成strip()的习惯能省很多事。当然要注意如果题目里的单词允许中间有空格比如句子那就不能用strip去掉内部空格但P1125的输入明确是单个单词直接用没问题。关于字符大小写原题保证输入单词由小写字母组成所以通常不需要额外处理。假如你想让代码更健壮可以统一word word.strip().lower()这样即使输入混合大小写也能正常统计。我在准备这个题的时候就顺手动用了lower()写起来不多但至少能应对一些非标准的测试数据。2.2 统计字符频率的三种写法与对比统计字符串中各字符出现次数Python里至少有三种常见写法。我整理了一下顺便比较了它们的适用场景。第一种是自定义字典手动统计count {} for ch in word: count[ch] count.get(ch, 0) 1第二种是用collections.Counter一行就能完成统计from collections import Counter count Counter(word)第三种是定长列表适合处理已知字符集的情况比如全是小写字母cnt [0] * 26 for ch in word: cnt[ord(ch) - ord(a)] 1三种方式的区别我用表格理了一下方式代码量取min/max的便利度适用场景自定义字典稍多需values再计算通用任何字符集合Counter最少最方便values就是实际出现字符的计数通用推荐定长列表中等需排除0值字符集固定且已知对于P1125来说我推荐直接用Counter。它返回的values()天然只包含出现过字符的计数值取min和max时不会碰到0。如果用定长列表就得自己过滤掉0否则就会踩到开头说的那个坑。如果你确实想用定长列表练手也可以但记得取最小值时要这样处理cnt [0] * 26 for ch in word: cnt[ord(ch) - ord(a)] 1 valid [x for x in cnt if x 0] maxn max(valid) minn min(valid)这样过滤之后就安全了。其实这个过滤的思路也是理解题目语义的一种方式你先把没出现过的字母从统计结果里排除再取最大值最小值逻辑上就完全对应题面了。2.3 极差计算的正确姿势极差就是maxn - minn。如果用Counter实现非常直接maxn max(count.values()) minn min(count.values())这里要注意一个边界情况如果单词只有一个字符比如输入a那么Counter的values只有一个值{1}maxn和minn都是1极差是0。0不是质数所以正确输出应该是No Answer和0。这个逻辑在代码里能自然覆盖到因为质数判断函数对0会返回False。再举一个更容易出错的例子。单词是aaaabbb四个a三个bmaxn4minn3极差11不是质数输出No Answer和0。这里的极差虽然只有1但如果你犯了我之前的错误用26个字母的数组做统计minn会取到0极差变成4而4不是质数结果碰巧还是No Answer——但输出会变成4接受不了。再比如单词abmaxn1minn1极差0正确输出是No Answer和0如果错用0参与min极差1同样输出No Answer但数字还是0这个靠不巧碰对是不可靠的。所以真正的解法必须把语义搞清楚不能靠巧合。2.4 质数判断函数的写法与边界质数判断是数论里最基础的内容想写好也得注意边界。我建议的参考函数如下def is_prime(n): if n 2: return False i 2 while i * i n: if n % i 0: return False i 1 return True用到i * i n这个循环条件是因为如果n有一个大于sqrt(n)的因子那么它一定对应一个小于sqrt(n)的因子所以只需要检查到平方根就够了。比如判断29只需要检查2到5之间的数有没有整除29的判断97检查2到9之间的数就够了。这样时间复杂度是O(sqrt(n))对P1125这种差值不超过100的数据来说完全够用。需要特别强调一下if n 2: return False这行不能省。1既不是质数也不是合数0也不是负数更不用说。有些人图省事写成if n 1: return False然后从2开始循环这样对负数会出问题而且当n0时也会漏掉。我见过不少新手因为这样写在测试某个极差为1的数据时才意识到边界没处理好。最稳妥的写法就是n 2直接排除。另外这个函数里循环可以优化成只检查奇数加特判2但对这个数据量而言意义不大。刷题入门阶段先把正确性放在性能前面等遇到真正的大数据再考虑优化也不迟。3. 完整代码与逐行解析3.1 一份可直接提交的参考代码下面给出一个可以完整提交到洛谷的Python 3参考实现。为了帮助阅读我拆成几个函数加主程序提交时直接复制即可不需要删注释。import sys from collections import Counter def is_prime(n: int) - bool: 判断n是否为质数。 if n 2: return False i 2 while i * i n: if n % i 0: return False i 1 return True def solve() - None: word sys.stdin.readline().strip().lower() if not word: return counter Counter(word) maxn max(counter.values()) minn min(counter.values()) diff maxn - minn if is_prime(diff): print(Lucky Word) print(diff) else: print(No Answer) print(0) if __name__ __main__: solve()这段代码的目标就是完全按题意输出。使用sys.stdin.readline()来读一行跟input()效果一致但我会解释一下为什么要写得更“底层”因为它更贴近OI选手的习惯。.strip()清理换行和多余空格.lower()统一大小写然后Counter统计频率。接着取最大最小值、求差值、判断质数、按分支输出。3.2 代码中几个容易被忽略的设计细节第一个是主程序入口的if __name__ __main__:。这种写法在竞赛代码里不必须做到P1125这个阶段也不需要写但养成这个习惯对你以后写工程化一点的Python代码有好处它可以让模块既能被导入又能独立运行。竞赛提交时这么写完全不影响正确性。第二个是sys.stdin.readline()相对input()的一点区别。input()内部会对读取的内容做一次strip处理而sys.stdin.readline()不会需要手动做strip。我一般还是用sys.stdin.readline()因为读数据量和执行效率在大量输入时更高一点。虽然P1125的数据量体会不出差距但作为习惯保留下来也不错。如果你更喜欢input()也完全可以两者在这个题目上没区别。第三个是函数拆分。虽然这题直接几行也能写完但拆成独立的is_prime()和solve()有两个明显好处一是让主逻辑看起来清晰二是方便本地单独测试质数函数。刷题不只是为了过题好的代码结构对后续复盘也有帮助。3.3 洛谷评测时关于输入输出的三个细节洛谷是Online Judge系统它要求程序从标准输入读取数据、向标准输出打印结果评测机拿你的输出和标准答案比对。这里有几个实际经验第一语言选择要选对。洛谷的Python语言选项中通常有Python 3、PyPy 3等提交时选Python 3或PyPy 3都可以。P1125对性能要求极低选Python 3就行。第二输出格式要完全匹配。题目要求输出两行第一行是“Lucky Word”或“No Answer”第二行是对应的数字。要注意大小写单词中间有一个空格末尾不要有多余空格。这些都可能导致“Presentation Error”或者WA。我刚开始刷题时经常因为多打了个空格被判PE后来就养成把所有输出都用print()单独一行、不加任何多余内容的习惯。第三本机运行结果正确不代表提交一定正确。尤其要注意换行符差异和路径中的特殊字符。像P1125这种字符串处理题本机用IDE跑跟OJ跑通常没区别但如果用的是Windows输入里的\r可能会干扰用了strip()之后就不会有问题。这也是我坚持读入后做清理的原因。4. 实测踩坑与错误分析4.1 最常见的WA原因minn统计到了0这应该是P1125评论区出现频率最高的问题也是我自己的首杀WA原因。先贴一个错误套路# 错误示例 cnt [0] * 26 for ch in word: cnt[ord(ch) - 97] 1 maxn max(cnt) minn min(cnt) # 这里的minn几乎一定是0 diff maxn - minn这段代码看起来逻辑完整数组统计次数、取最大值、取最小值、算差值。但问题在于cnt数组里有大量元素始终保持0min(cnt)得到的一定是0而不是“出现在单词中的字母的最小次数”。比如单词abccnt里a、b、c各1次其余23个位置都是0min(cnt)0极差就变成了1而正确答案的极差是0。关于这个坑我在洛谷题解区也看到不少人提到。总结一下两种正确姿势要么用Counter直接统计实际出现字符要么在定长数组基础上先过滤掉0。不管哪种核心都是“只对出现过的字符求最小值”。另外还有一个细节值得提醒就算单词里某个字母确实出现了如果它的出现次数刚好是0那说明这个字母根本没有出现在单词里所以不该参与min判断。很多直觉性错误都是因为把“数组所有位置”和“实际出现的字符”混在一起了。4.2 质数判断丢掉1这个特殊边界这道题题面里专门提到质数定义中的“大于1的自然数”。但很多人在实现is_prime时只考虑循环检查因子没有对1做单独处理。我见过这样一个写法# 错误示例 def is_prime(n): for i in range(2, n): if n % i 0: return False return True这个函数的问题很明显当n1时range(2, 1)是空区间循环不执行直接返回True于是1被错误地判成了质数。在P1125中如果某个单词的频率极差恰好是1比如aaaabbb这种情况你的代码就会输出Lucky Word和1直接WA。正确写法就是之前展示的那样最前面加一个if n 2: return False。请把这个条件视为质数判断题的标准开头不管是P1125还是后来的其他数论题你都会用到它。4.3 其他容易忽略的运行时问题P1125题目保证输入的是长度不超过100的小写字母单词所以理论上几乎不会有奇怪的运行时错误。但刷题过程中总会有人遇到一些小问题我总结了几条第一程序没有输出。这通常是因为读入逻辑导致空处理如果你写成word sys.stdin.readline().strip()然后没有对空字符串做判断后面Counter统计一个空字符串时values是空的直接max()会抛ValueError: max() arg is an empty sequence。虽然原题不会给空数据但本地手工测试空输入时程序就会崩溃。所以我在参考代码里加了if not word: return虽然这行对评测没有实际影响但能防止本地意外。第二Python版本语法差异。如果你用的是Python 2那么print写法、整数除法等都有区别。现在洛谷主流是Python 3初学者学新不用旧直接装Python 3.10以上版本就行。热词里也有“python安装教程”“python下载”这类需求我这里特别说明一下装解释器选官网最新稳定版即可安装时记得勾选“Add Python to PATH”否则命令行里打python会提示找不到命令。第三IDE配置问题。经常有人问VSCode怎么配置Python环境这个跟本题没有直接关系但会在刷题过程中卡住你。简单说在VSCode里装好Python插件然后按CtrlShiftP选择“Python: Select Interpreter”指向你安装的解释器再在终端里python xxx.py就能跑了。如果懒得折腾也可以用洛谷在线IDE或本地IDLE直接运行。4.4 洛谷评测结果的常见状态速查表我在刷题过程中总结了一张洛谷评测状态的对照表这是每个新手都会用到的评测状态表示含义常见原因Accepted通过代码正确Wrong Answer答案错误逻辑缺陷、边界条件没考虑、输出格式不对Presentation Error格式错误多空格、多换行、输出多余内容Runtime Error运行时错误访问越界、空序列取max/min、除零或模块级错误Compile Error编译错误语法错误、Python版本不兼容等P1125的WA错误里我前面列出的minn统计问题是绝对大头。PE也有基本都是print时多打了空格。RE的情况较少但空序列取max/min是可能出现的。翻评论区的题解时经常能看到各种错法我一开始还不太理解为什么这么简单的题会有这么多人错——后来自己错了一次就明白了。5. 从P1125延伸出去相关题目与刷题思路5.1 其他几道值得顺手练的洛谷基础题P1125做完之后如果你想趁热打铁巩固同类技巧可以试试下面几个题目。首先是洛谷P1011这是一道和统计、模拟相关的题题目本身考察的是对循环和数学规律的理解跟着题面一步步模拟把每一步的变量变化搞清楚非常锻炼基础能力。然后是P1508这道题偏向二维表格的搜索/动态规划基础让你从纯字符串处理过渡到表格型问题也能体会一下“题目描述花里胡哨但核心其实很简单”的套路。还有P9755它属于综合一点的题会用到更多的输入处理和条件判断正好用来检验你对基础语法的熟练度。这些题和P1125的共性在于题面都不复杂但都需要你先把文字描述转化成准确的算法逻辑再动手写代码。我推荐刷题顺序是“先自己分析→写一遍→错了再看题解→理解后重新写一遍”这个过程比单纯抄题解有效非常多。5.2 把频率统计从题目里带进真实场景P1125让你统计单词中字符出现次数本质上是一种非常基础的频率统计能力。这东西在真实世界的应用随处可见最常见的例子是词频分析。比如你想分析一个网页里哪些词汇出现频率最高用来快速了解页面主题核心思路就是分词、统计次数、排序取TopN。这和P1125里的Counter统计是同一个套路。再比如做爬虫时想统计某个论坛用户发言的关键词或者做数据分析时想统计某一列文本字段的类别频次底层也都是这个逻辑。Python爬虫、数据分析、量化策略代码里都有类似需求所以千万不要觉得P1125只是“竞赛玩具”。从这道题里学到的“统计→筛选→判断”的流程完全可以迁移到很多真实项目里。甚至你后面想做一个简单的文本情感分析第一步都是先做频率统计。我认识一个做数据分析的朋友他处理Excel里的文本列时经常用的就是collections.Counter直接统计类别频次几行代码就能搞定原来用Excel透视表半天操作的事情。这也是为什么我建议初学者认真掌握Counter这个工具库它的用处远远不只在算法竞赛里。5.3 关于环境配置和编辑器选择的一点建议热词里出现了“vscode python环境配置”“python安装教程”“pycharm配置python环境”这些词估计有不少人卡在了写代码之前的准备环节。我来分享一下最省心的配置方案。如果你刚开始刷题先在电脑上装好Python解释器然后随便用一个文本编辑器写代码就够了连IDE都不需要。等刷到几十道题觉得需要调试功能了再上VSCode或PyCharm。新手最容易犯的错误是装了一堆工具但没装解释器或者装了解释器却在编辑器里没选对导致F5运行无反应。排查顺序就三步确认python命令在终端可用确认编辑器选择的解释器是那个Python确认打开的是你自己写的.py文件。洛谷本身也有在线代码提交页面你完全可以不装任何环境直接在网页上写代码提交。但对长期刷题来说本地有个环境更方便因为你可能需要反复测试、打印中间结果。我的建议是装Python 装VSCode 装Python插件三步到位总共就十几分钟。5.4 这道题对后续竞赛学习的启发P1125虽然简单但它代表了一类非常典型的入门题目题意清晰、算法基础、陷阱藏在边界。做这类题目的练习价值在于你会慢慢形成一种“读完题先想边界条件”的直觉。我后来刷更多题的时候回头看P1125越发觉得它其实在教三件事第一数据结构的选取会影响后续操作的复杂度选对了Counter极差计算一行搞定选错了数组还得额外过滤第二边界条件质数定义里的1、频率统计里只算出现的字符必须在编码前想清楚第三程序不是写完就完了要自己在本地构造几组测试数据包括单词只有一个字符、所有字母频率相同、极差等于1这些情况全部验证通过再去提交。这份直觉是刷题的核心收益。你以后遇到更复杂的算法题时比如后面热词里提到的各种动态规划、图论题目它们的基本盘依然是“把问题抽象成模型→把模型翻译成代码→把边界情况全部测试到”。P1125就是这条路径上最朴素的一块基石把它吃透了后面会顺很多。我后来跟别人聊起刷题路线时经常说不要嫌这道题简单真正能一次性写出满分代码的人其实不多。6. 我的本地测试套路与提交前的自检清单6.1 构造覆盖边界条件的测试数据写完代码之后我只在本地跑一次样例就直接提交那我敢保证你大概率会WA。正确做法是先构造一组覆盖各种情况的测试数据每题适用P1125也不例外。我通常会准备这样几组用例。第一组是题目给的样例这不用说保证基本逻辑正确。第二组是只有一个字符的单词比如输入a期望结果是No Answer和0用来验证极差为0的边界。第三组是重复频率相等的单词比如abab两个字母各出现两次maxn2minn2极差0。第四组是极差为1的单词比如aaaabbb期望输出No Answer和0专门验证质数判断是否排除了1。第五组是较长的随机单词我用Python的random模块生成一个长度100的随机小写字符串确认程序不会因为长度或随机字母分布报错。把这些用例一个个跑一遍该通过的通不过该拒绝的没有拒绝逻辑漏洞就全暴露了。很多WA其实不是大问题就是某个边界会产生错误分支手工构造边界用例是最快的发现方式。6.2 提交前的三项自检每道题提交前我都会快速检查三件事你也可以参考。第一读入部分有没有做strip。如果你的代码里用了input()问题不大如果用了sys.stdin.readline()务必确认有strip否则极易在Windows本机环境与Linux评测环境之间产生差异。第二输出部分是否严格对齐题面。不要自作主张在行首行尾加空格也不要打印调试信息。调试信息记得注释掉再提交。这个问题我在新手期犯过好几次print(debug:, diff)这种代码留在里面直接导致WA。第三是否存在未捕获的运行时异常。比如空字符串时取max/min会崩质数判断如果没有前置n 2判断也会逻辑错误。P1125的数据一般不会触发这些问题但任何边界自测都建议做一下确保程序健壮。这三项检查加起来不超过两分钟但对通过率的影响是决定性的。我后来刷了上百道题依然保留着每次提交前先跑一遍自测用例的习惯。6.3 为什么我依然推荐先用最简单的方式做出来有些读者看到代码里用了Counter可能会疑惑这么简单的题自己写一个字典循环不也一样吗甚至有人觉得用库是“作弊”。我的看法是竞赛考察的是算法思维和解决问题的能力工具库是帮你聚焦核心逻辑的不是作弊。Counter是Python标准库的一部分洛谷环境明确支持用起来完全合规。不过我也理解入门阶段适当用最“原始”的方式实现一遍是有价值的。比如你手动写一个字典循环你会更理解“键值对存储”“获取不存在的键时如何给默认值”这些基础概念这对后续学习很有帮助。我自己的建议是第一遍可以不用Counter老老实实写一个字典计数第二遍再用Counter重写然后感受一下代码的简洁程度。两道版本都跑通之后你对这道题的理解会比直接复制题解深得多。另一个要注意的是刷题不是越炫越好。有人为了显得厉害明明一句话能做完的统计偏要写一堆位运算或高级函数这对新手完全没必要。先保证正确再追求简洁最后才考虑性能。P1125这题能用最直接的方式做出来你就已经完成目标了。后面遇到有严格时限的题目时再来优化性能也来得及。6.4 如果还想要挑战一点难度怎么办如果真的觉得P1125太轻松可以考虑两个方向的变体。第一个是把输入从单个单词变成一段文本统计整段文本的字符频率甚至统计单词频率极差的计算对象也相应改变。第二个是增加数据量比如输入一个长度达到10^6的字符串这时你需要考虑Counter的效率和内存占用可能还要引入一些空间换时间或时间换空间的策略。这些变体本身已经接近一些中等难度题目的雏形了。我在练习Python爬虫和文本分析时处理大段抓取下来的正文用的频率统计方式就和这个扩展方向完全一致。所以从P1125“毕业”之后把这些技能迁移到真实项目中是很自然的事。刷题不只是为了刷题把每道题作为后续工具能力的一次微训练这个思路我一直都很推荐。