简介杭州电子科技大学在线OJ题解代码合集面向准备算法竞赛、课程实验与在线刷题的编程学习者覆盖1000至1099号共一百道题目的C/C实现可用于对照解题思路、补齐边界处理并理解常见算法在真实题目中的落地方式。压缩包内共九十个文件以六十二个cpp和十六个c源码为主体另含少量VC60工程配置、调试中间文件与可执行文件整体约1.1MB体积轻便适合本地编译验证与按题号检索。已有1840人学习说明该题解在杭电OJ练习群体中具备一定参考价值。读者可从中获得排序、查找、动态规划、图论、数学推理等题型的完整代码样本并借助已调试通过的实现观察输入输出格式、边界条件与性能取舍工程文件也便于在旧版VC环境中直接打开运行适合作为刷题复盘和算法入门的辅助材料。1. 开篇1000 号段的分比你想象中更容易漏很多人打开某高校在线评测平台的 1000–1099 题号段代码扫一眼觉得都是入门题跳过不练。真正在机试现场丢分最多的地方恰恰是这一段。前二十题考循环和判断往后考的是读题能力——多组输入读到什么条件停、每组结果之间要不要空行、中间结果会不会溢出 int。这些跟算法无关判题机却一分不让。这份题号段代码的用处不是替你想思路而是把一百道题里反复出现的读入写法、输出写法、边界处理固化成手感。三类人最该刷第一次上机不知道怎么读数据、逻辑写得对但总被判格式错、以及想在两周内把基础题速度提起来的人。企业笔试和推免机试的第一批题走的也是同一套路数。2. 考点地图1000–1099 题号段的四层难度与拿分顺序2.1 一百道题其实只有四层先认清自己卡在哪层这段题号不是均匀铺开的它有一条很清晰的爬坡线。前段是语法层一道题只转一个弯中段开始上数据结构的雏形后段已经接近小型模拟题。刷之前先分层比盲目从 1000 顺着往下做效率高得多。很多人的问题是把时间全花在第一层反复做已经会的题一遇到多组输入就卡住然后就停在那里不动了。层级典型形态拿分要点最常见失分第一层 语法两数运算、判断、单层循环读入读干净输出不多不少多打一句提示语、末尾多空格第二层 多组数据求和、统计、读到结束标志终止条件写准漏最后一组、死循环第三层 字符串统计字符、大小写、回文、拆分下标边界和字符分类越界、负数传给字符函数第四层 结构与模拟结构体排序、日期、进制、图形比较函数写对、状态每次重算排序比较写、闰年表不更新第一层的分是白送的做对不算本事做快了才算。第二层是全段的枢纽卡在这里的人最多因为判题机不会告诉你「你少读了一组」它只给你一个 WA。第三层开始出现数组和字符串越界不一定崩但结果会错。第四层是拉分项涉及排序和模拟的题代码量上去了出错点也从一处变成五处。2.2 多组输入三种终止形态和一行判定的写法题号段里将近三分之一是「多组数据」题。这类题不看算法只看你会不会读。常见的有三种终止形态读到文件结尾、先给组数、读到特定标志比如两个 0 或一个 0结束。写错任何一种样例能过提交全错。#include cstdio int main() { int a, b; // scanf 返回成功读入的变量个数读到文件末尾返回 EOF值是 -1 // 用 ! EOF 判断不要用 while (1) 再在内部 break容易漏掉第一种写法 while (scanf(%d%d, a, b) ! EOF) { printf(%d\n, a b); } return 0; }这段的关键在scanf的返回值。它返回的是「成功匹配并赋值了几个变量」全部成功是 2只读到一个是 1一个都没读到是EOF。所以更稳的写法是while (scanf(%d%d, a, b) 2)因为它同时挡住了「只读到半个输入」这种脏数据情况。先给组数的题型是另一种节奏循环次数由第一行决定int t; scanf(%d, t); while (t--) { // t 组数据t-- 在判断时用的是旧值 int n; scanf(%d, n); // 每组内部重新初始化累加器这一步漏了就是连环错 long long sum 0; for (int i 0; i n; i) { int x; scanf(%d, x); sum x; } printf(%lld\n, sum); }while (t--)是一个能省一行但容易误读的写法等价于「执行 t 次」。如果读起来别扭换成for (int i 0; i t; i)更保险。累加器必须在循环体内重新置零放在外面就会把上一组的结果带进来这类错误在提交记录里非常常见。第三种是「读到 0 0 结束」判定要写在循环条件里而不是在循环体末尾判断后breakwhile (scanf(%d%d, a, b) 2 (a ! 0 || b ! 0)) { printf(%d\n, a b); }注意中间的||不能写成。a ! 0 || b ! 0的意思是「两个不同时为 0」而a ! 0 b ! 0会把3 0这种合法数据也踢出去。用 C 的cin 时cin在while条件里会被转换成布尔值读到结尾自动为假写起来更短while (cin a b) { ... }。但要注意它默认和scanf是同步的数据量大时会慢题号段这点数据量无所谓。2.3 输入输出格式空格、换行、空行这三件事判题机对格式的容忍度比人低。同一个答案多一个空格就是错。号段里关于格式的约定基本就三条行内元素之间用一个空格分隔、行末不留空格、多组数据之间是否需要空行要看题目明说。行末不留空格的常见写法是「第一个元素直接输出后面的先输出空格再输出元素」而不是「每个元素后面跟一个空格最后再想办法删」。后者做起来别扭还容易在只有一行输出时出错。// 输出 n 个数行内空格分隔行末无空格 for (int i 0; i n; i) { if (i 0) printf( ); // 空格打在元素前面天然不会有多余的结尾空格 printf(%d, a[i]); } printf(\n);空行是最容易踩的一个。题目如果说「每组输出之间空一行」正确的做法是先输出第一组之后每一组都「先打空行再打结果」或者用「不是第一组就多打一个换行」的判断。写错的方向通常是把换行放在每组末尾结果最后多出一个空行判题机照样判错。浮点数题还有一个隐藏要求保留几位小数。printf(%.2f\n, x)会自动四舍五入但整数除法的结果永远是整数1/2得到 0 而不是 0.5必须写成1.0/2或显式转换。这个坑在求平均值、求比值的题里出现频率极高。提示题目里凡是出现「精确到」「保留」「四舍五入」这类词先确认变量类型是不是浮点再确认输出格式串有没有写位数。3. 高频题型五类反复出现的题和对应模板3.1 数值计算溢出和精度是两个不同的坑号段里的计算题分两类。一类是常规整型运算坑在溢出一类是高精度坑在不能用内置类型。先说溢出。int在常见环境下是 32 位能装到约 21 亿。题号段里凡是让求阶乘、累加、幂次的题十几项就能顶穿这个上限。判断方法很简单粗算一下最大值超过 2×10⁹ 就换long long超过 1.8×10¹⁹ 就说明这题根本不是让你用内置类型做的。再说高精度。这类题的信号词是「位数不超过」「很大的整数」「不用考虑前导零」。看到这些直接从字符串入手按位模拟竖式。核心逻辑只有三行对应位相加、加上低位进位、取模留位、整除得新进位。求平均值、比值的题要注意整数除法的截断方向。C 的整数除法是向零取整负数时和「向下取整」不一样。如果题目要求向下取整而数据可能是负数得单独处理。3.2 字符串处理下标、分类、整行读入字符串题在号段里主要考四件事统计某类字符个数、大小写转换、判断回文、按分隔符拆词。它们的共同前提是「把一整行完整读进来」。cin s遇到空格就停读不了带空格的句子。要用getline(cin, line)。但这里有个经典陷阱如果前面用过cin 输入缓冲区里残留的换行符会被getline立刻吃掉导致读到一个空串。int n; cin n; cin.ignore(); // 丢掉 n 后面那个换行否则下面的 getline 读到空行 string line; getline(cin, line);字符分类不要手写if (c a c z)标准库有现成的isalpha判字母、isdigit判数字、isspace判空白、toupper/tolower转大小写。但这类函数接受的是int直接传char时如果字符值超过 127中文、扩展 ASCII会变成负数行为未定义。规范写法是先转成unsigned charisalpha((unsigned char)c)。这条不算玄学是血泪经验某些平台上不加转换就会随机出错。判断回文用双指针从两端往中间收遇到不相等立刻返回 false注意题目是否要求「忽略大小写和非字母字符」这是两个不同的难度。3.3 排序与结构体比较函数必须写成严格弱序结构体排序是号段后段的常客通常要求多关键字先按分数从高到低同分按名字字典序再同按输入顺序。写法是给sort传一个自定义比较函数或者 lambda。这里唯一需要记住的规则比较函数必须满足严格弱序也就是对任意两个元素x、ycmp(x, y)和cmp(y, x)不能同时为真。实践中的表现就是——判等的时候用!不要用。sort(v.begin(), v.end(), [](const Student x, const Student y) { if (x.score ! y.score) return x.score y.score; // 分数不同降序 if (x.name ! y.name) return x.name y.name; // 同分看名字升序 return x.id x.id; // 再同看输入顺序 });如果写成if (x.score y.score) return true;当两个元素分数相同时cmp(a,b)和cmp(b,a)都返回真sort的内部实现可能越界访问表现为「本地跑得好好的提交就 RE」。这个错误极难通过看代码发现因为逻辑看起来是对的。另一个细节是「稳定」。sort不保证相等元素的相对顺序需要稳定时用stable_sort。但在这种题里更省事的办法是给结构体加一个记录输入序号的字段用它兜底效果和稳定性一致还不依赖库实现。3.4 枚举与模拟日期、进制、图形打印三件套模拟题没有统一模板但号段里反复出现的就三种。日期题考的是闰年判断和月份天数表。闰年规则能被 4 整除且不能被 100 整除或者能被 400 整除。月份天数表不能写死在循环外因为每一组数据的年份都不同bool isLeap(int y) { return (y % 4 0 y % 100 ! 0) || (y % 400 0); } int month[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // 关键month[2] 必须跟着当前年份走多组数据时每次都要重算 month[2] isLeap(y) ? 29 : 28;进制转换考的是逐位累乘。转十进制时不要用pow逆序加权浮点误差会在高位上放大正确写法是从左到右v v * r d全程整数运算。十进制转其他进制用取模倒排注意 0 要单独处理否则输出空串。图形打印考的是找规律。给一个菱形模板核心是把「空格数」和「星号数」写成行号的函数然后分上下两半各写一个循环// 上半部分含中间行第 i 行从 1 开始空格 n-i 个星号 2i-1 个 for (int i 1; i n; i) { for (int j 0; j n - i; j) cout ; for (int j 0; j 2 * i - 1; j) cout *; cout \n; }下半部分把i从 1 走到 n-1空格数改成i星号数改成2*(n-i)-1。写这类题先在纸上把前三行画出来标上空格数和星号数规律自然就出来了硬凑公式反而慢。4. 真题演练五道典型题的逐行思路与代码4.1 多组求和先把读入方式定下来再想逻辑题目形态连续输入若干组数据每组先给一个整数 n后面跟 n 个整数求这组的和读到输入结束为止。思路顺序是固定的先定终止条件读到文件末尾再定每组内部的读入循环最后定输出格式每组一行。很多人一上来就写累加结果外层循环条件写错样例只过第一组。#include cstdio int main() { int n; // 外层只要能读到一个 n就说明还有一组数据 while (scanf(%d, n) 1) { long long sum 0; // 必须写在循环内部每组清零 for (int i 0; i n; i) { int x; scanf(%d, x); sum x; // 用 long long 兜住 n 很大时的累加溢出 } printf(%lld\n, sum); // %lld 对应 long long用 %d 会输出错值 } return 0; }讲解两句。scanf(%d, n) 1这个判断比! EOF更严格它挡住了「读到半个数字」的情况。sum用long long是因为题目没说 n 和元素的范围一万个十万相加就到 10⁹五万个就顶穿了 int。输出格式串必须和类型匹配long long用%lld用%d在 64 位环境下会读到错误的字节。4.2 大数相加字符串模拟竖式题目形态输入两个很长的非负整数位数可能上百输出它们的和。判分点只有一个能不能不用内置类型把它算出来。做法是把两个数当字符串从末尾往前逐位相加维护一个进位变量。循环终止条件是「两个串都走完了并且进位也是 0」——最后这个条件最容易漏导致最高位的进位被丢掉。#include iostream #include string #include algorithm using namespace std; int main() { string a, b; while (cin a b) { string res; int i a.size() - 1, j b.size() - 1, carry 0; // 三个条件缺一不可a 没走完、b 没走完、还有进位 while (i 0 || j 0 || carry) { int sum carry; if (i 0) sum a[i--] - 0; // 字符减 0 得到数值 if (j 0) sum b[j--] - 0; res.push_back(char(0 sum % 10)); // 留当前位 carry sum / 10; // 进位带到下一轮 } reverse(res.begin(), res.end()); // 刚才是个位在前要翻回来 // 结果可能是 000去掉前导零但至少保留一位 size_t pos res.find_first_not_of(0); cout (pos string::npos ? 0 : res.substr(pos)) endl; } return 0; }参数说明几个点。a[i--] - 0里同时完成了「取值」和「下标前移」两件事写紧凑但可读不习惯就拆成两行。char(0 sum % 10)是把数字位还原成字符不加char转换在部分编译器上会报 narrowing 警告。去前导零那一段是必需的因为输入可能是0和0或者两数相加恰好是整十整百。4.3 字符串统计分类计数与整行读入题目形态输入一行字符分别统计字母、数字、空格和其他字符的个数输出四个数。这题不难但有两个点是成规模的失分源。第一cin 读不到空格必须getline第二字符分类函数要传unsigned char。#include iostream #include string #include cctype using namespace std; int main() { string line; int letters 0, digits 0, spaces 0, others 0; while (getline(cin, line)) { // 一行一行读能处理多行输入 for (char c : line) { unsigned char u (unsigned char)c; // 先转无符号避免负值传入 if (isalpha(u)) letters; else if (isdigit(u)) digits; else if (c ) spaces; else others; } } cout letters digits spaces others endl; return 0; }while (getline(...))的好处是自动处理「有多行」和「只有一行」两种情况不用额外判断。判断空格用的是c 而不是isspace(u)因为题目里的「其他字符」通常不含制表符用isspace会把制表符也算进空格和题意不符。这类细节必须回读题面确认不能凭感觉。4.4 结构体多关键字排序比较函数是唯一的雷区题目形态给 n 个学生的姓名和成绩按成绩从高到低输出成绩相同按姓名升序都一样按输入顺序。写这题的正确姿势是先把结构体定出来把「输入序号」当第三个字段存进去然后写比较函数。比较函数按优先级逐层判断每一层都用「不等」作为进入条件。#include iostream #include vector #include string #include algorithm using namespace std; struct Student { string name; int score; int id; // 输入顺序兜底用 }; int main() { int n; cin n; vectorStudent v(n); for (int i 0; i n; i) { cin v[i].name v[i].score; v[i].id i; } sort(v.begin(), v.end(), [](const Student x, const Student y) { if (x.score ! y.score) return x.score y.score; // 第一关键字分数降序 if (x.name ! y.name) return x.name y.name; // 第二关键字姓名升序 return x.id y.id; // 第三关键字输入顺序 }); for (const auto s : v) cout s.name s.score \n; return 0; }三个关键字每一层都写!再返回比较结果这样任意两个元素之间只有一种确定关系满足严格弱序。假如把第一行写成if (x.score y.score) return true;分数相同时两个方向都返回真sort的行为就变成未定义。这个 bug 在小数据上不显形在几千条数据上直接崩属于典型的环境相关错误。输出用\n而不是endl是因为endl每次都强制刷新缓冲区数据量大时明显拖慢。题号段的数据量本来无所谓但这是个值得从第一题就养成的手感。4.5 日期与进制状态每次重算题目形态一给年月日输出这一天是本年的第几天。形态二给一个数和进制输出它在十进制下的值。日期题的核心不是循环是「月份天数表要跟着年份变」。写在循环外的month[2] 28会让所有闰年数据全错而且错误只出现在 2 月之后。#include iostream using namespace std; bool isLeap(int y) { return (y % 4 0 y % 100 ! 0) || (y % 400 0); } int main() { int month[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int y, m, d; while (cin y m d) { month[2] isLeap(y) ? 29 : 28; // 每次读入新日期都要重算别提到循环外 int days 0; for (int i 1; i m; i) days month[i]; // 累加前面整月 days d; // 加上当月天数 cout days endl; } return 0; }进制题的写法在 3.4 已经给过这里强调一个判断顺序先确认输入里有没有可能出现小写字母a~f表示 10~15有的话转换前先toupper。再确认进制范围超过 16 的进制不能只靠单个字符表示一位题目一般会避开但读题时要看到这句。5. 易错点五个最冤的失分现场与纠正手法5.1 输入输出类失分格式错和读不全错在哪输出里多打了一句「请输入」。这是刚上手的人最常见的错本地跑起来看着很友好提交直接 WA。判题机做的是逐字符比对你输出的每一个字符都会被算进答案。为什么错把控制台程序的习惯带进了判题环境。在线评测只认标准输出里的答案部分任何提示语、单位说明、多余标点都算错。怎么答对提交前把printf和cout从头到尾扫一遍只保留题目要求输出的内容。养成一个习惯本地测试时把输入输出重定向到文件对着文件看结果比在终端里看更容易发现多余字符。错在哪多组数据的输出之间空行处理反了。题目要求「每组之间空一行」很多人写成每组末尾加空行最后一组后面就多出一个空行。为什么错「组间」和「组后」在只有一组数据时表现一样两组以上才分得出来而样例往往只给一组。怎么答对用「第一组特殊处理」的写法先输出第一组之后每一组都在输出结果前先打一个换行。这样无论多少组末尾都不会多空行。5.2 数据类型与边界类失分溢出和越界错在哪累加用 int结果在测试点 7 变成负数。题号段里求阶乘、求幂和、求累加的题n 给到二三十就能顶穿 32 位。为什么错样例给的数据小本地算出来是对的误以为类型没问题。判题机的测试点专门卡边界。怎么答对读完题先粗算最大值再定类型超过 2×10⁹ 用long long超过 1.8×10¹⁹ 就说明要用高精度。输出格式串同步改成%lld。错在哪数组开得刚好等于题目上限。题目说「n 不超过 100」就开int a[100]然后循环写到a[100]。为什么错下标从 0 开始n 个数占的是 0 到 n-1但只要循环条件写成i n就会多写一位。这个越界在本地可能不崩只是把相邻变量改了。怎么答对数组统一按上限加 5 到 10 开循环条件统一写成i n。写完之后专门检查一遍所有出现的位置。5.3 逻辑顺序与初始化类失分清零和重算错在哪多组数据的累加器定义在循环外面。第一组结果对第二组开始翻倍。为什么错变量的作用域和生命周期没对齐。定义在外面的变量只初始化一次后面每组都在上一组的结果上继续加。怎么答对把所有「每组都要重新开始」的变量——累加器、计数器、标志位、临时数组——统统定义在循环体内部第一行。这条规则不需要理解照做就行。错在哪排序比较函数里用判等。小数据能过数据一多就运行时错误。为什么错比较函数不满足严格弱序sort内部的划分逻辑会越界。这个错误隐蔽性极强因为代码看上去完全符合直觉。怎么答对比较函数里所有判等一律用!最后一行再返回兜底比较。写完拿一组「全部元素相同」的数据自测能过基本就没问题。注意这五条失分里有四条和数据规模无关用样例根本测不出来。自测时务必自己造边界数据别只跑题目给的样例。6. 答题技巧机试现场的 40 分钟分配与提交自检清单进了考场题号段练出来的东西要以另一种方式用出来。基础题的正确策略不是「做出来」而是「快且一次过」。一道 AB 型题花十五分钟调试后面就没时间了。我自己的分配是这样的读题 3 分钟其中至少一半时间用来确认输入格式和输出格式把「几组数据、怎么终止、要不要空行、保留几位小数」这四个问题在纸上写清楚。写代码 10 分钟写完立刻用样例跑一遍。剩下时间造两组边界数据一组最小值或空输入一组刚好等于题目上限。全部通过再提交。提交前检查项具体看什么出问题的典型表现输入方式单组、多组、先给组数、读到标志结束样例过、提交只过第一组终止条件EOF、 1、! 0死循环超时或漏最后一组变量类型累加和、乘积、中间结果大测试点是负数数组大小是否按上限加余量循环是否而非本地正常提交运行错误初始化位置累加器是否在循环体内清零第二组开始结果翻倍输出格式行末空格、组间空行、小数位数、类型匹配答案数值对仍然 WA比较函数判等是否用!是否满足严格弱序小数据过大数据崩溃这张表我后来打印出来贴在显示器边上每次提交前从上往下扫一遍扫完再点提交。刚开始觉得繁琐两三天之后就变成条件反射了。还有一个押题方向的判断如果题库里出现了「多组输入 结构体排序 日期或进制」的组合题几乎可以肯定后面还有一道同类型的加强版。这类题在号段里是成组出现的做完一道就把模板代码留着下一道改两行就能用。真正拉开差距的不是会不会做是能不能在十分钟内把模板改对。从那以后我每次上机不管题目多简单都强制走一遍这张清单——先确认读入再确认类型最后确认输出。省下来的调试时间远比检查花掉的多。希望帮到你。本文还有配套的精品资源点击获取
