连着刷了三个晚上东华OJ的基础练习终于推进到了第7到第9题。说实话这三道题单独拎出来都不算难但它们卡我的时间和心态比后面那些看起来更复杂的题还要狠。第7题让我第一次在OJ上感受到“Time Limit Exceeded”的分量第8题让我对着“Wrong Answer”翻来覆去折腾了半小时第9题则逼着我把辗转相除法从暴力到优化完整推导了一遍。今天抽空把这三道题完整复盘一遍顺带把我在这个过程中踩过的坑、总结的排查清单整理出来给同样在东华OJ或者类似在线评测系统上刷题的朋友做个参考。如果你也是刚接触这类系统这套题里的问题你大概率也会遇到。1. 第7题复盘多组输入与求和公式别让循环拖垮你1.1 我遇到的题面每行一个n读到EOF我刷到的第7题是这样的计算1到n之间所有奇数的和n为正整数。输入包含多组测试数据每行一个整数n直到文件结束EOF为止。对每一组输入输出对应的和每个输出占一行。先说明一下不同时期东华OJ的题号分配可能会调整所以如果你打开题目发现第7题不是这题也别慌多组输入加EOF结束这个模式在入门阶段一定会碰到把这题吃透后面处理AB、字符统计这类题目的输入骨架可以直接复用。为什么单独拿这道题出来说因为它的题面很短看起来就是个循环累加的小练习可恰恰是这种“看起来很简单”的题最容易让人翻车。我第一眼的想法是从1开始步长2累加所有奇数输出结果收工。这个思路本身没错问题出在效率上。1.2 第一版翻车循环累加在10^9面前毫无还手之力第一版代码很自然地写成下面这样逻辑不复杂就是对每个n都从1循环到n#include stdio.h int main() { int n; while (scanf(%d, n) ! EOF) { int sum 0; for (int i 1; i n; i 2) { sum i; } printf(%d\n, sum); } return 0; }本地测了几组小数据1359、135716看起来都对提交却直接TLE。我当时的第一反应是OJ出问题了然后才开始怀疑是不是输入循环写错了。排查半天问题出在n的大小上题面没有明确写n的上限后台测试数据里却出现了10^9这种量级。for循环走5亿次哪怕每一次只是一次加法在1秒的时间限制下也扛不住。这是入门阶段最容易踩的坑只考虑功能正确不考虑时间开销。OJ不是本地编译器它有严格的时间限制测试数据也不是只有你看到的样例那几组。这里我顺带说一个很多人忽略的点本地通过了不代表OJ上一定能过。本地编译器通常有优化测试数据也少时间感受不明显OJ后台的测试用例是批量跑的单点时间限制通常只有1秒或2秒。判断自己的算法会不会超时最简单的办法是看循环次数不要超过10^8最好控制在10^7以内。如果循环次数到10^9基本就要找数学规律或者换算法了。第7题用循环累加就是活生生的例子换成O(1)的公式后无论n多大计算量都只有常数这才是可以在OJ上稳定提交的写法。1.3 等差数列才是正解顺带解决scanf返回值问题1到n的所有奇数本质上是首项为1、公差为2的等差数列。求和不需要真的把每一项加一遍直接算项数和总和就行。奇数项的个数k(n1)/2这里用的是整数除法所以不需要分n是奇数还是偶数。n5的时候奇数有1、3、5三项(51)/23n4的时候奇数有1、3两项(41)/22。项数确定后连续奇数项的和恰好等于k的平方因为13...(2k-1)k^2。这个结论可以靠数学归纳法验证也可以自己多举几组例子感受一下。于是代码变成#include stdio.h int main() { long long n; while (scanf(%lld, n) ! EOF) { long long k (n 1) / 2; long long ans k * k; printf(%lld\n, ans); } return 0; }这里有几个隐藏考点。第一scanf的返回值它返回成功匹配并赋值的参数个数读到文件末尾会返回EOF。while(scanf(...) ! EOF)是处理多组输入的标准写法如果你用while(1)再手动break逻辑稍不留神就会死循环。第二类型选择n如果达到10^9k就是510^8kk是2.5*10^17已经远超32位int的范围必须用long long。第三输出格式long long对应%lld不要写成%d。这几个点单独看都很小但任何一个都会让你收获一个鲜红的WA或者TLE。2. 第8题复盘成绩等级判断等号与边界是重灾区2.1 题面与初版写法if-else堆出来的答案第8题是一道典型的成绩转换题输入一个0到100的整数成绩输出对应的等级。90到100是A80到89是B70到79是C60到69是D60以下是E。输出一个字符加一个换行。题目给的样例是连续好几个成绩我用多组输入来处理OJ会把我的输出和标准输出逐行比对所以多处理几行也没问题。我的第一版写法相信很多初学者都熟悉#include stdio.h int main() { int score; while (scanf(%d, score) ! EOF) { if (score 90 score 100) printf(A\n); else if (score 80 score 89) printf(B\n); else if (score 70 score 79) printf(C\n); else if (score 60 score 69) printf(D\n); else printf(E\n); } return 0; }逻辑上看起来滴水不漏每个区间都明确写了上下界但提交后依然WA。原因说出来有点丢人我当时觉得“90到100”应该写作score 90 score 100理由是自己想当然地认为100分应该单独处理或者脑子里潜意识觉得100是特殊情况。结果就是100分没有进入第一个分支一路掉进了else输出E。2.2 翻车点抛开经验逐字读题和边界测试这个错误表面上是粗心深一层的原因是没做边界测试。成绩转换这种区间题最容易翻车的点是每一档的端点0、59、60、69、70、79、80、89、90、99、100。你至少要跑一遍这组数据确认输出分别对应E、E、D、D、C、C、B、B、A、A、A然后再提交。我第一版代码如果测了100马上就会发现它被错误地分到了E档。大部分人写if-else的时候总觉得条件很清楚于是随便测一两个中间值就提交结果WA了之后才开始怀疑人生。还有一个细节值得单独说如果成绩不在0到100之间代码要怎么处理我见过有的同学加了一行if(score 0 || score 100) return 0;也有的同学直接忽略。其实正确做法是看题面。如果题面明确说了输入保证在0到100不写防御完全没问题如果题面没说写一下也无妨。关键是不要因为防御逻辑改变正常输出的格式尤其不要输出什么“Invalid”之类的提示除非题面要求。在线评测系统只认标准输出你多打一行字轻则PE重则WA。2.3 用switch(score/10)和查表法重构这类区间映射题用switch(score/10)比一长串if-else更容易检查。分数除以10之后90到99落在9100落在1080到89落在870到79落在760到69落在60到59落在0到5。于是可以这样写switch (score / 10) { case 10: case 9: printf(A\n); break; case 8: printf(B\n); break; case 7: printf(C\n); break; case 6: printf(D\n); break; default: printf(E\n); break; }注意case 10绝对不能漏因为100除以10等于10。如果你只写case 9满分就会落到default输出E和if-else版的错误一模一样。这个坑在switch写法里显得尤其阴险因为代码看起来好像很规整实际上边界还是没守住。如果你愿意再进一步还可以用查表法定义一个字符串数组存放等级然后用score/10做下标。char *level[] {E,E,E,E,E,E,D,C,B,A,A}下标0到10分别对应0到100分输出level[score/10]即可。这种写法把区间映射集中在一个数据结构里结构最清晰漏写的概率也最低。第一次看可能觉得绕我的建议是先熟练掌握switch版本再慢慢体会查表法的好处。还有一个比较隐蔽的细节else if和多个独立if是两回事。有的同学会把每个区间写成分开的if四个if依次判断这样的代码在逻辑上可能会让同一个分数进入两个分支比如score95时第一个if输出A第四个if如果写成if(score60)又会输出E。使用else if可以保证只执行第一个成立的分支但前提是条件顺序要正确。把最严格的区间写前面把宽松的区间写后面。而switch和查表法本质上已经把区间切割清楚了不太容易出现这种双重命中问题这也是我推荐改写成switch的另一个原因。3. 第9题复盘最大公约数与最小公倍数从暴力到辗转相除3.1 题面里藏着两个输出值先别急着写代码第9题的题面非常简洁输入两个正整数a和b输出它们的最大公约数和最小公倍数两个数之间用空格隔开每组结果占一行。输入也是多组读到EOF结束。题面没有把a和b的上限写得特别清楚我当时默认它们可能接近int上限这个直觉在后面救了我。这个题容易让人吃亏的点有两个。第一是输出两个值不是只求一个最大公约数就完事最小公倍数也要算。第二是最小公倍数的计算有个容易忽略的数学细节。很多人算法课上学过gcd考试也写过但到了OJ上同样的思路却会因为数据类型和计算顺序翻车。所以这个题不能只满足于“能算”还要想清楚怎样才算写得稳。3.2 暴力枚举为什么炸数据一大就原形毕露暴力求gcd的思路是从min(a,b)开始逐步往下找找到第一个能同时整除a和b的数就停下来。比如a12、b18从12开始往下试12不行、11不行……一直到6才成功。数据小的时候这个算法完全没问题甚至比辗转相除法更直观。但一旦a和b都是很大的质数比如999999937和999999929从较小的数开始往下找要迭代好几亿次OJ不可能让你过。暴力代码不是没有价值我建议把它留在本地当作对拍器生成一些随机小数据拿暴力结果和优化算法的结果对比如果完全一致再手动检查一下大数边界代码基本就没问题了。暴力版本的写法也简单long long gcd_bruteforce(long long a, long long b) { long long i; for (i (a b ? a : b); i 1; i--) { if (a % i 0 b % i 0) return i; } return 1; }这种代码最大的问题是当a和b互质时循环会一直走到i1才停复杂度O(min(a,b))完全顶不住大数据。3.3 辗转相除法的推导与递归实现辗转相除法的核心事实是gcd(a,b)gcd(b,a%b)。这个等式可以这样理解如果某个整数d同时整除a和b那么d一定也整除a减去b的任意整数倍也就是a除以b的余数。反过来如果d同时整除b和a%b那么d也一定整除a。所以a和b的公约数集合和b与a%b的公约数集合完全相等最大公约数自然相等。余数会越来越小最终变成0此时另一个非零的数就是两者的最大公约数。写成递归就三行long long gcd(long long a, long long b) { return b 0 ? a : gcd(b, a % b); }有人会担心a小于b的情况。比如a12、b18第一次调用gcd(12,18)因为12%1812调用就变成gcd(18,12)相当于自动交换了一次。所以不需要提前判断a和b的大小递归会帮你处理。时间上欧几里得算法的迭代次数是O(log min(a,b))哪怕a和b都接近10^18也只需要几十次迭代性能和暴力完全是两个数量级。递归版本看起来很简洁但有的同学担心递归层数会不会太深。其实gcd的递归深度在int范围内就是个位数到几十位完全不会爆栈。如果你实在想避免递归也可以改成迭代版本long long gcd(long long a, long long b) { while (b) { long long t a % b; a b; b t; } return a; }这个版本的时间复杂度和递归版本完全一样无非是把系统栈换成了循环。刻意记哪一种其实都行关键是理解“余数为0时停止”这个终止条件。我个人更推荐把迭代版本记熟因为写起来不用考虑栈也方便在需要的情况下改成计算过程中的中间结果。3.4 最小公倍数的计算顺序先除后乘防溢出最大公约数算出来后最小公倍数的标准公式是lcm a * b / gcd。但这个公式直接用在代码里有一个隐患如果a和b都接近int上限a*b这一项先算的时候会溢出32位的int结果变成负数后面再赋值给long long也来不及了。在C语言里乘法表达式的类型取决于操作数类型int乘int得到的是int溢出行为在OJ环境下通常就是截断成负数这不是你换成long long类型的结果变量就能解决的。更稳的写法是先除后乘long long g gcd(a, b); long long l a / g * b;因为a/g一定整除真实结果ab/g一定小于等于ab所以这个顺序能避免中间的溢出现象。完整的提交代码就是这样#include stdio.h long long gcd(long long a, long long b) { return b 0 ? a : gcd(b, a % b); } int main() { 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; }再强调一次输出顺序题目要的是“最大公约数 最小公倍数”我见过有同学一激动把顺序写反了样例却刚好两个数字一样导致提交后才暴露。所以真的务必先看样例。样例里第一个输出是gcd第二个是lcm别想当然。4. 三题连刷后我总结的OJ一遍过清单4.1 读题阶段的三件事结束条件、数据范围、输出格式7到9这三道题刷下来的最大收获不是背住了某个公式而是养成了一套读题的肌肉记忆。每次拿到题我先默念三件事输入怎么结束、数据范围多大、输出格式是什么。这三个问题搞不清写再漂亮的代码也白搭。输入结束方式常见的有三种读到EOF用while(scanf(...)!EOF)先给一个组数n然后用for循环读n次读到特殊值结束比如0 0这种要在循环体里判断。三种情况对应三种骨架混着用就会出问题。数据范围则决定类型和算法数字一大第一反应是long long运算量一大第一反应是找数学公式或者更快的算法。输出格式也要逐字看每组一行还是组间空行末尾要不要换行左右有没有空格样例是最权威的参考没有把握的格式细节跟着样例抄都可以。4.2 提交前自测边界值、多组输入、换行符我之前经常写完代码直接提交然后盯着OJ的状态栏等结果。第8题那次WA之后我开始强迫自己在提交前做一轮自测。自测的具体做法就是边界值加多组输入。第7题至少测n1、n2、n1000000000确认没有输出负数没有超时结果数量级也符合预期。第8题把0、59、60、69、70、79、80、89、90、99、100全部跑一遍确认等级逐个对得上。第9题测a1,b1测a1,b999999937测两个相等的大数再测两个互质的大数。如果条件允许再写一个暴力的gcd函数随机生成十几组小数据做对拍暴力结果和辗转相除法结果一致就基本可以放心提交了。还有一个细节是换行符。OJ一般允许最后一个输出后面没有换行但如果你在循环外多写了一个空行或者每行结尾多了空格就会得到Presentation Error。输出内容要严格按照要求不要自己加装饰。提交之后你会看到各种评测状态最常接触的几种AcceptedAC就是通过Wrong AnswerWA是答案错误Time Limit ExceededTLE是超时Memory Limit ExceededMLE是内存超限Presentation ErrorPE是输出格式错误Runtime ErrorRE是运行时错误通常是数组越界、除零或者栈溢出Compile ErrorCE是编译错误。看到PE别慌说明你的输出内容基本对了只是空白符格式不符合要求检查一下每行结尾是不是多了空格、行数对不对。看到RE先找除零和数组越界这类问题在入门题里往往是最容易忽略的。4.3 从WA到AC的调试路径万一提交之后还是Wrong Answer不要慌按顺序做三件事。第一步拿题目样例跑一遍如果程序输出和样例不一致说明主干逻辑有问题直接看代码。第二步如果样例能过那就构造特殊输入最大值、最小值、边界值、相等值、0或者1。第8题就是典型的例子中间值测不出问题100分一测就露馅。第三步如果边界值也过了考虑类型溢出、输出格式、数组边界比如%lld写成了%d或者下标越界。这一类问题在C语言OJ题里出现频率极高。如果还查不出来用对拍。写一个你认为一定正确的暴力解法再写一个数据生成器生成随机小数据把两个程序的输出重定向到文件里用diff逐行比对。这个方法能帮你在大样本下发现在哪里。我自己刷题的经验是对拍半小时往往比盲目提交十次更有用。复盘这三道题我最深的体会是OJ考验的往往不是你会不会某个高深算法而是你能不能把一个简单问题考虑得足够完整。多组输入、边界值、数据范围、输出格式这四个词看着像废话却是绝大多数WA和TLE的真正来源。第7题教会我用公式替代循环第8题教会我永远尊重端点第9题教会我在计算顺序上提前避开溢出。希望这篇复盘能让你少走一点我走过的弯路。
连着刷了三个晚上东华OJ的基础练习终于推进到了第7到第9题。说实话这三道题单独拎出来都不算难但它们卡我的时间和心态比后面那些看起来更复杂的题还要狠。第7题让我第一次在OJ上感受到“Time Limit Exceeded”的分量第8题让我对着“Wrong Answer”翻来覆去折腾了半小时第9题则逼着我把辗转相除法从暴力到优化完整推导了一遍。今天抽空把这三道题完整复盘一遍顺带把我在这个过程中踩过的坑、总结的排查清单整理出来给同样在东华OJ或者类似在线评测系统上刷题的朋友做个参考。如果你也是刚接触这类系统这套题里的问题你大概率也会遇到。1. 第7题复盘多组输入与求和公式别让循环拖垮你1.1 我遇到的题面每行一个n读到EOF我刷到的第7题是这样的计算1到n之间所有奇数的和n为正整数。输入包含多组测试数据每行一个整数n直到文件结束EOF为止。对每一组输入输出对应的和每个输出占一行。先说明一下不同时期东华OJ的题号分配可能会调整所以如果你打开题目发现第7题不是这题也别慌多组输入加EOF结束这个模式在入门阶段一定会碰到把这题吃透后面处理AB、字符统计这类题目的输入骨架可以直接复用。为什么单独拿这道题出来说因为它的题面很短看起来就是个循环累加的小练习可恰恰是这种“看起来很简单”的题最容易让人翻车。我第一眼的想法是从1开始步长2累加所有奇数输出结果收工。这个思路本身没错问题出在效率上。1.2 第一版翻车循环累加在10^9面前毫无还手之力第一版代码很自然地写成下面这样逻辑不复杂就是对每个n都从1循环到n#include stdio.h int main() { int n; while (scanf(%d, n) ! EOF) { int sum 0; for (int i 1; i n; i 2) { sum i; } printf(%d\n, sum); } return 0; }本地测了几组小数据1359、135716看起来都对提交却直接TLE。我当时的第一反应是OJ出问题了然后才开始怀疑是不是输入循环写错了。排查半天问题出在n的大小上题面没有明确写n的上限后台测试数据里却出现了10^9这种量级。for循环走5亿次哪怕每一次只是一次加法在1秒的时间限制下也扛不住。这是入门阶段最容易踩的坑只考虑功能正确不考虑时间开销。OJ不是本地编译器它有严格的时间限制测试数据也不是只有你看到的样例那几组。这里我顺带说一个很多人忽略的点本地通过了不代表OJ上一定能过。本地编译器通常有优化测试数据也少时间感受不明显OJ后台的测试用例是批量跑的单点时间限制通常只有1秒或2秒。判断自己的算法会不会超时最简单的办法是看循环次数不要超过10^8最好控制在10^7以内。如果循环次数到10^9基本就要找数学规律或者换算法了。第7题用循环累加就是活生生的例子换成O(1)的公式后无论n多大计算量都只有常数这才是可以在OJ上稳定提交的写法。1.3 等差数列才是正解顺带解决scanf返回值问题1到n的所有奇数本质上是首项为1、公差为2的等差数列。求和不需要真的把每一项加一遍直接算项数和总和就行。奇数项的个数k(n1)/2这里用的是整数除法所以不需要分n是奇数还是偶数。n5的时候奇数有1、3、5三项(51)/23n4的时候奇数有1、3两项(41)/22。项数确定后连续奇数项的和恰好等于k的平方因为13...(2k-1)k^2。这个结论可以靠数学归纳法验证也可以自己多举几组例子感受一下。于是代码变成#include stdio.h int main() { long long n; while (scanf(%lld, n) ! EOF) { long long k (n 1) / 2; long long ans k * k; printf(%lld\n, ans); } return 0; }这里有几个隐藏考点。第一scanf的返回值它返回成功匹配并赋值的参数个数读到文件末尾会返回EOF。while(scanf(...) ! EOF)是处理多组输入的标准写法如果你用while(1)再手动break逻辑稍不留神就会死循环。第二类型选择n如果达到10^9k就是510^8kk是2.5*10^17已经远超32位int的范围必须用long long。第三输出格式long long对应%lld不要写成%d。这几个点单独看都很小但任何一个都会让你收获一个鲜红的WA或者TLE。2. 第8题复盘成绩等级判断等号与边界是重灾区2.1 题面与初版写法if-else堆出来的答案第8题是一道典型的成绩转换题输入一个0到100的整数成绩输出对应的等级。90到100是A80到89是B70到79是C60到69是D60以下是E。输出一个字符加一个换行。题目给的样例是连续好几个成绩我用多组输入来处理OJ会把我的输出和标准输出逐行比对所以多处理几行也没问题。我的第一版写法相信很多初学者都熟悉#include stdio.h int main() { int score; while (scanf(%d, score) ! EOF) { if (score 90 score 100) printf(A\n); else if (score 80 score 89) printf(B\n); else if (score 70 score 79) printf(C\n); else if (score 60 score 69) printf(D\n); else printf(E\n); } return 0; }逻辑上看起来滴水不漏每个区间都明确写了上下界但提交后依然WA。原因说出来有点丢人我当时觉得“90到100”应该写作score 90 score 100理由是自己想当然地认为100分应该单独处理或者脑子里潜意识觉得100是特殊情况。结果就是100分没有进入第一个分支一路掉进了else输出E。2.2 翻车点抛开经验逐字读题和边界测试这个错误表面上是粗心深一层的原因是没做边界测试。成绩转换这种区间题最容易翻车的点是每一档的端点0、59、60、69、70、79、80、89、90、99、100。你至少要跑一遍这组数据确认输出分别对应E、E、D、D、C、C、B、B、A、A、A然后再提交。我第一版代码如果测了100马上就会发现它被错误地分到了E档。大部分人写if-else的时候总觉得条件很清楚于是随便测一两个中间值就提交结果WA了之后才开始怀疑人生。还有一个细节值得单独说如果成绩不在0到100之间代码要怎么处理我见过有的同学加了一行if(score 0 || score 100) return 0;也有的同学直接忽略。其实正确做法是看题面。如果题面明确说了输入保证在0到100不写防御完全没问题如果题面没说写一下也无妨。关键是不要因为防御逻辑改变正常输出的格式尤其不要输出什么“Invalid”之类的提示除非题面要求。在线评测系统只认标准输出你多打一行字轻则PE重则WA。2.3 用switch(score/10)和查表法重构这类区间映射题用switch(score/10)比一长串if-else更容易检查。分数除以10之后90到99落在9100落在1080到89落在870到79落在760到69落在60到59落在0到5。于是可以这样写switch (score / 10) { case 10: case 9: printf(A\n); break; case 8: printf(B\n); break; case 7: printf(C\n); break; case 6: printf(D\n); break; default: printf(E\n); break; }注意case 10绝对不能漏因为100除以10等于10。如果你只写case 9满分就会落到default输出E和if-else版的错误一模一样。这个坑在switch写法里显得尤其阴险因为代码看起来好像很规整实际上边界还是没守住。如果你愿意再进一步还可以用查表法定义一个字符串数组存放等级然后用score/10做下标。char *level[] {E,E,E,E,E,E,D,C,B,A,A}下标0到10分别对应0到100分输出level[score/10]即可。这种写法把区间映射集中在一个数据结构里结构最清晰漏写的概率也最低。第一次看可能觉得绕我的建议是先熟练掌握switch版本再慢慢体会查表法的好处。还有一个比较隐蔽的细节else if和多个独立if是两回事。有的同学会把每个区间写成分开的if四个if依次判断这样的代码在逻辑上可能会让同一个分数进入两个分支比如score95时第一个if输出A第四个if如果写成if(score60)又会输出E。使用else if可以保证只执行第一个成立的分支但前提是条件顺序要正确。把最严格的区间写前面把宽松的区间写后面。而switch和查表法本质上已经把区间切割清楚了不太容易出现这种双重命中问题这也是我推荐改写成switch的另一个原因。3. 第9题复盘最大公约数与最小公倍数从暴力到辗转相除3.1 题面里藏着两个输出值先别急着写代码第9题的题面非常简洁输入两个正整数a和b输出它们的最大公约数和最小公倍数两个数之间用空格隔开每组结果占一行。输入也是多组读到EOF结束。题面没有把a和b的上限写得特别清楚我当时默认它们可能接近int上限这个直觉在后面救了我。这个题容易让人吃亏的点有两个。第一是输出两个值不是只求一个最大公约数就完事最小公倍数也要算。第二是最小公倍数的计算有个容易忽略的数学细节。很多人算法课上学过gcd考试也写过但到了OJ上同样的思路却会因为数据类型和计算顺序翻车。所以这个题不能只满足于“能算”还要想清楚怎样才算写得稳。3.2 暴力枚举为什么炸数据一大就原形毕露暴力求gcd的思路是从min(a,b)开始逐步往下找找到第一个能同时整除a和b的数就停下来。比如a12、b18从12开始往下试12不行、11不行……一直到6才成功。数据小的时候这个算法完全没问题甚至比辗转相除法更直观。但一旦a和b都是很大的质数比如999999937和999999929从较小的数开始往下找要迭代好几亿次OJ不可能让你过。暴力代码不是没有价值我建议把它留在本地当作对拍器生成一些随机小数据拿暴力结果和优化算法的结果对比如果完全一致再手动检查一下大数边界代码基本就没问题了。暴力版本的写法也简单long long gcd_bruteforce(long long a, long long b) { long long i; for (i (a b ? a : b); i 1; i--) { if (a % i 0 b % i 0) return i; } return 1; }这种代码最大的问题是当a和b互质时循环会一直走到i1才停复杂度O(min(a,b))完全顶不住大数据。3.3 辗转相除法的推导与递归实现辗转相除法的核心事实是gcd(a,b)gcd(b,a%b)。这个等式可以这样理解如果某个整数d同时整除a和b那么d一定也整除a减去b的任意整数倍也就是a除以b的余数。反过来如果d同时整除b和a%b那么d也一定整除a。所以a和b的公约数集合和b与a%b的公约数集合完全相等最大公约数自然相等。余数会越来越小最终变成0此时另一个非零的数就是两者的最大公约数。写成递归就三行long long gcd(long long a, long long b) { return b 0 ? a : gcd(b, a % b); }有人会担心a小于b的情况。比如a12、b18第一次调用gcd(12,18)因为12%1812调用就变成gcd(18,12)相当于自动交换了一次。所以不需要提前判断a和b的大小递归会帮你处理。时间上欧几里得算法的迭代次数是O(log min(a,b))哪怕a和b都接近10^18也只需要几十次迭代性能和暴力完全是两个数量级。递归版本看起来很简洁但有的同学担心递归层数会不会太深。其实gcd的递归深度在int范围内就是个位数到几十位完全不会爆栈。如果你实在想避免递归也可以改成迭代版本long long gcd(long long a, long long b) { while (b) { long long t a % b; a b; b t; } return a; }这个版本的时间复杂度和递归版本完全一样无非是把系统栈换成了循环。刻意记哪一种其实都行关键是理解“余数为0时停止”这个终止条件。我个人更推荐把迭代版本记熟因为写起来不用考虑栈也方便在需要的情况下改成计算过程中的中间结果。3.4 最小公倍数的计算顺序先除后乘防溢出最大公约数算出来后最小公倍数的标准公式是lcm a * b / gcd。但这个公式直接用在代码里有一个隐患如果a和b都接近int上限a*b这一项先算的时候会溢出32位的int结果变成负数后面再赋值给long long也来不及了。在C语言里乘法表达式的类型取决于操作数类型int乘int得到的是int溢出行为在OJ环境下通常就是截断成负数这不是你换成long long类型的结果变量就能解决的。更稳的写法是先除后乘long long g gcd(a, b); long long l a / g * b;因为a/g一定整除真实结果ab/g一定小于等于ab所以这个顺序能避免中间的溢出现象。完整的提交代码就是这样#include stdio.h long long gcd(long long a, long long b) { return b 0 ? a : gcd(b, a % b); } int main() { 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; }再强调一次输出顺序题目要的是“最大公约数 最小公倍数”我见过有同学一激动把顺序写反了样例却刚好两个数字一样导致提交后才暴露。所以真的务必先看样例。样例里第一个输出是gcd第二个是lcm别想当然。4. 三题连刷后我总结的OJ一遍过清单4.1 读题阶段的三件事结束条件、数据范围、输出格式7到9这三道题刷下来的最大收获不是背住了某个公式而是养成了一套读题的肌肉记忆。每次拿到题我先默念三件事输入怎么结束、数据范围多大、输出格式是什么。这三个问题搞不清写再漂亮的代码也白搭。输入结束方式常见的有三种读到EOF用while(scanf(...)!EOF)先给一个组数n然后用for循环读n次读到特殊值结束比如0 0这种要在循环体里判断。三种情况对应三种骨架混着用就会出问题。数据范围则决定类型和算法数字一大第一反应是long long运算量一大第一反应是找数学公式或者更快的算法。输出格式也要逐字看每组一行还是组间空行末尾要不要换行左右有没有空格样例是最权威的参考没有把握的格式细节跟着样例抄都可以。4.2 提交前自测边界值、多组输入、换行符我之前经常写完代码直接提交然后盯着OJ的状态栏等结果。第8题那次WA之后我开始强迫自己在提交前做一轮自测。自测的具体做法就是边界值加多组输入。第7题至少测n1、n2、n1000000000确认没有输出负数没有超时结果数量级也符合预期。第8题把0、59、60、69、70、79、80、89、90、99、100全部跑一遍确认等级逐个对得上。第9题测a1,b1测a1,b999999937测两个相等的大数再测两个互质的大数。如果条件允许再写一个暴力的gcd函数随机生成十几组小数据做对拍暴力结果和辗转相除法结果一致就基本可以放心提交了。还有一个细节是换行符。OJ一般允许最后一个输出后面没有换行但如果你在循环外多写了一个空行或者每行结尾多了空格就会得到Presentation Error。输出内容要严格按照要求不要自己加装饰。提交之后你会看到各种评测状态最常接触的几种AcceptedAC就是通过Wrong AnswerWA是答案错误Time Limit ExceededTLE是超时Memory Limit ExceededMLE是内存超限Presentation ErrorPE是输出格式错误Runtime ErrorRE是运行时错误通常是数组越界、除零或者栈溢出Compile ErrorCE是编译错误。看到PE别慌说明你的输出内容基本对了只是空白符格式不符合要求检查一下每行结尾是不是多了空格、行数对不对。看到RE先找除零和数组越界这类问题在入门题里往往是最容易忽略的。4.3 从WA到AC的调试路径万一提交之后还是Wrong Answer不要慌按顺序做三件事。第一步拿题目样例跑一遍如果程序输出和样例不一致说明主干逻辑有问题直接看代码。第二步如果样例能过那就构造特殊输入最大值、最小值、边界值、相等值、0或者1。第8题就是典型的例子中间值测不出问题100分一测就露馅。第三步如果边界值也过了考虑类型溢出、输出格式、数组边界比如%lld写成了%d或者下标越界。这一类问题在C语言OJ题里出现频率极高。如果还查不出来用对拍。写一个你认为一定正确的暴力解法再写一个数据生成器生成随机小数据把两个程序的输出重定向到文件里用diff逐行比对。这个方法能帮你在大样本下发现在哪里。我自己刷题的经验是对拍半小时往往比盲目提交十次更有用。复盘这三道题我最深的体会是OJ考验的往往不是你会不会某个高深算法而是你能不能把一个简单问题考虑得足够完整。多组输入、边界值、数据范围、输出格式这四个词看着像废话却是绝大多数WA和TLE的真正来源。第7题教会我用公式替代循环第8题教会我永远尊重端点第9题教会我在计算顺序上提前避开溢出。希望这篇复盘能让你少走一点我走过的弯路。
