刷算法题的人都知道最打击自信心的往往不是那些需要想半天的难题而是你一眼就觉得“这不就是基础题吗”的题目。我最近帮人复盘某校OJ基础4-6题才发现这三道题比想象中更能暴露问题样例能过一提交就WA本地跑得好好的一换输入就出乱子甚至有人因为多了一个空格整道题判错。这篇文章就用我练习时选的三道经典基础题——素数输出、最大公约数与最小公倍数、字符分类统计——把完整的读题、编码、调试、复盘过程走一遍。不管你在哪个平台刷题只要遇到类似编号的基础题这套思路都能直接用。1. 先把三道题翻译成“能直接写代码的话”很多新手拿到基础4-6题习惯性先打开编辑器照着样例猜逻辑。这不是完全不行但大概率会漏掉关键信息。我的习惯是先把题目要求转成三句非常朴素的话输入是什么、处理什么、输出什么。这三句话写清楚了后面写代码就只是填空。1.1 基础题翻车九成出在“题目读完就开始写”你可能会问基础题还能翻车太能了。常见情况是样例输入只有一组于是代码写死成单次处理或者样例输出没有显示行尾空格就以为空格无所谓再或者题目说“输入一行字符”你直接用scanf(%s)去读结果只要字符串里有空格后面全被截断。这些都不是算法问题而是对输入输出的理解不够精确。OJ的判题机是逐字符比较你的输出和标准输出多一个空格、少一个换行都可能被判定为Wrong Answer。所以拿到任何题目第一件事永远是把输入输出的边界条件抠清楚而不是着急写循环。1.2 我练的基础4输出2到n之间的所有素数题目描述大概是这样的输入一个正整数n2 ≤ n ≤ 1000输出从2到n之间的所有素数每个素数占一行。样例输入是10样例输出是2 3 5 7这道题考的是循环嵌套和素数判断。注意它要求“每个素数占一行”意味着输出末尾是换行符而不是空格或逗号。很多人喜欢把结果存到一个数组里再统一输出这个思路没问题但直接边判断边输出更省事也能避免数组越界的问题。1.3 我练的基础5求最大公约数和最小公倍数题目描述输入两个正整数a和b1 ≤ a, b ≤ 10^9输出它们的最大公约数gcd和最小公倍数lcm两个数之间用一个空格分隔。样例输入是“12 8”样例输出是“4 24”。这道题表面考数学实际考的是对辗转相除法的理解以及对整型溢出问题的敏感度。后面我会专门讲为什么最小公倍数不能直接写成a * b / gcd(a, b)这里先记住读入时一眼看到10^9心里就该警醒——这个量级已经逼近32位整数的上限了。1.4 我练的基础6统计一行字符串的字符类别题目描述输入一行字符可能包含空格长度不超过1000统计其中大写字母、小写字母、数字和其他字符的个数按顺序输出四个整数用空格分隔。样例输入是“Hello 123!”样例输出是“1 4 3 2”。我们来验算一下H是大写ello是4个小写123是3个数字空格和感叹号都算“其他字符”所以是2个。这个统计逻辑本身很简单难点在于“一行可能包含空格”。如果不知道这个前提你用scanf(%s)读入读到空格就停了样例可能都过不了。这道题是后续文本处理类题目的雏形非常值得认真对待。2. 素数题暴力判断其实完全够用但边界必须想清楚基础4的n最大只有1000所以完全没有必要套复杂筛法用二重循环暴力判断每个数是不是素数计算量也就是几千次除法对OJ来说几乎是零负担。2.1 最直接的二重循环写法#include stdio.h int main(void) { int n, i, j; int is_prime; scanf(%d, n); for (i 2; i n; i) { is_prime 1; for (j 2; j * j i; j) { if (i % j 0) { is_prime 0; break; } } if (is_prime) { printf(%d\n, i); } } return 0; }这段代码的逻辑是外层循环枚举2到n的每个数内层循环从2试到sqrt(i)一旦发现i能被某个数整除就说明它不是素数直接跳出内层循环。如果内层循环完整走完都没找到因子is_prime保持为1就输出。2.2 为什么用j * j i而不是j sqrt(i)这是我特别想强调的一个细节。用sqrt(i)再强转成int虽然也能得到正确结果但会有两个隐患第一sqrt需要引入math.h编译链接也要加-lm在某些在线评测环境里容易出幺蛾子第二浮点数存在精度误差如果i恰好是某个完全平方数sqrt(i)可能得到6.999999999强转成int就是6导致少检查一个因子。j * j i用的是纯整数运算既没有浮点转换也没有精度问题还顺带把内层循环次数压到平方根级别。这种写法的性能更好代码也更干净。2.3 如果n变大该怎么办基础4虽然只需要暴力但不妨碍我们多想一步如果哪天遇到n1000000二重循环就会超时。那时应该用埃氏筛核心逻辑是先假设所有数都是素数然后从2开始把每个素数的倍数全部标记为合数。代码片段大概是这样的int is_prime[1000001]; for (i 2; i * i n; i) { if (!is_prime[i]) { for (j i * i; j n; j i) { is_prime[j] 1; } } }这个写法的好处是时间复杂度接近O(n log log n)处理100万级别数据绰绰有余。但我不建议在基础题里一上来就写筛法因为题目范围明确写着1000暴力解法已经是标准答案没必要为了“秀操作”引入额外复杂度。2.4 提交时最容易错的输出格式素数题本身不难很多人却挂在格式上。比如把样例输出误解成“2 3 5 7”这种空格分隔代码写了printf(%d , i)一提交就WA。再比如最后一行多输出一个换行虽然很多判题系统不敏感但严格模式下也会判错。我的建议很简单题目说“每个数占一行”就老老实实写printf(%d\n, i)题目说“空格分隔”就在每个输出后跟一个空格或者用一个flag控制首元素前不加空格。格式这种东西不要靠猜直接看样例输出最稳妥。3. 最大公约数题三行核心代码背后的数学直觉基础5这道题难点不在代码而在你信不信辗转相除法。很多同学背了公式会写但一被问到“为什么这样循环就能得到gcd”就卡住。只背结论的人遇到变种题容易懵。3.1 辗转相除法为什么是对的辗转相除法的原理是对于两个整数a和bgcd(a, b) gcd(b, a % b)。也就是说用a除以b得到余数r然后原问题就变成求b和r的最大公约数。因为能同时整除a和b的数一定也能整除a % b所以这个转化不会改变公约数的集合。举个例子gcd(12, 8)12 % 8 4于是问题变成gcd(8, 4)8 % 4 0所以答案是4。整个过程中两个数越来越小直到余数为0最后一次的非零除数就是最大公约数。这个过程用循环实现就是int gcd(int a, int b) { while (b) { int temp b; b a % b; a temp; } return a; }递归写法更短int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }两种写法背后是同一个原理。我一般推荐先用迭代版因为递归版虽然简洁但初学者容易搞混调用顺序而且如果题目数据极端递归层数可能会增加虽然这里不会爆栈但养成用迭代的习惯更稳。3.2 最小公倍数必须“先除后乘”求最小公倍数的公式是lcm a * b / gcd(a, b)这没错但在编程里要反过来写lcm a / gcd(a, b) * b。为什么因为a * b可能会溢出。我记得这道题给的范围是a和b最大到10^9两个数相乘就是10^18这已经超过32位int的21亿上限了也超过很多OJ里int能表示的范围。即使你在代码里用了long long也仅仅是在本题安全换个更大范围的题目照样可能翻车。先除后乘的好处是先把结果缩小到不会溢出的范围再做乘法。3.3 完整代码顺便处理多组输入很多OJ的基础题不会只测一组数据而是会在后台放很多组测试用例按文件结束符EOF结束。如果代码只读一组就退出只能过样例后台数据可能全挂。所以读入部分建议写成while(scanf(%d%d, a, b) ! EOF)。#include stdio.h int gcd(int a, int b) { while (b) { int temp b; b a % b; a temp; } return a; } int main(void) { long long a, b; while (scanf(%lld%lld, a, b) ! EOF) { long long g gcd(a, b); long long l a / g * b; printf(%lld %lld\n, g, l); } return 0; }这里我把a和b都声明成long long然后用%lld读入。有的同学图省事用int在本题数据有10^9的情况下虽然gcd本身不会溢出但a * b会。直接用long long能从源头规避问题成本几乎为零。4. 字符统计题缓冲区残留和getchar的经典大坑基础6考察的是字符处理很多初学者会在这里卡很久。表面上是统计字符分类实际上暴露的是对输入缓冲区的不理解。4.1 为什么不能用scanf(%s)读入scanf(%s)遇到空白字符空格、制表符、换行就会停止读取。题目说“输入一行字符可能包含空格”如果用%s读输入“Hello 123!”实际读到的只有“Hello”后面全部丢掉统计结果必然错误。正确的思路是逐字符读入直到读到换行符为止。这里可以用getchar()#include stdio.h int main(void) { int upper 0, lower 0, digit 0, other 0; int ch; while ((ch getchar()) ! EOF ch ! \n) { if (ch A ch Z) { upper; } else if (ch a ch z) { lower; } else if (ch 0 ch 9) { digit; } else { other; } } printf(%d %d %d %d\n, upper, lower, digit, other); return 0; }4.2 为什么必须用int ch而不是char ch这是C语言里一个隐蔽的坑。getchar()的返回值类型是int因为除了字符ASCII码之外它还要能表示EOF而EOF通常是-1。如果你把返回值直接塞给char在部分平台上char是无符号类型-1会被截断成255导致ch ! EOF的判断永远不成立程序可能陷入死循环。更常见的表现是本地测试明明输出正确一提交就超时或WA。排查半天最后发现是char ch的问题。所以这类题统一用int ch接收getchar()的返回值养成习惯就不会踩这个坑。4.3 排查“样例过了但WA”的完整链路我之前帮A同学看这道题时他贴出代码后我先让他跑样例结果本地输出完全正确。但OJ上就是WA。后来我们一行行检查发现问题不在统计逻辑而是在他这次提交的代码里前面还有一个scanf(%d, n)的读入操作。执行完scanf后输入缓冲区里会残留一个换行符紧接着调用getchar()读到的第一内容就是这个残留的换行符导致后面的字符串统计直接从第二行开始数据全乱。这个问题在OJ的字符串类题目里特别常见。题目有时候会先输入一个整数再输入一行带空格的字符串如果你直接用scanf读整数然后gets读字符串必挂。解决办法有两种一是在scanf之后用一个循环把缓冲区的换行符清空二是改用fgets读整行再从字符串里逐个字符处理。我建议初学者多熟悉fgets因为它在处理“包含空格的整行输入”时更稳char line[1005]; fgets(line, sizeof(line), stdin);fgets会连换行符一起读进来统计时要记得判断line[i] \n时应略过不过因为你只统计字符串的字符类型换行符会被算进“其他字符”。如果题目明确说统计到回车为止最好在读入后手动去掉末尾换行或者循环时排除它。4.4 字符判断用字符常量不要用ASCII码数字ch 65 ch 90这种写法在功能上没问题但可读性很差。写成ch A ch Z一眼就能看出这是在判断大写字母还能避免记错ASCII码。同理数字判断写成ch 0 ch 9。这类基础题虽然短小但代码风格会影响你调试的效率干净清晰的判断条件能帮你减少很多不必要的分心。5. 把基础题当“体检报告”AC之后值得做的三件事三道题都AC后别急着关页面去刷下一批题。基础题最大的意义不是那几分钟的快感而是像体检报告一样告诉你哪些基本功还需要加固。我每次重做这类题都会额外做三件事。5.1 整理一份“防WA检查清单”这比多刷十道题还管用。下面是我基于这三道题总结出来的自查表题目最容易翻车点我的检查方法基础4 素数输出输出分隔符和内循环边界每行一个换行用j * j i判断基础5 gcd/lcm乘法溢出、多组输入用long long先除后乘while(scanf...!EOF)基础6 字符统计scanf残留换行符、getchar的EOF用int ch接收必要时fgets读整行这张表在后续做更复杂的题目时也可以复用。很多WA根本不是算法想错了而是输入输出类型、溢出或缓冲区的问题一份清单能让你快速锁定方向。5.2 把函数封装成自己的“代码零件”基础5里那种gcd函数值得单独保存起来。后面刷题你会不停用到最大公约数分数化简、同余运算、扩展欧几里得甚至一些字符串题里也会间接用到。用一个文件专门收集这种短小而通用的函数慢慢就会变成你自己的代码库写题时直接复制过来能省下大量调试时间。5.3 往三个方向做思维延伸三道基础题的背后都有对应的进阶方向素数题往上走是埃氏筛、线性筛、区间筛再到质因数分解gcd/lcm往上走是欧几里得算法的扩展比如扩展欧几里得解不定方程字符统计往上走是词频统计、字符串哈希、文本处理。我不是让你现在就去学这些而是在心里留个索引之后碰到相关题目时知道它们是从这些基础点长出来的。最后再分享一个小习惯每次提交通过后把样例输入改几个边界值再跑一遍比如n2、n1000、a1、b10^9、字符串全是空格等。基础题最大的陷阱不藏在算法里而是藏在边界和格式里。把这一步做成了本能后面刷复杂题时你会省掉大量因为低级错误带来的返工。