洛谷刷题第二天：字符串边界判断与DFS递归枚举实战记录

今天是刷题打卡的第二天。昨天我还没完全适应节奏在洛谷上东看西看翻别人的题解研究评测机脾气结果真正A掉的题没几道。今天我不打算这么散漫了给自己定了三个目标把基础语法再顺一遍集中吃透“字符串处理”和“递归枚举”这两个知识点再留一道挑战题在晚上有空时做。一天下来我AC了四道题最大的突破是第一次独立写出了DFS递归代码。这篇文章就把今天的选题思路、每道题的完整思考过程、以及踩过的坑都记录下来给同样在洛谷刷题的读者做个参考。1. 第二天刷题题目怎么选1.1 从“随手做做题”到“有目的地刷题”第一天刷题的时候我踩了一个很典型的坑看见什么题顺眼就做什么看到一道题目长一点的直接跳过结果刷了半天AC的全都是“入门”难度里的简单水题几乎没有形成任何知识积累。第二天我调整了策略。我不再看一道做一道而是先花十分钟想清楚今天需要提升什么能力。洛谷的题目有明确难度分级从红色“入门”、橙色“普及-”、黄色“普及/提高-”到后面的绿、蓝、紫、黑依次变难。第二天这个阶段更适合做红色到黄色之间的题太低没挑战性太高容易挫败。我给自己定了一个“31”原则三道必须当天AC的题加一道挑战题。三道里第一道是热身水题目的是恢复手感、熟练输入输出第二道是今天想重点突破的知识点第三道是另一个知识点的巩固题。挑战题可以当天做做不出来也不强求整理好思路留到第三天继续。这比盲目刷题要有用得多因为每道题做完之后我能明确说出“我今天学到了什么”。1.2 今天的选题清单和难度梯度今天下午我实际执行下来选了这样几道题先列出来给大家看一眼。题号题目名称洛谷难度考察点预计用时P1001AB Problem红色入门基本输入输出5分钟P1427小鱼的数字游戏红色入门数组与逆序输出15分钟P1308统计单词数橙色普及-字符串处理、边界判断40分钟P1036选数黄色普及/提高-DFS递归、组合枚举、素数判断60分钟P1008三连击橙色普及-暴力枚举、全排列40分钟为什么这样排P1001让我的大脑从“周末慵懒状态”切换到“写代码状态”不需要动脑纯热身。P1427虽然简单但数组和下标这个东西是一切算法的基础做一遍等于提醒自己注意边界。P1308是今天的主攻题字符串处理在后续很多题目里都会遇到尤其是“单词边界”这个坑非常经典值得认真写一遍。P1036则是为了引入递归和DFS这道题是一个标准的组合枚举模板理解了它后面很多搜索题都会轻松很多。P1008是预留的挑战如果晚上还有精力就写写不出来也不影响今天的整体进度。2. 核心知识点拆解字符串边界与递归枚举2.1 为什么字符串边界判断是P1308的隐藏考点P1308“统计单词数”这道题表面上只是让你数一数某个单词在一段文章中出现了几次但真正做起来就会发现它考的不只是字符串查找而是“完整匹配”的概念。打个比方你现在要找文章里所有的“cat”如果直接用查找函数去搜那么“cat”出现了但“category”里的“cat”也会被搜到“concatenate”里的“cat”同样会被搜到这些显然都不是你要找的“完整单词”。这就是边界问题也是题目最容易出错的地方。我的处理思路是把待查找的单词和整段文章都先转成小写忽略大小写差异然后在单词前后各加一个空格再在文章前后也各加一个空格。这样搜索的时候直接查找“空格单词空格”这个模式就能保证只匹配完整的独立单词。比如“cat”变成了“ cat ”在“the category of cat”中搜索时“category”里的“cat”前后都不是空格所以不会被匹配到而最后的“cat”前面是空格、后面也正好是空格就能正确命中。另一个容易忽略的坑是读取输入的方式。洛谷的题目里需要查找的单词在第一行文章在第二行文章里可能包含空格。如果直接用cin读文章遇到空格就断了根本读不完整。这里必须用getline但要注意如果前面用cin读入过内容缓冲区里会留下一个换行符直接getline的话会读到空行。所以我选择了连续两次getline读完之后再统一处理。2.2 递归解决组合问题P1036的思考路径P1036“选数”这道题是经典的“从n个数里选k个数问和为质数的方案有多少种”。我第一次看到这道题的时候第一反应是用for循环套for循环但很快发现行不通因为k是变量k等于3时候写三层循环k等于5就因为需要写五层这明显不合理。递归就是解决这类“层数不确定”的枚举问题的标准方法。核心思想是定义一个函数dfs(start, picked, sum)表示“我已经从第start个位置开始考虑已经选了picked个数当前的和是sum”。每次调用时从start位置往后选一个数把选中状态传下去然后进入下一层递归。当picked等于k的时候说明已经选完k个数了就检查sum是不是质数是的话答案加一。这里有个很实用的经验递归参数能传值就不要用全局变量。把start、picked、sum作为参数往下传每一层递归都有自己独立的变量副本根本不需要写“回溯”代码也不用担心递归返回时状态被污染。我刚学DFS的时候经常在“要不要回溯”这个问题上纠结后来发现如果设计成传参累加很多情况下可以省掉显式回溯这一步代码会简洁很多出错概率也小很多。质数判断也不复杂从2开始到根号sum为止逐个试除就行。因为sum最大不超过n个数的总和用long long存储可以避免乘法溢出。这道题的数据范围很小n最大20k最大不超过n的一半最坏情况下的组合数也就是十几万暴力枚举完全来得及所以不用担心超时。3. 实操现场从读题到AC的完整记录3.1 热身环节P1001 和 P1427P1001“AB Problem”就不放完整代码了它存在的意义只是让我进入状态。一个读入两个整数、输出和的过程一分钟就能写完。但我要多说一句别觉得这种题没用很多新手在第一天连“ab”都要查语法第二天能闭着眼写出来本身就是进步。P1427“小鱼的数字游戏”稍微有点意思。它要求依次读入一串正整数以0为结束标志然后把除0以外的所有数逆序输出。我用了数组来存这个思路很简单但下标控制值得注意读入的时候从下标0开始存每读一个数下标加1遇到0就停止。输出的时候再逆着遍历一遍数组从最后一个有效下标一直走到0。#include bits/stdc.h using namespace std; int main() { int a[105]; int n 0; while (cin a[n] a[n] ! 0) { n; } for (int i n - 1; i 0; i--) { cout a[i] ; } cout endl; return 0; }这里我想提醒一下数组不是开得越大越好但太小了一定会出事。我一开始开的是a[100]这道题数据范围不大所以能过但养成习惯的话我建议数组开到题目上限再加上5到10的余量这样能避免一些边界情况下的数组越界。另外这个代码用的是“先读入后判断是不是0”的顺序所以0本身不会进入有效数组输出的时候自然不会输出它。3.2 P1308WA两次之后的正确写法P1308这道题我提交了三次才AC前两次都挂在同一个地方单词边界。我第一版代码直接用了字符串的find去找单词样例过了但提交后有两个测试点WA。我检查了一下才反应过来比如文章里出现了“to”这个词同时又出现了“today”这个词我搜索“to”的时候“today”里的“to”也会被误判成目标单词。显然这不符合题意因为题目要求的是完整的、独立的单词不能是某个长单词的一部分。第二版我设想用“前后字符是不是空格”来判断边界写起来很别扭处理开头和结尾的时候特别容易乱。后来想通了用前面提到的“首尾加空格”法一次搞定。最终代码如下#include bits/stdc.h using namespace std; string to_lower(string s) { for (char c : s) { if (c A c Z) { c 32; } } return s; } int main() { string word, text; getline(cin, word); getline(cin, text); word to_lower(word) ; text to_lower(text) ; int count 0; int first -1; size_t pos 0; while ((pos text.find(word, pos)) ! string::npos) { if (first -1) { first pos; } count; pos word.length() - 1; } if (first -1) { cout -1 endl; } else { cout count first endl; } return 0; }说几个细节。第一统一转小写之后再处理避免大写和小写字母干扰匹配。第二find函数找到了一个位置之后我把pos更新为“当前位置单词长度-1”这样下一次查找不会重复命中同一个位置但又能支持连续出现的情况。第三题目要求的“第一次出现位置”是从0开始计数的因为我在文章最前面加了一个空格所有原本的位置都会往后移一位正好和0起始的索引对应上了这一点我在本地测试的时候专门验证过。这道题给我的收获是字符串题目一定要先想清楚“边界条件”尤其是“单词边界”、“空行”、“首尾位置”。这些地方往往是隐藏的测试点样例根本覆盖不到。3.3 P1036第一次独立写出DFS到了晚上我开始挑战P1036“选数”。说实话递归的概念我之前看书看懂过但自己动手写还是第一次。前几分钟我盯着空白的编辑器发呆脑子里知道思路手就是不知道往哪里放。后来我强迫自己先写一个框架把函数需要的三个参数写出来start表示从哪个下标开始选picked表示已经选了几个数sum表示当前已选数字的和。然后我问自己什么时候结束递归答案很简单picked等于k的时候。什么时候继续往下选答案也很简单从start到n-1中再挑一个数。把这两个问题想明白代码就自然而然地出来了。#include bits/stdc.h using namespace std; int n, k; int a[25]; int ans 0; bool is_prime(long long x) { if (x 2) return false; for (long long i 2; i * i x; i) { if (x % i 0) return false; } return true; } void dfs(int start, int picked, long long sum) { if (picked k) { if (is_prime(sum)) { ans; } return; } for (int i start; i n; i) { dfs(i 1, picked 1, sum a[i]); } } int main() { cin n k; for (int i 0; i n; i) { cin a[i]; } dfs(0, 0, 0); cout ans endl; return 0; }我第一个版本有个小失误把scanf写成了“a[i] n”这种明显不对的语法被编译器提醒之后才发现是顺序颠倒了。这种低级错误真的很浪费时间所以我现在养成了一个习惯写输入输出的时候故意放慢速度一行一行看。等代码跑出正确答案的那个瞬间我其实没有特别激动反而有一种“原来递归就是这样”的恍然大悟。DFS并不是什么高深莫测的东西它就是“把当前能做的选择都做一遍做完之后再看看结果满不满足要求”的穷举思想。这道题里每个数字只有“被选”和“不被选”两个方向从start到n-1这个循环实际上就是枚举“下一个要选的数字是谁”一旦选够数量就判断答案整个流程清晰又自然。3.4 预留挑战题P1008 三连击P1008“三连击”的要求是用1到9这九个数字组成三个三位数使得它们满足1:2:3的比例输出所有可能的三位数组合。这道题并不需要高深的算法用暴力枚举就能做但麻烦在于要确保三个三位数合起来正好用完1到9这九个数字且不重复。我用了一个很常见的技巧把三个三位数分别拆成数字存到一个长度为10的标记数组里。如果某个数字出现两次以上就说明组合不合法。如果1到9每个数字都正好出现一次说明找到了一个答案。三重循环显然不现实我自己只写出了一种不太优雅的全排列思路测试后输出结果没问题但代码还可以优化。这道题我没有在当天彻底吃透所以决定把思路记录下来第三天再重新写一版更优雅的解法。学习编程本来就不是一蹴而就的事今天能完成P1308和P1036我已经很满意了。挑战题没做出来恰恰说明我找到了自己的薄弱点这是一个好的信号。4. 洛谷平台实用操作新手最容易忽略的细节4.1 切换编程语言和在线IDE很多新手第一次用洛谷提交的时候都会遇到这样一个问题明明本地运行得好好的提交上去就编译错误。常见原因之一就是编程语言选错了。在洛谷的题目页面右侧“提交答案”的窗口下方有一个语言下拉框里面默认选项可能不是你想用的语言。如果你用C17的语法写代码但语言却默认选成了C98那很多新特性就无法使用编译直接失败。我的建议是在个人设置里把默认语言改成C17这样每次提交就不用手动切换。洛谷的“在线IDE”功能也很好用位于页面顶部的练习菜单里可以在网页上直接写代码并测试不需要打开本地编译器。在线IDE和评测机的环境基本一致提交前先在在线IDE运行一遍能提前发现不少编译问题。另外如果你在某一道题里使用的语言和提交时选择的语言不一致也会报错这个细节千万别忽视。4.2 评测结果怎么看从AC到TLE第一次刷题的人可能不知道洛谷的评测结果到底是什么意思。我整理一份简表方便对照。评测结果英文全称含义ACAccepted答案正确通过WAWrong Answer答案错误TLETime Limit Exceeded超出时间限制程序跑得太慢MLEMemory Limit Exceeded超出内存限制RERuntime Error运行时错误可能数组越界或除零CECompile Error编译错误OLEOutput Limit Exceeded输出内容过多拿到WA不要上来就改代码先想想自己到底考虑过哪些边界情况。拿到TLE先看数据范围检查算法复杂度是不是过高。拿到RE优先检查数组下标是否越界尤其循环边界那种“差一个”的问题。AC之后也不用着急跑可以顺手看看这道题通过率是多少如果通过率很低而自己一次过了说明运气好但可能遗漏了某些测试点建议再去题解区看看别人的思路。4.3 账号登录、绑定与数据同步洛谷支持微信扫码登录但偶尔会遇到“微信登不了”的情况。排除服务器维护外最常见的原因是微信没有绑定手机号或者扫码后没有在手机上确认授权。如果扫码后一直转圈可以先退出重新登录或者改用账号密码登录在个人设置里补全手机号绑定通常就能解决。如果你还在vjudge这类跨站聚合OJ上刷题可以把洛谷账号绑定到vjudge的个人设置里这样跨平台的提交记录就能汇总在一个地方复盘时比较方便。绑定的时候需要先登录vjudge然后在账号绑定选项中找到洛谷并授权。如果绑定失败优先检查洛谷账号是否绑定了手机号以及是否关闭了第三方平台授权开关。4.4 讨论区、题解、搜索用户别浪费这些资源洛谷的价值不只是做题它的题解区质量很高。但看题解也有讲究不要一上来就看代码先看思路部分试着理解“为什么要这么做”再分两步走第一步把思路用自己的语言复述出来第二步在不看代码的情况下自己写一遍。如果直接复制粘贴别人的代码过两天遇到差不多的题照样不会写。洛谷还支持搜索用户输入别人的用户名就能看到TA的做题记录、通过题数和最近动态。我偶尔会去找同级别的人看看他们刷了哪些题会碰到很多自己没注意到的经典题。另外洛谷站内还藏着一些小游戏比如某些页面能触发“点灯”之类的小功能长时间刷题觉得脑子转不动了玩两局放松一下再继续换换思路比硬撑有效。5. 今日踩坑实录与常见问题排查5.1 编译错误这些低级错误真的很耽误时间今天遇到的最无语的编译错误就是P1036里把语句顺序写反了。具体的错误就不展示了主要原因是手比脑子快录入代码的时候没有逐字核对。还有一个常见的编译错误是变量名和系统自带函数或关键字冲突比如用next、time、rank做变量名在某些编译环境下会出问题。遇到编译错误时洛谷会显示“编译错误”的提示和详细日志点开日志就能看到出错的具体行号和原因一步步排查就行。另外如果你在本地用较老的编译器测试没开C11以上标准使用了auto等新语法本地编译都会报错更不用说提交了。洛谷的评测机一般支持较新的标准但还是要确认你选择的语言版本和代码使用的语法保持一致。5.2 运行错误和数组越界用好全局数组运行错误RE最常见的原因是数组越界。比如只开了一个长度为100的数组但循环里访问了下标105程序跑到一半就崩了。我的建议是不确定数据规模时数组尽量开在全局区直接定义为全局变量。全局数组默认初始化为0而且容量大适合大多数题目需求。如果一定要在main函数里开数组数据量大的时候可能引起栈溢出这也是MLE或RE的隐藏原因。另外递归深度过深也会导致栈溢出从而出现RE。解决方法一种是改用循环迭代实现另一种是增加剪枝条件来减少递归次数。P1036这道题的递归深度最多k层完全不用担心但遇到深度搜索迷宫等题目时就要警惕。5.3 超时与内存问题先看复杂度再优化IOTLE出现的原因是程序运行耗时超过了题目限制。遇到TLE时第一个要算的是时间复杂度。比如题目数据范围是n10^5如果你用了双重循环复杂度O(n^2)那就是10^10次运算超出评测机能承受的范围了必须要换思路。其次要优化输入输出C的cin和cout默认会和C语言的标准IO同步速度较慢在数据量大的时候可以在main函数开头加一行ios::sync_with_stdio(false)这样能提升不少速度。不想处理这些细节的话直接用scanf和printf也可以。MLE的问题则更简单粗暴通常是大数组开得太多或者递归栈太深。检查一下代码里有没有不必要的大数组能压缩尽量压缩。有时候开一个全局数组和多个局部大数组内存就会超。5.4 常见问题速查表现象可能原因处理建议样例能过但提交WA边界条件没处理比如字符串末尾、空行、大写字母构造边界数据进行测试提交显示CE语言版本选错或代码有语法错误检查编译日志确认语言版本出现RE数组越界、栈溢出、除零数组开全局并加大检查循环边界WA但找不到原因单词边界、数字分隔、重复匹配等问题给输入串首尾加空格再查找输出答案比预期多找到了重复解在递归或循环中检查参数更新逻辑提交成功但无法登录微信授权过期或未绑定手机退出重登确认手机绑定今天踩过的这些坑基本都是新手阶段绕不开的典型问题。我自己的体会是刷题过程中遇到WA和RE不丢人关键是看到报错之后能不能冷静下来按照“先看数据范围、再检查边界、最后复查代码”的顺序去排查。把每一次报错都当作一次练习比单纯刷过100道水题更有价值。明天我打算把P1008“三连击”补完然后继续深入一下DFS看看能不能独立写出第二道搜索题。如果你也处在这个阶段我的建议是给自己留一道即使做不出来也不会影响心情的挑战题第二天回头再看往往就会有新的思路。