1. 基础题3、5、6到底在考察什么先看清OJ的门道很多刚开始刷题的同学看到基础 3 5 6这种题号都会有点懵不知道它对应的是什么样的题目也不知道为什么这三道题会被放在一起。我最近把某高校在线评测平台下面简称OJ基础题库里的这三道题从头到尾重刷了一遍才发现这个编号顺序其实是有讲究的它们对应的正是OJ刷题最核心的三件事——输入输出格式处理、基础算法应用、边界情况排查。把这三道题吃透后面再碰更复杂的题起码不会因为低级问题卡到怀疑人生。1.1 三道题在能力阶梯上的位置先说第3题。它在题库里属于输入输出练习的范畴表面上看只是求和但真正让人犯错的点在于题目怎么描述输入数据。OJ和平时自己写程序最大的区别是你面对的不是一个交互式输入而是评测系统预先准备好的一批测试数据。程序要能从标准输入里读完所有数据处理完再按格式输出。很多第一次刷OJ的人会在这里翻车原因就是没有意识到多组数据意味着什么。第5题则是排序。它考察的不只是你会不会写排序算法更重要的是你能否在规定的时限内处理完题目给的数据量。排序是所有算法题的地基树状数组、线段树、二分查找这些高级主题底层全是排序和有序性的思维。这道题我选择了手写排序而不是直接调用库函数原因后面会详细说。第6题是字符串处理。字符串在OJ题里是出了名的看起来简单、做起来全是坑因为你要同时处理字符数组的读入、终止符、空白字符、ASCII边界等一系列问题。这道题我从零重构了读入逻辑才把评测状态从答案错误刷成通过。1.2 拿到题目第一件事别急着写代码我见过不少同学包括早期的我自己一看到题目描述末尾那句输出样例即可就开始噼里啪啦敲键盘。这是刷OJ的大忌。正确做法是先静下心分析三件事输入以什么形式结束EOF特定位数的n换行符、输出对换行和空格的要求是什么、数据范围是否大到需要改变算法策略。以这三道基础题为例它们的输入规模都不大暴力解法完全可行但输入格式的坑相当多。第3题要求你不断读入n如果n等于0就终止第5题第一行给整数个数m第二行给m个整数第6题输入一行字符串可能包含空格。这些细节如果在写代码前没有理清楚后面WA错误答案一次就要回去改半天代码。所以我把刷题的第一个步骤固定成了把题目描述复制到本地用黑色加粗标出输入格式和输出格式两段看完之后再动手。这个习惯看着不起眼但帮我避开了至少80%的格式类错误。2. 第3题多组输入下的求和问题第一步就卡住一半人第3题的原题描述大概是这样的输入包含多组测试数据每组数据第一个数为n表示本组有n个整数当n为0时结束每组输出所有整数的和。看起来是不是很简单但这道题提交一次的通过率并不高原因就出在最基础的读入方式上。2.1 题目形态与隐藏边界先说题目形态。n的取值题目里没有明说但从基础题库的难度来推断n大概率在100以内整数范围也在int可承受的范围内。这意味着不需要开long long也不需要优化算法纯属考察你能不能把多组数据正确地读完、正确地和累加完。隐藏边界有两处。第一处是n为0时结束——有些同学看到这一句会真的把0当作一组数据去处理于是程序卡死在读入循环里或者输出一个多余的0。第二处是每组数据的输出后面要不要空行。OJ评测是逐字符比对的多一个空格、少一个换行都会被标记为格式错误PE虽然比WA好一点但同样不能通过。2.2 错误示范与正确写法我最初提交的版本长这样看起来没毛病但就是WA#include stdio.h int main() { int n; while (scanf(%d, n) ! EOF) { if (n 0) break; int sum 0, x; for (int i 0; i n; i) { scanf(%d, x); sum x; } printf(%d\n, sum); } return 0; }这个代码的问题出在哪它在本地自己试的时候没有问题但OJ里有一个测试点是n为0的情况终止循环理论上也没问题。后来我排查了很久才发现问题藏在scanf的返回值上某些版本的OJ评测数据里会出现只有n后面没有数据的情况此时scanf(%d, n)返回的是0而不是EOF程序就直接进入死循环了。正确的写法应该对scanf的返回值做严格判断#include stdio.h int main() { int n; while (scanf(%d, n) 1) { if (n 0) break; int sum 0, x; for (int i 0; i n; i) { scanf(%d, x); sum x; } printf(%d\n, sum); } return 0; }这两种写法在日常本地运行中几乎看不出差别但在评测系统的边界数据下返回值的差异就是AC和WA的区别。这一点是第3题教给我最深刻的一课OJ的读入永远不要用想当然的方式。3. 第5题排序问题的真相是调库还是手写第5题是给出一组整数要求从小到大输出。题目描述非常短数据规模给的是m小于等于1000看起来很基础。但在刷这道题的时候我更关注的问题是手写排序还是调用库函数不同选择背后的代价完全不同。3.1 为什么排序题容易把人带偏资源少、时间紧的新手最容易走的一条弯路是一看到排序就想直接调用qsort或sort函数。这样做本身没有错在工程开发中我也会这么干但在OJ基础题里我强烈建议至少手写一次排序。原因有三点第一基础题的意义就是让你理解算法本身。冒泡、选择、插入这三种排序代码量都不长自己写一遍能直观感受到比较次数和交换次数这也是后面学习复杂排序算法的前提。第二OJ评测讲究稳定库函数的排序实现虽然强大但如果你不理解它的比较器怎么写反而容易在结构体排序上犯错比如把降序写成升序或者比较函数返回值不符合规则。第三手写排序还能让你养成手动模拟数据流的习惯这在排查WA时尤其重要。3.2 手写选择排序和调用qsort的取舍对m小于等于1000的数据量选择排序的O(m²)完全够用。我实践下来的代码是这样#include stdio.h int main() { int m; int arr[1005]; scanf(%d, m); for (int i 0; i m; i) { scanf(%d, arr[i]); } for (int i 0; i m - 1; i) { int minIdx i; for (int j i 1; j m; j) { if (arr[j] arr[minIdx]) { minIdx j; } } if (minIdx ! i) { int tmp arr[i]; arr[i] arr[minIdx]; arr[minIdx] tmp; } } for (int i 0; i m; i) { if (i 0) printf( ); printf(%d, arr[i]); } printf(\n); return 0; }这里有一个容易被忽略的输出要求两个数之间以空格分隔行尾不能有多余空格但整行末尾必须有换行。我见过很多人在输出时直接写printf(%d , arr[i]);最后一个数后面自然会多一个空格OJ就会判格式错误。如果你确实想用库函数也不是不行。C语言里用qsort注意比较函数要写成int cmp(const void *a, const void *b) { int ia *(int *)a; int ib *(int *)b; return ia - ib; }C里用sort更简单sort(arr, arr m);默认就是升序。但要记住手写排序不是笨它让你在数据范围变大的时候能自然想到归并排序、快速排序这些更优的方案。如果一上来就只会调库后面遇到需要自定义排序规则的题会比较痛苦。4. 第6题字符串处理的隐藏坑位从一次WA说起第6题看起来也不难输入一行字符统计其中数字字符的个数并输出。题干就一句话没有特殊说明。但正是这种没有特殊说明让很多人在同一处栽跟头这一行字符里到底有没有空格4.1 题目描述看似友好陷阱在字符类型判断如果这一行字符不包含空格那么用scanf(%s, str)读入就够了但OJ评测数据里往往混有空格字符串变成类似abc 123 def 456这种形式。scanf(%s)遇到空白字符就会停止读入后面的数字根本读不进来统计结果自然出错。当时我的思路是这样的先用char数组存字符串然后遍历每个字符判断ASCII值在0到9之间就计数。逻辑没错但我使用的读入函数错了。这就是典型的算法对了输入处理错了整个程序等于白写。4.2 排查链路从读入方式到ASCII边界我第一次提交的代码是#include stdio.h #include string.h int main() { char str[1005]; scanf(%s, str); int cnt 0; for (int i 0; i strlen(str); i) { if (str[i] 0 str[i] 9) { cnt; } } printf(%d\n, cnt); return 0; }本地测试abc123没问题但我拿包含空格的测试样例一跑发现输出完全不对。这就是WA的根源。排查过程其实不复杂我用一个最简单的调试方式把读入的字符串原样打印出来看看它到底收到了什么。打印结果发现我的程序只收到了abc后面的123根本没被读进数组。正确的做法是使用gets或者fgets来读取带空格的一整行#include stdio.h #include string.h int main() { char str[1005]; if (fgets(str, sizeof(str), stdin) ! NULL) { int cnt 0; for (int i 0; str[i] ! \0 str[i] ! \n; i) { if (str[i] 0 str[i] 9) { cnt; } } printf(%d\n, cnt); } return 0; }这里要特别留意fgets的两个特点第一它会保留末尾的换行符\n所以遍历时要做判断否则把换行符也算进去就会莫名少1个第二如果字符串长度超过数组容量它会把剩余字符留在输入缓冲区里所以数组尽量开大一点题目没有给范围时1000到2000都是安全的。从这次WA里我总结出一个排查链路先打印读入的内容确认输入处理没错再打印计数结果确认统计逻辑没错最后检查输出格式。把这个顺序固化下来字符串类题目的错误率会直线下降。5. 基础题刷完之后我踩过的坑和真正有用的经验三道题刷完我的评价是它们不难但非常值得做。因为它们展开了一个完整的OJ刷题视角——既有输入输出细节又有算法手写训练还有字符串处理技巧。更关键的是它们让我踩了一串真实的坑这些坑比多刷十道套模板的题还有价值。5.1 新手最容易反复WA的五个细节我把自己在刷题过程中踩过的坑整理了一张表非常有代表性细节错误表现正确做法scanf返回值死循环或漏读数据判断 1而不是! EOF输出行尾空格格式错误PE用辅助变量控制首尾空格字符串含空格只读到空格前内容用fgets/gets读整行换行符残留字符串多出\n遍历时过滤\n数组越界结果错误或崩溃数组开大至少100到200这些细节在教程里很难被当作重点讲但在评测系统里每一个都会让你的提交状态从AC变成WA或PE。5.2 关于OJ刷题节奏的个人建议最后分享一点个人体会。不要因为这是基础题就直接跳过也不要一个晚上把三道题全部硬啃下来。我一个晚上只刷两道刷完先不看别人的题解自己复现一遍再隔两天重新提交一次看自己是否还记得写法的核心逻辑。这种方法比一次刷十道题有效得多。因为OJ刷题的本质不是我做过这道题而是我彻底理解了它背后的模式。基础3、5、6这三道题让我牢牢记住了读入必须严格校验输出格式必须精确到结尾无空格这两个原则。在后面的进阶题目里这两条原则又帮我挡住了一大批低级错误。如果你也正卡在OJ基础阶段建议你可以找找类似的题号认真把输入输出这块地基打牢。刷题这条路没有捷径但它有一个很友好的规律前期踩过的每一个坑都会在后面的题里以另一种形式回报给你。
1. 基础题3、5、6到底在考察什么先看清OJ的门道很多刚开始刷题的同学看到基础 3 5 6这种题号都会有点懵不知道它对应的是什么样的题目也不知道为什么这三道题会被放在一起。我最近把某高校在线评测平台下面简称OJ基础题库里的这三道题从头到尾重刷了一遍才发现这个编号顺序其实是有讲究的它们对应的正是OJ刷题最核心的三件事——输入输出格式处理、基础算法应用、边界情况排查。把这三道题吃透后面再碰更复杂的题起码不会因为低级问题卡到怀疑人生。1.1 三道题在能力阶梯上的位置先说第3题。它在题库里属于输入输出练习的范畴表面上看只是求和但真正让人犯错的点在于题目怎么描述输入数据。OJ和平时自己写程序最大的区别是你面对的不是一个交互式输入而是评测系统预先准备好的一批测试数据。程序要能从标准输入里读完所有数据处理完再按格式输出。很多第一次刷OJ的人会在这里翻车原因就是没有意识到多组数据意味着什么。第5题则是排序。它考察的不只是你会不会写排序算法更重要的是你能否在规定的时限内处理完题目给的数据量。排序是所有算法题的地基树状数组、线段树、二分查找这些高级主题底层全是排序和有序性的思维。这道题我选择了手写排序而不是直接调用库函数原因后面会详细说。第6题是字符串处理。字符串在OJ题里是出了名的看起来简单、做起来全是坑因为你要同时处理字符数组的读入、终止符、空白字符、ASCII边界等一系列问题。这道题我从零重构了读入逻辑才把评测状态从答案错误刷成通过。1.2 拿到题目第一件事别急着写代码我见过不少同学包括早期的我自己一看到题目描述末尾那句输出样例即可就开始噼里啪啦敲键盘。这是刷OJ的大忌。正确做法是先静下心分析三件事输入以什么形式结束EOF特定位数的n换行符、输出对换行和空格的要求是什么、数据范围是否大到需要改变算法策略。以这三道基础题为例它们的输入规模都不大暴力解法完全可行但输入格式的坑相当多。第3题要求你不断读入n如果n等于0就终止第5题第一行给整数个数m第二行给m个整数第6题输入一行字符串可能包含空格。这些细节如果在写代码前没有理清楚后面WA错误答案一次就要回去改半天代码。所以我把刷题的第一个步骤固定成了把题目描述复制到本地用黑色加粗标出输入格式和输出格式两段看完之后再动手。这个习惯看着不起眼但帮我避开了至少80%的格式类错误。2. 第3题多组输入下的求和问题第一步就卡住一半人第3题的原题描述大概是这样的输入包含多组测试数据每组数据第一个数为n表示本组有n个整数当n为0时结束每组输出所有整数的和。看起来是不是很简单但这道题提交一次的通过率并不高原因就出在最基础的读入方式上。2.1 题目形态与隐藏边界先说题目形态。n的取值题目里没有明说但从基础题库的难度来推断n大概率在100以内整数范围也在int可承受的范围内。这意味着不需要开long long也不需要优化算法纯属考察你能不能把多组数据正确地读完、正确地和累加完。隐藏边界有两处。第一处是n为0时结束——有些同学看到这一句会真的把0当作一组数据去处理于是程序卡死在读入循环里或者输出一个多余的0。第二处是每组数据的输出后面要不要空行。OJ评测是逐字符比对的多一个空格、少一个换行都会被标记为格式错误PE虽然比WA好一点但同样不能通过。2.2 错误示范与正确写法我最初提交的版本长这样看起来没毛病但就是WA#include stdio.h int main() { int n; while (scanf(%d, n) ! EOF) { if (n 0) break; int sum 0, x; for (int i 0; i n; i) { scanf(%d, x); sum x; } printf(%d\n, sum); } return 0; }这个代码的问题出在哪它在本地自己试的时候没有问题但OJ里有一个测试点是n为0的情况终止循环理论上也没问题。后来我排查了很久才发现问题藏在scanf的返回值上某些版本的OJ评测数据里会出现只有n后面没有数据的情况此时scanf(%d, n)返回的是0而不是EOF程序就直接进入死循环了。正确的写法应该对scanf的返回值做严格判断#include stdio.h int main() { int n; while (scanf(%d, n) 1) { if (n 0) break; int sum 0, x; for (int i 0; i n; i) { scanf(%d, x); sum x; } printf(%d\n, sum); } return 0; }这两种写法在日常本地运行中几乎看不出差别但在评测系统的边界数据下返回值的差异就是AC和WA的区别。这一点是第3题教给我最深刻的一课OJ的读入永远不要用想当然的方式。3. 第5题排序问题的真相是调库还是手写第5题是给出一组整数要求从小到大输出。题目描述非常短数据规模给的是m小于等于1000看起来很基础。但在刷这道题的时候我更关注的问题是手写排序还是调用库函数不同选择背后的代价完全不同。3.1 为什么排序题容易把人带偏资源少、时间紧的新手最容易走的一条弯路是一看到排序就想直接调用qsort或sort函数。这样做本身没有错在工程开发中我也会这么干但在OJ基础题里我强烈建议至少手写一次排序。原因有三点第一基础题的意义就是让你理解算法本身。冒泡、选择、插入这三种排序代码量都不长自己写一遍能直观感受到比较次数和交换次数这也是后面学习复杂排序算法的前提。第二OJ评测讲究稳定库函数的排序实现虽然强大但如果你不理解它的比较器怎么写反而容易在结构体排序上犯错比如把降序写成升序或者比较函数返回值不符合规则。第三手写排序还能让你养成手动模拟数据流的习惯这在排查WA时尤其重要。3.2 手写选择排序和调用qsort的取舍对m小于等于1000的数据量选择排序的O(m²)完全够用。我实践下来的代码是这样#include stdio.h int main() { int m; int arr[1005]; scanf(%d, m); for (int i 0; i m; i) { scanf(%d, arr[i]); } for (int i 0; i m - 1; i) { int minIdx i; for (int j i 1; j m; j) { if (arr[j] arr[minIdx]) { minIdx j; } } if (minIdx ! i) { int tmp arr[i]; arr[i] arr[minIdx]; arr[minIdx] tmp; } } for (int i 0; i m; i) { if (i 0) printf( ); printf(%d, arr[i]); } printf(\n); return 0; }这里有一个容易被忽略的输出要求两个数之间以空格分隔行尾不能有多余空格但整行末尾必须有换行。我见过很多人在输出时直接写printf(%d , arr[i]);最后一个数后面自然会多一个空格OJ就会判格式错误。如果你确实想用库函数也不是不行。C语言里用qsort注意比较函数要写成int cmp(const void *a, const void *b) { int ia *(int *)a; int ib *(int *)b; return ia - ib; }C里用sort更简单sort(arr, arr m);默认就是升序。但要记住手写排序不是笨它让你在数据范围变大的时候能自然想到归并排序、快速排序这些更优的方案。如果一上来就只会调库后面遇到需要自定义排序规则的题会比较痛苦。4. 第6题字符串处理的隐藏坑位从一次WA说起第6题看起来也不难输入一行字符统计其中数字字符的个数并输出。题干就一句话没有特殊说明。但正是这种没有特殊说明让很多人在同一处栽跟头这一行字符里到底有没有空格4.1 题目描述看似友好陷阱在字符类型判断如果这一行字符不包含空格那么用scanf(%s, str)读入就够了但OJ评测数据里往往混有空格字符串变成类似abc 123 def 456这种形式。scanf(%s)遇到空白字符就会停止读入后面的数字根本读不进来统计结果自然出错。当时我的思路是这样的先用char数组存字符串然后遍历每个字符判断ASCII值在0到9之间就计数。逻辑没错但我使用的读入函数错了。这就是典型的算法对了输入处理错了整个程序等于白写。4.2 排查链路从读入方式到ASCII边界我第一次提交的代码是#include stdio.h #include string.h int main() { char str[1005]; scanf(%s, str); int cnt 0; for (int i 0; i strlen(str); i) { if (str[i] 0 str[i] 9) { cnt; } } printf(%d\n, cnt); return 0; }本地测试abc123没问题但我拿包含空格的测试样例一跑发现输出完全不对。这就是WA的根源。排查过程其实不复杂我用一个最简单的调试方式把读入的字符串原样打印出来看看它到底收到了什么。打印结果发现我的程序只收到了abc后面的123根本没被读进数组。正确的做法是使用gets或者fgets来读取带空格的一整行#include stdio.h #include string.h int main() { char str[1005]; if (fgets(str, sizeof(str), stdin) ! NULL) { int cnt 0; for (int i 0; str[i] ! \0 str[i] ! \n; i) { if (str[i] 0 str[i] 9) { cnt; } } printf(%d\n, cnt); } return 0; }这里要特别留意fgets的两个特点第一它会保留末尾的换行符\n所以遍历时要做判断否则把换行符也算进去就会莫名少1个第二如果字符串长度超过数组容量它会把剩余字符留在输入缓冲区里所以数组尽量开大一点题目没有给范围时1000到2000都是安全的。从这次WA里我总结出一个排查链路先打印读入的内容确认输入处理没错再打印计数结果确认统计逻辑没错最后检查输出格式。把这个顺序固化下来字符串类题目的错误率会直线下降。5. 基础题刷完之后我踩过的坑和真正有用的经验三道题刷完我的评价是它们不难但非常值得做。因为它们展开了一个完整的OJ刷题视角——既有输入输出细节又有算法手写训练还有字符串处理技巧。更关键的是它们让我踩了一串真实的坑这些坑比多刷十道套模板的题还有价值。5.1 新手最容易反复WA的五个细节我把自己在刷题过程中踩过的坑整理了一张表非常有代表性细节错误表现正确做法scanf返回值死循环或漏读数据判断 1而不是! EOF输出行尾空格格式错误PE用辅助变量控制首尾空格字符串含空格只读到空格前内容用fgets/gets读整行换行符残留字符串多出\n遍历时过滤\n数组越界结果错误或崩溃数组开大至少100到200这些细节在教程里很难被当作重点讲但在评测系统里每一个都会让你的提交状态从AC变成WA或PE。5.2 关于OJ刷题节奏的个人建议最后分享一点个人体会。不要因为这是基础题就直接跳过也不要一个晚上把三道题全部硬啃下来。我一个晚上只刷两道刷完先不看别人的题解自己复现一遍再隔两天重新提交一次看自己是否还记得写法的核心逻辑。这种方法比一次刷十道题有效得多。因为OJ刷题的本质不是我做过这道题而是我彻底理解了它背后的模式。基础3、5、6这三道题让我牢牢记住了读入必须严格校验输出格式必须精确到结尾无空格这两个原则。在后面的进阶题目里这两条原则又帮我挡住了一大批低级错误。如果你也正卡在OJ基础阶段建议你可以找找类似的题号认真把输入输出这块地基打牢。刷题这条路没有捷径但它有一个很友好的规律前期踩过的每一个坑都会在后面的题里以另一种形式回报给你。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
