OJ 1000–1099题单：输入输出陷阱与基础算法模板-平芜编程栈

简介：面向准备杭电在线OJ入门至中阶题目的编程学习者，这套1000—1099题解代码包可直接用于对照练习、复盘算法思路与查漏补缺。压缩包共90个文件、约1.1MB，主体为62个cpp与16个c源码，另含少量VC6工程及调试产物（dsp、dsw、pdb、obj等），便于在旧版环境中打开或迁移编译。题目覆盖基础算法、数据结构、数学应用、模拟与逻辑推理等方向，代码均已调试通过，可帮助读者理解C/C++语法、指针与内存管理、排序查找、动态规划、图论等知识的实际落地。已有1840人学习，适合作为课后刷题答案参考、课程实验辅助或竞赛入门训练素材，也能从工程文件组织中了解早期C/C++项目的编译与调试方式。

1. 1000–1099 不是送分题：先看清这套题单到底在考什么

很多人打开这份 1000–1099 的 OJ 代码，第一反应是「一百道入门题，抄一遍就完事」。真到上机那天，最先翻车的偏偏是 1000 号那道 A+B——判题机不看思路，只逐字节比对标准输出，多一个空格、少一个换行就是 Wrong Answer。这套题单考的从来不是算法多花哨，而是三件事：能不能按题面要求把数据读干净，能不能在边界值上不漏判，能不能把一段模拟流程写得既不重也不漏。对应的场景很明确，程序设计课程机考、转专业与推免上机、复试现场编码，考的都是「一次写对」的稳定性。一百道题拆开看，背后只有六类模型；把这六类的模板默写到不用想，剩下的功夫全在输入输出对齐上。这份代码适合已经学过语法、却一上机就交七八次的人。

2. 输入输出格式：1089–1096 那八道 A+B 藏着的四类陷阱

题号段最前面那组 A+B 练习，是整套题单里最被低估的部分。它们的算法难度几乎为零，却是唯一一组专门用八道题反复折磨「输入输出格式」的题目。上机考试里因为格式丢的分，通常比因为算法不会丢的分还多，原因很直接：算法不会你当场就知道，格式错了你会一直以为自己写对了。这一章把四种终止方式、空行的位置、类型的取值范围和不定长读入这四件事拆开讲，每一件都配一道可以立刻敲进判题框的写法。

2.1 四种输入终止方式，先认出来再动手

题面里描述输入结构的那一两句话，比正文的算法描述重要得多。写代码之前先把这段读完，判断它属于哪一类：读到文件末尾为止、开头先给一个整数表示组数、每组数据以某个特殊值收尾、每行长度不定需要整行读入。这四类对应四种完全不同的主循环骨架，选错了后面全白写。

第一类是 EOF 终止，题面通常写「输入包含多组测试数据」。C 风格用scanf的返回值判断，C++ 风格用cin >>的隐式转换，两者都别写成while (scanf(...))。第二类是显式给组数，读一个 T 然后循环 T 次，注意 T 可能为 0。第三类是哨兵终止，读到某个约定值就停，这个值本身不产生任何输出。第四类是整行读入，常见于字符串题。

#include <cstdio> int main() { int a, b; // scanf 返回成功读入的变量个数，读到文件末尾返回 -1 // 写成 while (scanf("%d%d", &a, &b)) 会死循环：-1 在 C 里是真值 while (scanf("%d%d", &a, &b) == 2) { printf("%d\n", a + b); } return 0; }

这段代码的关键只有一处：== 2。返回值的语义是「成功赋值的变量个数」，两个%d都读到了才等于 2，中途遇到换行、空格会跳过继续等，遇到文件结束才返回 -1。同理，读单个整数时判断== 1，读double时用%lf并判断== 1。

哨兵型的写法差别在于判断时机，哨兵必须在输出之前拦掉：

int a, b; while (scanf("%d%d", &a, &b) == 2) { if (a == 0 && b == 0) break; // 哨兵一旦读入立刻退出，绝不能先输出再判断 printf("%d\n", a + b); }

如果题面给的是「输入 n，n 为 0 时结束」，而 n 本身还要参与计算，那就更不能先算再判。这类题最常见的翻车是把break写成continue，结果多输出一行0，判题机直接判错。

显式给组数的写法要用long long存累加结果，这一点在 2.3 节展开。另外提一句，有些题面写「第一行是整数 N，接下来 N 行」，但样例里 N 后面跟着一个空行，这时候用cin >>会自动跳过空白，用fgets就会读到一个空串，选哪种读法取决于你要不要保留行结构。

2.2 输出格式：空行到底加在哪一行

空行是这套题单里最容易反复提交的地方。题面常见三种表述：「每组输出占一行」「每组输出后跟一个空行」「两组输出之间有一个空行」。第一种最简单，printf("%d\n", ans)收工。后两种的差别在于最后一组之后要不要多留一行，这个必须看样例输出的最后一行是不是空的，别凭感觉。

稳妥的写法是显式区分「组间」和「组后」：

#include <cstdio> int main() { int T; scanf("%d", &T); for (int i = 0; i < T; ++i) { long long n, sum; scanf("%lld", &n); // n 接近 2^31 时 n * (n + 1) 早已溢出 int，必须用 long long sum = n * (n + 1) / 2; printf("%lld\n", sum); if (i != T - 1) printf("\n"); // 组间空行：最后一组不再补 } return 0; }

如果题面明确要求「每组输出后跟一个空行」，把条件判断删掉，无条件printf("\n")即可，最后会多出一个空行，这恰好是题目要的。判断依据永远是样例输出，不是你的直觉。还有一类变体是「Case #x: 结果」，注意冒号后面有一个空格，x从 1 开始，这些细节判题机一个都不放过。

行末空格是另一个隐形杀手。输出一串数字时，很多人写成「每个数后面跟一个空格」，最后一位后面就多了一个空格。正确做法是第一位不加分隔符、之后每位前面加：

for (int i = 0; i < n; ++i) { if (i) printf(" "); printf("%d", a[i]); } printf("\n");

提示：本地看不出行末空格，提交前用cat -A看一眼自己程序的输出，行尾多出来的空格会显示成可见字符。

2.3 类型与范围：什么时候 int 会悄悄溢出

这套题单里超过一半的错误提交和类型选择有关，而且它们不会报错，只会得到一个负数或者一个莫名其妙的小数字。判断方法很机械：把题面给出的数据范围抄下来，估算中间结果的最大值，超过 2×10⁹ 就换long long。

典型的坑是求和公式。n * (n + 1) / 2里，即使n本身只有 10⁵，中间乘积也可能到 10¹⁰，int直接爆掉。改成long long n之后整个表达式都在 64 位下计算，问题消失。如果n只声明成int而结果变量是long long，那要先转类型：(long long)n * (n + 1) / 2。

第二个坑是比较时的乘法。素数判定里写i * i <= n，i最大到 46340 时平方还在int范围内，但换到 64 位输入就危险了，写成(long long)i * i <= n一劳永逸。第三个坑是scanf的格式符和变量类型必须严格对应，long long配%lld，double配%lf，float配%f，写反了不会报错，只会读进一片垃圾，这类 bug 排查起来非常费时间。

2.4 真题演练：不定长整行的读法

题面给「每行若干个整数，个数不定」时，C 风格要先整行读进来再拆分，Python 则天然适合。下面两种写法都要求跳过可能的空行，因为样例文件末尾常常带一个空行，不跳过就会多输出一次。

import sys for line in sys.stdin: line = line.strip() if not line: # 空行直接跳过，否则 split() 返回空列表，后面解包会抛异常 continue nums = list(map(int, line.split())) print(sum(nums))

strip()去掉行尾换行和首尾空格，split()不传参数时按任意空白切分，连续空格也能正确分开。整段逻辑只有四行，但里面有两处是不能省的：strip和空行判断。C 风格对应的是fgets加strtok或sscanf逐段解析，代码量翻三倍，如果不是必须用 C，这类题用 Python 提交反而更快。

3. 数学与模拟：素数、进制、循环节、日期的四套固定打法

这一段的题目开始有一点「算法」的味道，但难度仍然停留在模板层面。它们的共同特征是有固定套路，见过一次就能套用，没见过就要现场推。上机考试时间紧，现场推公式的成功率很低，所以这四类模板值得背到能默写。每一类下面都给出可运行的完整写法，以及最常被忽略的那一行。

3.1 素数：从试除到筛法的两套模板

单个数判素用试除法，一段区间内批量判素用筛法，两者不能混用。试除法写成for (i = 2; i < n; ++i)是最常见的写法，也是超时的标准写法，数据量大一点就会超时。正确写法有三处优化：只试到根号、跳过偶数、先把小于 2 的情况摘出去。

bool isPrime(long long n) { if (n < 2) return false; // 0、1 和负数都不是素数，这一行最容易漏 if (n % 2 == 0) return n == 2; // 偶数里只有 2 是素数 for (long long i = 3; i * i <= n; i += 2) { if (n % i == 0) return false; } return true; }

i * i <= n比i <= sqrt(n)更好，一是省掉浮点开方的误差，二是循环条件里没有函数调用。i += 2把候选量减半。n < 2那一行如果不写，输入 1 会返回 true，这是这套题单里出现频率最高的错误答案之一。

批量判素用埃氏筛，注意内层循环从i * i起跳：

const int MAXN = 1000000; bool comp[MAXN + 1]; // comp[i] 为 true 表示 i 是合数 void sieve() { comp[0] = comp[1] = true; for (int i = 2; (long long)i * i <= MAXN; ++i) { if (comp[i]) continue; for (long long j = (long long)i * i; j <= MAXN; j += i) { comp[j] = true; // 从 i*i 起步，更小的倍数已经被更小的素数标记过 } } }

从i * i起步能省掉近一半的重复标记，这是筛法能不能在时限内跑完的关键。数组开成全局，一百万级别的bool放在栈上会直接崩。

3.2 进制转换与数位分离

进制转换的模板只有一个，理解「取余得低位、整除降一位」就不会写错。最容易错的地方是最后要整体翻转，因为取余的顺序是从低位到高位。

#include <string> #include <algorithm> std::string toBase(long long n, int base) { if (n == 0) return "0"; // 0 单独处理，否则返回空串 const char* digit = "0123456789ABCDEF"; bool neg = n < 0; if (neg) n = -n; std::string s; while (n > 0) { s += digit[n % base]; n /= base; } if (neg) s += '-'; std::reverse(s.begin(), s.end()); // 低位在前，必须翻转 return s; }

反向的转换（任意进制转十进制）用n = n * base + (c - '0')逐位累加，注意字母位要写c - 'A' + 10。数位分离是同一套思路的简化版，水仙花数、数根、各位求和都用它：

int digitSum(long long n) { int s = 0; while (n > 0) { s += n % 10; n /= 10; } return s; }

数根题里如果输入长度超过 19 位，long long装不下，必须用字符串读入，然后写s += c - '0'逐字符累加。这是类型选择影响解法的典型例子。

3.3 循环节：递推题超时的唯一解

递推题给出n高达 10⁸ 甚至 10⁹，一定是让你找循环节，不是让你真循环。判断依据很清晰：递推式只依赖前 k 项，每项取值范围有限，状态总数就是「取值范围的 k 次方」，超过这个数必然重复，周期不会超过它。

// 形如 f(1)=1, f(2)=1, f(n) = (A*f(n-1) + B*f(n-2)) % 7 // 每项取值只有 0..6 共 7 种，前两项组合共 49 种，周期不超过 49 int f[55]; f[1] = f[2] = 1; for (int i = 3; i <= 49; ++i) { f[i] = (A * f[i - 1] + B * f[i - 2]) % 7; } n = (n - 1) % 49 + 1; // 把 n 折到 1..49，n 可能是 1e8 printf("%d\n", f[n]);

这里有两处细节决定对错。一是周期长度取 49 而不是 50，写大了数组越界，写小了结果错位。二是(n - 1) % 49 + 1这个折叠公式，直接写n % 49会让n = 49折成 0，取到未初始化的位置。这类题在本地用小数据对拍一遍就能确认，把n从 1 跑到 200，和暴力递推的结果逐项比对，一致了再提交。

3.4 日期与日历模拟的三件事

日期题的复杂度全在闰年和月份天数上，套路固定：判闰年、取当月天数、累加。闰年规则写全(y % 4 == 0 && y % 100 != 0) || y % 400 == 0，只写y % 4 == 0会在整百年上出错。

#include <cstdio> bool isLeap(int y) { return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0); } int dayOfYear(int y, int m, int d) { int mdays[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; mdays[2] = isLeap(y) ? 29 : 28; // 用局部数组，改完不影响下一次调用 int s = d; for (int i = 1; i < m; ++i) s += mdays[i]; return s; }

月份表放在函数内部是刻意的。写成全局数组再在函数里改mdays[2] = 29，下一次调用遇到平年就忘了改回来，这种 bug 在多组输入的题目里会稳定复现，而且极难肉眼发现。日期题的第二个坑是跨年，如果题面要求「若干天后是哪一天」，要把天数一天一天推，别想着用公式一次算完。第三个坑是输出补零，2024-3-5和2024-03-05是两个不同答案，看样例确认。

4. 字符串与大数：读入、排序、进位这三关怎么过

字符串题在这套题单里占比不低，但真正让人反复提交的不是算法，是读入。C 和 C++ 混用输入函数时，缓冲区里残留的换行符会引发一连串看似玄学的错误。大数题则只有一道关：进位。把这两块处理好，这一段的题目基本一次过。

4.1 字符串读入：scanf、fgets、getline 的分工

scanf("%s", s)遇空白就停，读不了带空格的整行。fgets能读整行但会把换行符一起留下。getline干净利落但会和前面的cin >>打架。三者的适用场景必须分清。

#include <cstdio> #include <cstring> int main() { char s[1005]; int n; scanf("%d", &n); getchar(); // 吃掉整数后面残留的换行，否则 fgets 立刻读到空串 while (n-- && fgets(s, sizeof(s), stdin)) { s[strcspn(s, "\r\n")] = '\0'; // 掐掉行尾换行，判题机的行尾可能是 \r\n printf("%s\n", s); } return 0; }

strcspn(s, "\r\n")返回第一个\r或\n的下标，直接置\0就把行尾清干净了，比手写循环短且不容易漏。getchar()那一行是整段代码的关键，没有它，第一次fgets会读到一个只有换行的字符串，后面全部错位一位，现象是「每个输出都比答案多一个空行」，很多人会误以为是输出格式问题，实际上是读入问题。

C++ 里的等价写法是cin >> n; cin.ignore();然后getline(cin, line)。ignore()不传参数默认跳过一个字符，正好是那个换行。Python 只要用sys.stdin.readline().rstrip('\n')，不存在缓冲区残留的问题。

4.2 排序：字典序和长度序差在哪

同一个字符串数组，按字典序排和按长度排的结果完全不同，题面写「按字典序从小到大」还是「按长度从短到长」必须先看清楚。字典序是逐位比较字符编码，只有公共前缀完全相同时长度才起作用；长度序是先比长度再比内容。

#include <algorithm> #include <string> #include <vector> // 字典序：逐位比 ASCII，短串是长串前缀时短串更小 std::sort(v.begin(), v.end()); // 长度优先，长度相同再按字典序 std::sort(v.begin(), v.end(), [](const std::string& a, const std::string& b) { if (a.size() != b.size()) return a.size() < b.size(); return a < b; });

std::string的<已经是字典序，不需要自己写比较函数，这是最常见的过度编码。倒序用std::greater<std::string>()或者排完再reverse。如果题目要求「按出现次数排序，次数相同按字典序」，就把比较函数写成两级判断，别写成冒泡，数据量一大必超时。

4.3 大数加法：那道 A+B 的进位写法

题面给的数超过long long范围时，只能按字符串处理。核心逻辑和小学竖式一样：从低位往高位逐位相加，进位单独存，最高位进位单独补一位。

#include <string> #include <algorithm> // 两个非负十进制大数相加 std::string addBig(const std::string& a, const std::string& b) { std::string r; int i = (int)a.size() - 1, j = (int)b.size() - 1, carry = 0; while (i >= 0 || j >= 0 || carry) { // carry 也要参与循环条件，否则末位进位丢失 int s = carry; if (i >= 0) s += a[i--] - '0'; if (j >= 0) s += b[j--] - '0'; r += char('0' + s % 10); carry = s / 10; } std::reverse(r.begin(), r.end()); return r; }

while条件里的carry是最容易漏的一处，漏掉就会在999 + 1这种用例上得到000。其次要注意输入可能存在前导零，输出前用while (r.size() > 1 && r[0] == '0') r.erase(r.begin());清一遍。如果两个数都可能是负数，先判符号再决定做加法还是减法，减法还要额外处理大小比较，别硬塞进同一个函数。

4.4 字符统计与大小写

统计类题目看着简单，却容易在字符范围上出错。用cctype里的isalpha、isdigit、toupper时，传进去的必须是unsigned char转成的int，否则遇到高位字节会返回未定义结果。

#include <cctype> int cnt[26] = {0}; for (const char* p = s; *p; ++p) { unsigned char c = (unsigned char)*p; // 先转无符号，避免负值传入 ctype 函数 if (std::isalpha(c)) { cnt[std::toupper(c) - 'A']++; // 大小写合并统计 } }

如果题目要求区分大小写，就用两个数组或者下标加 26。toupper返回的是int，减'A'之后再当下标用是安全的，因为已经保证是字母。数标点的题要注意，isspace认的是空格、制表、换行三类，中文标点不在此列，别想当然。

5. 失分点：五个让提交次数翻倍的错法

下面五条是从这套题单里挑出来的、出现频率最高且最容易自我说服「我写得没问题」的错误。每一条都按「错在哪、为什么错、怎么答对」拆开，对着自己的历史提交逐条核一遍，通常能找出三成以上的错误提交。

5.1 漏判 scanf 返回值，读入垃圾或死循环

错在哪：主循环写成while (scanf("%d", &n))或者干脆while (1) { scanf(...); ... }，靠一个内部break退出。

为什么错：scanf在文件结束时返回 -1，而 -1 在 C 里是真值，条件永远成立，循环停不下来。如果判题机限制了输出大小，会判 Output Limit Exceeded；没限制就是 Time Limit Exceeded。这两种结果看起来和「读入」毫无关系，所以很多人往算法上找原因。

怎么答对：把所有scanf返回值都拿来做循环条件，格式串里有几个转换符就判断等于几。while (scanf("%d%d", &a, &b) == 2)、while (scanf("%d", &n) == 1)。用cin的直接写while (cin >> a >> b)，istream的布尔转换会正确处理 EOF。改完这个问题，超时投诉能少一大半。

5.2 累加变量用 int，答案莫名其妙变负

错在哪：int sum = 0;然后累加一百万个不超过 10⁶ 的数。

为什么错：int上限约 2.1×10⁹，一百万个 10⁶ 加起来是 10¹²，早已溢出。溢出后的结果是负数或者一个随机的小数字，判题机只会告诉你 Wrong Answer，不告诉你哪一位错了。

怎么答对：看到累加、连乘、组合数、求和公式，先算一遍量级。超过 10⁹ 一律long long，格式符跟着改成%lld。中间表达式也要检查：(long long)n * (n + 1) / 2和n * (n + 1) / 2是两回事，后者在n是int时先按int算完再转，转的时候已经晚了。养成习惯：求和变量永远long long，成本只是一个字母。

5.3 素数判定里漏掉 n 小于 2 的情况

错在哪：函数开头直接进循环，for (i = 2; i * i <= n; ++i)。

为什么错：当n = 0或n = 1时循环体一次都不执行，函数返回 true，把 0 和 1 当成了素数。测试数据里几乎一定有这两个值，因为它们正是边界。

怎么答对：函数第一行写if (n < 2) return false;，第二行处理偶数if (n % 2 == 0) return n == 2;。筛法的初始化同理，comp[0] = comp[1] = true;不能省。这类「边界单独摘出来」的写法适用于所有判定型函数，值得当成条件反射。

5.4 混用 scanf 和整行读入，结果整体错位一行

错在哪：先用scanf("%d", &n)读组数，紧接着gets(s)或getline(cin, s)读第一行字符串。

为什么错：scanf读到整数就停，后面的换行符留在缓冲区里，第一次整行读入读到的是那个换行，得到一个空串。之后每一次读入都提前一行，输出跟着整体错位，现象看起来像「少了第一组数据」。

怎么答对：读完数字后立刻清掉换行，C 用getchar()，C++ 用cin.ignore()。整行读入统一用fgets或getline，不要碰gets，它在新的标准里已经被移除，不少判题机直接编译失败。清完之后再用 4.1 节里的strcspn去掉行尾换行，两个动作分开做，逻辑才清楚。

5.5 循环节的周期长度和取模公式写错

错在哪：数组开 50，循环到 50，然后n = n % 50。

为什么错：前两项组合只有 49 种状态，周期最多 49，写到 50 会读到没有赋过值的f[50]。而n % 50在n = 50时得 0，取到的是f[0]，同样是未初始化位置。两处错误叠加，小数据能过、大数据就错，很难定位。

怎么答对：周期长度按「取值个数 ^ 依赖项数」算，模 7 且依赖两项就是 49，数组开到 55 留余量，循环到 49 为止。折叠公式统一写成(n - 1) % 周期 + 1，把下标映射到 1 起始的合法区间。写完拿n从 1 跑到 100 和暴力递推对拍，一致再提交，这一步花不了两分钟。

6. 上机答题流程：一道题 5 分钟内该走完的四步

拿到题目先别敲键盘，用一分钟把题面里描述输入输出的那几句话单独读一遍，判断属于四类终止方式里的哪一类，再看数据范围决定用int还是long long。这一步做完，脑子里应该已经有一个主循环骨架了。第二分钟写核心逻辑，只写函数，不写输出格式。第三分钟补输入输出，把Case #、空行、行末空格一次性写对。第四分钟用题面样例跑一遍，再用自己构造的三个边界用例跑一遍：最小值、最大值、退化情况。第五分钟检查有没有漏判返回值、有没有数组越界。

下面这张表是这套题单里出现频率最高的几类模型，以及对应的首选写法和提交前必查项，可以照着背。

题面特征	首选模板	提交前必查
多组数据，无组数	`while (scanf(...) == k)`	返回值个数是否等于转换符个数
先给组数 T	`for (i = 0; i < T; ++i)`	组间空行是否多留/少留
每组以 0 0 结束	读入后先判哨兵再输出	`break`有没有写成`continue`
求区间内素数个数	埃氏筛，内层从`i*i`起	数组是否开成全局、是否够大
递推 + n 很大	找周期，`(n-1)%T+1`	周期长度与数组边界
数字长度超过 19 位	字符串大数运算	末位进位、前导零
整行字符串	`fgets`+`strcspn`	前面是否残留换行符
按规则排序	`std::sort`+ 比较函数	字典序还是长度序