东方博宜OJ刷到1201-1210这段的兄弟多半是在补课程作业或者正在为CSP-J、蓝桥杯这类入门比赛做准备。说实话这段题目放在整个OJ题库里不算难但它刚好卡在语法入门尾巴和简单算法开头的连接处特别容易在细节上翻车少打了个空格、数组开小越界、循环边界差了一位这类低级错我见得太多了。这篇我就把这10道题按最常见的版本逐个拆开讲每道题给出完整思路、参考代码和易错点。我不太建议直接抄代码交差因为OJ的判题系统会查重是一回事更关键的是——这段题几乎是后面所有题目的地基你在这里踩过的坑后面都要加倍还回去。1. 先看清这组题1201-1210到底在考什么1.1 题号背后的训练节奏东方博宜OJ的题号编排有个规律基本上是按照难度阶梯排的。1000出头还在练基本的输入输出、变量类型1100多开始上分支和循环到了1200这一带就明显感觉到题目开始混搭了。不是说单纯考一个知识点而是要把几个基础点串起来用。1201-1210这段我的判断是正处在语法基础收尾、算法思维启蒙的过渡区。题目里既有循环数学题也有数组字符串操作还开始涉及到递推、排序、进制转换这些简单算法。你把它当成一个承上启下的关卡来看就明白为什么学校老师喜欢从中抽题当作业了——它能把前面学的知识全部串一遍又能试探一下你有没有算法思维。1.2 题型分布与难度雷达我按东方博宜OJ里这一段的常见考法把10道题大致归类如下。注意不同学校或平台挂的题目版本可能有细微差异有的把输出大小写改了有的把数据范围扩大了但核心考点基本就是这个分布。题号常见题型核心考点最容易出错的地方1201数列求和循环、等差数列int溢出、边界值1202最大公约数辗转相除法特殊输入、除零1203回文数判断数字拆分输出大小写1204数字反转循环取位负号、前导零1205数组逆序数组、循环数组越界、空格格式1206单词统计getline、状态机换行符残留1207素数筛选埃氏筛数组初始化、超时1208斐波那契数列递推递归爆栈、首项定义1209排序sort或冒泡升降序要求1210进制转换短除法0的特判、倒序输出难度都不算高但如果有一两道题卡住大概率不是不会写而是漏了某个边界情况。下面我按顺序逐题拆。2. 逐题拆解与参考代码上数学与循环基础2.1 1201 数列求和公式比循环更快这道题最常见的版本是输入一个整数n求123...n的值。很多同学的第一反应是写个for循环累加逻辑没错但如果n给到10的9次方量级循环就得跑十亿次轻则超时重则让你怀疑人生。正确做法是直接用等差数列求和公式n * (n 1) / 2。但这里藏着一个新手必踩的坑——直接写int n; cin n; cout n * (n 1) / 2;n一大就溢出了。因为两个int相乘的结果还是int存不下就可能变成负数。#include iostream using namespace std; int main() { long long n; cin n; cout n * (n 1) / 2 endl; return 0; }我自己给学生讲这道题时一定会让他们记住一句话只要题目里的数可能超过10的9次方就老老实实用long long别自作聪明。另外这个公式在n是奇数或偶数时都能整除不用担心除不尽的问题因为n和n1里必然有一个是偶数。2.2 1202 最大公约数与最小公倍数辗转相除法的边界这道题的核心算法就是辗转相除法欧几里得算法思路一句话就能讲清楚两个数a和ba除以b的余数为r然后让abbr不断重复直到余数为0此时的b就是最大公约数。代码实现也很短#include iostream using namespace std; int gcd(int a, int b) { while (b ! 0) { int t a % b; a b; b t; } return a; } int main() { int a, b; cin a b; cout gcd(a, b) endl; return 0; }如果题目还要求输出最小公倍数记住一条先除再乘a / gcd(a, b) * b而不是a * b / gcd(a, b)。原因是a乘以b可能会溢出先除以最大公约数可以把这个风险降下来。还有一点容易被忽略就是a和b谁大谁小其实无所谓辗转相除法第一轮自己会调整不需要提前比较。2.3 1203 回文数判断拆数字的通用套路回文数的定义不用多解释了121正着读反着读都一样。判断方法有很多最通用的是把数字一位一位拆出来然后组成一个新数最后比较新数和原数是否相等。#include iostream using namespace std; int main() { int n, x, rev 0; cin n; x n; while (x 0) { rev rev * 10 x % 10; x / 10; } if (rev n) { cout Yes endl; } else { cout No endl; } return 0; }拆数字的套路就一句话取余拿末位整除去末位。x % 10拿到当前最后一位x / 10把最后一位删掉然后拼到rev后面。这里特别提醒一句输出到底是Yes还是YES是No还是NO以题目原文为准。我见过不少人被这种细节卡到怀疑人生。另一种思路是把数字转成字符串再头尾比较实现更直观但数字拆分法不需要引入字符串库也更能锻炼对整数运算的理解建议两个做法都练一遍。2.4 1204 数字反转负数和零怎么处理数字反转和判断回文其实是同一套核心逻辑只是这道题会多出几个特殊情况。最常见版本是输入一个整数输出它的反转结果比如输入-120输出-21注意不是-021前导零要去掉。#include iostream using namespace std; int main() { int n; cin n; bool isNegative false; if (n 0) { isNegative true; n -n; } int rev 0; while (n 0) { rev rev * 10 n % 10; n / 10; } if (isNegative) { rev -rev; } cout rev endl; return 0; }新手最容易踩的坑就是只处理正数题目一输入-120就懵了。还有一点要注意如果输入的是0或者像100这类反转后开头为0的数用整数算法天然会把前导零丢掉输出1而不是001这恰好符合大多数题目的要求。3. 逐题拆解与参考代码下数组、字符串与简单算法3.1 1205 数组逆序输出数组开多大的学问这道题一般是输入n和n个整数然后逆序输出。很多人第一个反应就是我正着存倒着遍历不就行了对这就是全部思路。#include iostream using namespace std; int a[1005]; int main() { int n; cin n; for (int i 0; i n; i) { cin a[i]; } for (int i n - 1; i 0; i--) { cout a[i]; if (i 0) cout ; } cout endl; return 0; }这里有两个细节值得花时间强调。第一数组到底开多大我见过太多人开a[105]然后题目范围给到1000直接越界。稳妥的习惯是看完题目范围后多开10到20个比如题目说n不超过1000就开a[1005]或a[1010]。第二输出格式。OJ判题时对空格和换行非常敏感用我上面写的if (i 0) cout 这种写法可以保证最后一个数字后面没有多余空格。3.2 1206 单词统计getline与状态机这题常见版本是输入一行英文句子可能包含多个连续空格统计有多少个单词。核心难点在于如果只用cin s空格会被自动跳过反而没法处理。正确姿势是用getline读取整行然后用一个是否正在单词中的标记来统计。#include iostream #include string using namespace std; int main() { string s; getline(cin, s); int cnt 0; bool inWord false; for (char c : s) { if (c ! ) { if (!inWord) { cnt; inWord true; } } else { inWord false; } } cout cnt endl; return 0; }这个方法叫状态机思想通俗说就是用一个变量记住我当前是不是在一个单词里面。碰到非空格且之前不在单词里说明新单词开始了碰到空格就把状态重置。这个套路以后在字符串题目里会反复用到值得重点掌握。有一个经典坑如果题目前面还有一次cin n之类的操作再用getline会直接读到残留的换行符导致字符串为空。解决办法是在cin之后先调用一次getline(cin, 临时字符串)把换行吃掉。3.3 1207 素数筛选O(n log log n)背后的原理求2到n之间的所有素数最朴素的做法是对每个数逐个判断复杂度是O(n√n)n小的时候无所谓n一旦到10的5次方以上就会明显变慢。这里推荐用埃拉托斯特尼筛法简称埃氏筛思路特别形象准备一张从2到n的表从2开始把2的所有倍数划掉然后找到下一个没被划掉的数3把3的所有倍数划掉不断重复。#include iostream using namespace std; const int MAXN 1000005; bool isPrime[MAXN]; int main() { int n; cin n; for (int i 0; i n; i) isPrime[i] true; isPrime[0] isPrime[1] false; for (int i 2; i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) { isPrime[j] false; } } } for (int i 2; i n; i) { if (isPrime[i]) cout i ; } cout endl; return 0; }很多教材会直接给代码但不解释为什么内层循环从i * i开始。原因很简单比i * i小的i的倍数比如2 * i, 3 * i ...在之前更小的素数筛选时已经被划掉了没必要重复操作。这个优化能把常数压下去不少而且代码看着也更专业。如果你把isPrime定义成局部数组记得先初始化定义成全局数组则可以默认全为false但逻辑上还要自己维护。我上面特意写成了全局数组再手动赋true图的就是逻辑直观。3.4 1208 斐波那契数列递推别用递归斐波那契数列的定义是F(1)1F(2)1从第3项开始每项等于前两项之和。代码实现最简单的是递归但n一大就会原地爆炸因为重复计算太多了。别问我怎么知道的我曾经让刚学的学生用递归求第50项半天没跑出来。正确的入门做法是递推用一个循环从第3项一路算到第n项#include iostream using namespace std; int main() { int n; cin n; long long a 1, b 1, c; if (n 2) { cout 1 endl; return 0; } for (int i 3; i n; i) { c a b; a b; b c; } cout b endl; return 0; }这道题有个特别坑的地方有些题目版本里F(0)0、F(1)1有些则是F(1)1、F(2)1两者输出的结果在n比较小时完全不一样。所以做题第一件事是看题目给的定义和样例先拿样例验证你理解的规则对不对再动手写代码。3.5 1209 排序sort能用但底层逻辑得懂排序题在OJ里属于会了不难难了不会的类型。如果平台用的是C直接用sort函数就能轻松搞定#include iostream #include algorithm using namespace std; int a[1005]; int main() { int n; cin n; for (int i 0; i n; i) cin a[i]; sort(a, a n); for (int i 0; i n; i) { cout a[i]; if (i ! n - 1) cout ; } cout endl; return 0; }默认是升序如果题目要求降序加上第三个参数greaterint()就行。不过我也想提醒一句如果你是在课程作业里有些老师会明确规定不能用sort必须手写冒泡或选择排序。这时候你就得理解排序的底层逻辑比如冒泡排序的核心——每轮把相邻的两个数比较并交换把当前最大的数冒到最后面。手写冒泡的代码我就不贴了网上到处都是关键是理解外层循环控制多少轮内层循环控制比较范围每轮结束后比较范围缩小一格。这个思想比背代码重要一百倍。3.6 1210 进制转换短除法倒着读十进制转二进制标准做法是短除法不断除以2记录余数最后把余数倒着拼起来。比如10转二进制10除以2余05除以2余12除以2余01除以2余1倒着读就是1010。#include iostream #include vector using namespace std; int main() { int n; cin n; if (n 0) { cout 0 endl; return 0; } vectorint bits; while (n 0) { bits.push_back(n % 2); n / 2; } for (int i bits.size() - 1; i 0; i--) { cout bits[i]; } cout endl; return 0; }这里最容易被忽略的是n等于0的情况直接输出0不然后面的while循环压根不进去啥也输出不出来。另外如果题目要求转成八进制或十六进制代码只需要把n % 2和n / 2改成对应的基数但十六进制要考虑10到15用A到F表示这时候用vectorint存余数再按需转字符会比较方便。4. OJ判题结果与常见错误排查从WA到AC4.1 判题结果怎么看我在带新手刷题时发现很多人看到WA就懵了不知道自己到底错在哪。先把这个表记住遇到问题起码能判断排查方向。判题结果含义优先排查方向AC全部通过恭喜下一题WA答案错误算法逻辑、边界情况、输出格式PE格式错误空格、换行、大小写RE运行时错误数组越界、除零、递归过深TLE运行超时换更高效的算法、检查死循环MLE内存超限数组开太大、递归爆栈CE编译错误语法问题、忘记引入头文件其中WA和PE看起来像但性质不同。PE说明OJ已经拿到了你的输出只是格式不对比如最后多了一个空格。很多判题系统会把PE单独列出来就是为了提醒你逻辑基本对了改改格式就行。4.2 这段题最容易翻车的5个细节第一个是输出格式。我见过太多人代码逻辑完全正确就因为最后一个数后面多打了一个空格反复提交几十次。养成好习惯要么像我上面那样判断不是最后一个就输出空格要么用字符串拼接好再一次性输出。第二个是整数溢出。1201的n * (n 1) / 2就是个典型n刚过10的5次方int就扛不住了。判断要不要用long long就看题目给的数据范围只要接近10的9次方直接上long long没商量。第三个是数组越界。数组开小了不会马上报错只会在运行时踩到不该踩的内存表现出来就是各种莫名其妙的RE。直接养成习惯数组按最大值再加10或20。第四个是循环边界。i n还是i ni * i n还是i * i n这类问题几乎每道题都会出现。我的习惯是代入特殊值验证比如n1或n2时程序还正不正常。第五个是特殊输入。n0、n1、输入为0、输入为负数这些边界值最容易让代码漏出破绽。样例通常给的是正常值你自己得多测几个边界样例这个习惯是真的能救命。5. 刷完这段题下一步怎么练5.1 同题型的变式与扩展1201-1210是个很好的起点但你想真正把基础打牢光做这10道题不够。我自己刷题的经验是每道题做完之后给自己出几个变式练到看到题目就知道考点在哪的程度。比如数列求和之后你可以去练平方和、立方和、分数数列求和最大公约数之后可以练三个数的最大公约数、最小公倍数应用的日期问题数组逆序之后可以练循环右移、数组去重、合并两个有序数组。这些题目在OJ上一搜一大把每个知识点扩充3到5题你的手感会完全不一样。5.2 提交前自测清单我总结了一个提交前的自测清单每次提交之前花30秒过一遍可以省掉大量提交试错的时间。第一样例能过吗样例过了不代表AC但样例都过不了肯定没戏。第二边界值测了吗n0、n1、n取最大值、输入负数这些特殊输入跑一遍。第三输出格式检查了吗最后一行的换行、最后一个数字后的空格、大小写、中英文括号全部对一遍。第四数据类型对吗会不会溢出要不要用long long。第五数组够大吗有没有多开余量。这套清单看着简单真能坚持下来的人不多。我见过太多人样例一遍过、自信满满提交结果WA得一脸茫然回来一查不是少了个等于号就是数组开小了。说说我自己带学生刷这套题的一点体会。很多人以为OJ刷题就是比谁代码敲得快其实不是。做得快的同学往往是花时间读题、在草稿纸上推演、想清楚边界条件之后才动手敲键盘的。1201-1210这10道题每道题都不难但它们组合起来就是在训练你一件事把一个模糊的题目转化成清晰的、可运行的逻辑。另外分享一个小技巧刷完每道题之后不管AC没AC都在自己的笔记里记一行这题考了什么知识点我第一遍漏了什么条件以后遇到同类题要提醒自己注意什么。积累一段时间你就会发现犯过的错基本不会再犯第二次。这比刷题数量重要太多了。
与search()核心区别详解)
