东华oj刷题记录我本来只打算在自己的笔记里写两句话就翻篇。结果第66到第70题这一批做完之后我回头一看发现几乎每道题都让我多花了一些“不该花的功夫”而这些功夫其实都可以靠读题习惯和几个固定模板省下来。所以干脆单独整理一篇既是给自己的复盘也顺手分享给正在冲东华oj基础题阶段的同学。这篇内容适合三类人看正在刷东华oj基础题的初学者、想快速复习字符串/日期/矩阵/递归/DP这些经典模板的选手、以及每次写完代码总在“Presentation Error”和“答案错误”之间反复横跳的倒霉蛋。接下来我按自己实际做题的顺序来写先讲整体印象再把踩坑细节和模板代码一份一份列出来。1. 这批题给我的整体印象考点很常规陷阱藏在细节里1.1 五道题的基本盘把第66到第70题放在一起看我有一个强烈的感受它们不是上来就考难题而是在“基础算法”和“工程细节”之间拿捏平衡。我当时看到的题目大致可以归成下面这几类题号题目给我的感觉主要考点复杂度要求66给一段文本统计里面不同字符的个数字符处理、哈希思想O(n) 即可67给两个日期求它们之间隔了多少天闰年、月份表、累加天数不宜逐日模拟太久68往一个矩阵里按某种规律填数二维数组、方向数组O(n^2) 正常69递归问题类似汉诺塔或辗转相除那一类递归出口、递推关系递归深度要可控70动态规划入门类似背包或最长上升子序列状态定义、循环顺序1000规模下O(n^2)可接受我不把原题原文整段贴进来因为OJ题面可能在不同学期有调整但核心套路是稳定的。你只要看到题目描述里出现“不同字符”“日期”“矩阵”“递归”“动态规划”这几个关键词基本就能对号入座。不同学校的题库或同题库不同批次可能题号对应关系有变化但本文里的思路和模板照样能直接用。在往下看细节之前我先交代一下我自己的刷题背景我是以“考试和找工作笔试”为目标来刷东华oj的不是奔着ACM拿牌去的。所以整套思路都比较务实——不追求最优解追求“写得快、不容易错、好调试”。这个前提决定了下面很多经验看起来比较“土”但真的管用。1.2 我做题之前的三步读题法我在这批题上浪费过几次时间后来总结出一个读题顺序第一遍只看输入格式描述确认是单组数据、多组数据还是读到文件结尾为止第二遍只看数据范围判断目标复杂度大概要写成什么样第三遍才看样例把输出格式里到底几个空格、要不要换行看清楚。这个顺序帮我省掉了很多“读题没读懂”的时间。尤其是数据范围比如一道矩阵题如果写明n100那O(n^3)都可能过如果写明n10^5那基本可以排除暴力O(n^2)的思路。东华oj的题面里这个信息通常写得很明确别跳过。一个常见的误区是一上来就看样例样例看懂了就觉得自己懂了。结果样例输出确实能过但题目里那句“若输入为0则结束”被无视了提交就挂。我现在宁愿多花两分钟把题面第一段和最后一段读干净也不愿意在提交后为了一个“答案错误”反复查十分钟。1.3 这些题有个共同点样例都对提交就挂第66到第70这个区间很有趣题目样例大多很友好让你在本地随便跑都能得到期望输出。但提交之后常见的错误是“答案错误”而不是“编译错误”或“运行超时”说明不是语法不行而是边界没处理。比如字符统计题样例字符串里没有换行你统计出来的结果自然是对的但OJ实际测试数据里可能有空行、可能有行尾空格。日期题的样例年份都在2000年前后int完全够用但实际数据可能把年份拉到了很远。矩阵题样例规模都是3×3或4×4肉眼就能看出形状但n1时你的方向数组可能直接就越界了。这些细节不会在样例里露出来只在裁判器的隐藏数据里等着。所以刷这批题的关键不是把算法背熟而是把“处理不确定情况”的方法练熟。后面两章我会专门讲这批题里最容易挂的细节。2. 真正浪费我时间的地方输入方式和变量类型2.1 先搞清楚OJ到底给你几组数据我记得很清楚第67题第一次做的时候我以为只有一组日期写完提交直接“答案错误”。后来回看题面才发现人家写的是“多组测试数据”第一行给个T后面每组两行。这个教训让我之后每道题都先看输入模式。在线题库里常见的有三种输入模式我把对应的写法都放进来了。模式一第一行告诉你一共有T组测试数据int T; scanf(%d, T); while (T--) { // 处理一组 }模式二不知道几组一直读到文件结尾while (scanf(%d%d, n, m) ! EOF) { // 处理一组 }模式三题目明确说“输入以0 0结束”while (scanf(%d%d, n, m) 2 (n ! 0 || m ! 0)) { // 处理一组 }这三种模式只要写错结果就是要么只处理第一组、要么死循环、要么把结束标记也当成有效输入。我推荐一个习惯拿到题先把输入描述里第一句话圈出来看有没有“多组测试数据”这样的提示。如果是在网页上刷题那就把题目拖到文本末段通常那里会写“输入包含多个测试用例以EOF结束”。另外要注意有些题的“0 0结束”是同时要求两个都是0才结束有些题则只要n为0就算结束还有的是“0 0 0”三个数。别想当然拿题目原话作准。2.2 本地正常的代码为什么提交就不行一个经常出问题的地方是输出提示信息。比如你在本地为了调试写了printf(请输入n: ); scanf(%d, n);本地当然没问题因为你是人眼看输入但OJ是拿标准输入喂给你的程序然后只比较标准输出。你多打印了“请输入n:”这一行裁判器会认为这是你的输出内容的一部分几乎必然判“答案错误”。这不是逻辑问题而是调试输出没清干净。所以提交之前我会用一行注释把所有调试输出全部关掉或者在编译时把调试代码包在#ifdef DEBUG里。这个习惯养成之后能省掉很多无意义的失败提交。另外还有一个本地和OJ行为不一致的点本地编译器可能默认把所有未初始化的局部变量清零而OJ的编译器不一定。比如你声明了int cnt[256];但没有memset或{0}初始化本地跑起来可能碰巧全是0提交就随机错。这类问题最坑表现形式也是“答案错误”而且时对时不对。处理办法很简单数组一律初始化。2.3 日期题必须用对变量类型第67题是典型的日期差计算。很多人一开始会写“从date1逐日加到date2”这种做法本身没错但如果年份跨度大、还要求跨过多个闰年逐日循环虽然能过但代码又长又容易漏。更稳的做法是先把日期转换成一个绝对数值再求差。这里有个很容易被忽略的细节日期累加时千万不要小看年份数量。比如要处理公元1年到公元3000年就算只算天数累加结果也在百万级别int其实扛得住但如果题目要求继续换算成秒、毫秒或者把结束年份放宽到很大int就有风险。我用一个统一的模板直接用long long存天数省得每次都要重新推一遍会不会溢出。int isLeap(int y) { return (y % 4 0 y % 100 ! 0) || (y % 400 0); } int daysOfMonth(int y, int m) { int days[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (m 2 isLeap(y)) return 29; return days[m]; } long long dateToInt(int y, int m, int d) { long long sum 0; for (int i 1; i y; i) { sum isLeap(i) ? 366 : 365; } for (int i 1; i m; i) { sum daysOfMonth(y, i); } sum d; return sum; }两个日期之间的天数差就是long long diff dateToInt(y2, m2, d2) - dateToInt(y1, m1, d1); if (diff 0) diff -diff;有些题会要求“头尾都算”这时候要diff 1有些题只要求相隔天数直接用diff。我每次写完都会对比样例里的结果确认这个1要不要加。别小看这个差异一个1就能让整道题从AC变WA。2.4 行尾空格和换行也算输出的一部分第68题给矩阵按某种规律填数输出要求通常是每一行数字之间用一个空格隔开最后一列后面不能有空格。很多第一次写的人会直接在循环里写printf(%d , a[i][j]);结果每一行末尾都多了一个空格。OJ的裁判器对这种情况一般不会判“答案错误”而是判“Presentation Error”大概意思是你答案内容对但输出格式不太对。东华oj对格式同样有严格检查PE本身也算没通过。我的做法是要么把每行先拼成一个字符串再输出要么用“第一个元素前不加空格其余元素前加空格”的模式for (int j 1; j n; j) { if (j 1) printf( ); printf(%d, a[i][j]); } printf(\n);这样最后一个元素后面不会多出空格。这个小模板我后来在几乎所有二维数组输出里都用上了顺手也解决了“换行是否多余”的焦虑。3. 五道题可以直接复用的代码模板3.1 字符统计模板第66题如果题目说“统计一段文字里不同字符的个数”最简单的做法是开一个大小为256的计数数组。因为C语言里的char本质是一个整数大多数时候我们只需要把字符的ASCII值当作数组下标。#include stdio.h #include string.h int main() { char s[1005]; while (fgets(s, sizeof(s), stdin)) { int cnt[256] {0}; int len strlen(s); // 去掉fgets读进来的换行符 if (len 0 s[len - 1] \n) { s[len - 1] \0; len--; } for (int i 0; i len; i) { cnt[(unsigned char)s[i]]; } int ans 0; for (int i 0; i 256; i) { if (cnt[i] 0) ans; } printf(%d\n, ans); } return 0; }这里有几个细节容易翻车一是fgets会把换行符读进字符串如果直接统计换行符会被当成一个“字符”计入结果二是有些题问的是“不同字符”有些题问的却是“出现次数最多的字符”这俩一个用计数器大于0一个还要再遍历找最大值三是遇到空格时不能简单跳过得看题面是否把空格计入。如果题目允许用C那用mapchar, int会更直观但C的数组计数法在比赛里更快所以我个人还是推荐这种写法。另外要注意如果字符串里可能有中文字符或其他多字节编码数组计数法就不适用了好在OJ的字符统计题一般只涉及ASCII字符。3.2 日期工具模板第67题上面第2.3节已经给了isLeap、daysOfMonth、dateToInt三个函数组合起来基本能解决所有日期类问题。我再补一个经常用到的变体判断某天是星期几。只要知道一个基准日期是星期几就能通过天数差对7取模算出来。比如公元1年1月1日是星期一这个基准在不少题目里都会出现但每个题给的基准可能不一样所以关键还是先把“天数差”算对。日期题还有一个常见陷阱闰年判断公式很多人只写了y % 4 0忘了“整百年必须被400整除”这个条件。东华oj里出现过类似“1899年不是闰年2000年是闰年”的细节所以别把公式写漏。另一个容易错的地方是月份天数表2月不能单独写死成28天要看年份决定是否改成29天。还有一个细节我要特别提醒很多日期题的数据范围会写到“年份在1到10000之间”这种情况下dateToInt里的for循环要从1累加到当前年份虽然看起来循环很长但实际也就是几万次运算性能完全不是问题。怕就怕你图省事直接用某个公式跳过累加结果公式记错反而出错。累加法反而是这类题里最稳的写法。3.3 矩阵填充的方向增量法第68题矩阵填数题不管是螺旋矩阵、蛇形矩阵还是回字形矩阵都可以用同一个核心思路维护当前坐标(x, y)和当前方向dir每次先按方向尝试走一步如果走出去或者撞到已填过的格子就右转方向加1再对4取模然后继续走。以螺旋矩阵为例#include stdio.h #include string.h int a[105][105]; int dx[4] {0, 1, 0, -1}; int dy[4] {1, 0, -1,
东华oj刷题记录我本来只打算在自己的笔记里写两句话就翻篇。结果第66到第70题这一批做完之后我回头一看发现几乎每道题都让我多花了一些“不该花的功夫”而这些功夫其实都可以靠读题习惯和几个固定模板省下来。所以干脆单独整理一篇既是给自己的复盘也顺手分享给正在冲东华oj基础题阶段的同学。这篇内容适合三类人看正在刷东华oj基础题的初学者、想快速复习字符串/日期/矩阵/递归/DP这些经典模板的选手、以及每次写完代码总在“Presentation Error”和“答案错误”之间反复横跳的倒霉蛋。接下来我按自己实际做题的顺序来写先讲整体印象再把踩坑细节和模板代码一份一份列出来。1. 这批题给我的整体印象考点很常规陷阱藏在细节里1.1 五道题的基本盘把第66到第70题放在一起看我有一个强烈的感受它们不是上来就考难题而是在“基础算法”和“工程细节”之间拿捏平衡。我当时看到的题目大致可以归成下面这几类题号题目给我的感觉主要考点复杂度要求66给一段文本统计里面不同字符的个数字符处理、哈希思想O(n) 即可67给两个日期求它们之间隔了多少天闰年、月份表、累加天数不宜逐日模拟太久68往一个矩阵里按某种规律填数二维数组、方向数组O(n^2) 正常69递归问题类似汉诺塔或辗转相除那一类递归出口、递推关系递归深度要可控70动态规划入门类似背包或最长上升子序列状态定义、循环顺序1000规模下O(n^2)可接受我不把原题原文整段贴进来因为OJ题面可能在不同学期有调整但核心套路是稳定的。你只要看到题目描述里出现“不同字符”“日期”“矩阵”“递归”“动态规划”这几个关键词基本就能对号入座。不同学校的题库或同题库不同批次可能题号对应关系有变化但本文里的思路和模板照样能直接用。在往下看细节之前我先交代一下我自己的刷题背景我是以“考试和找工作笔试”为目标来刷东华oj的不是奔着ACM拿牌去的。所以整套思路都比较务实——不追求最优解追求“写得快、不容易错、好调试”。这个前提决定了下面很多经验看起来比较“土”但真的管用。1.2 我做题之前的三步读题法我在这批题上浪费过几次时间后来总结出一个读题顺序第一遍只看输入格式描述确认是单组数据、多组数据还是读到文件结尾为止第二遍只看数据范围判断目标复杂度大概要写成什么样第三遍才看样例把输出格式里到底几个空格、要不要换行看清楚。这个顺序帮我省掉了很多“读题没读懂”的时间。尤其是数据范围比如一道矩阵题如果写明n100那O(n^3)都可能过如果写明n10^5那基本可以排除暴力O(n^2)的思路。东华oj的题面里这个信息通常写得很明确别跳过。一个常见的误区是一上来就看样例样例看懂了就觉得自己懂了。结果样例输出确实能过但题目里那句“若输入为0则结束”被无视了提交就挂。我现在宁愿多花两分钟把题面第一段和最后一段读干净也不愿意在提交后为了一个“答案错误”反复查十分钟。1.3 这些题有个共同点样例都对提交就挂第66到第70这个区间很有趣题目样例大多很友好让你在本地随便跑都能得到期望输出。但提交之后常见的错误是“答案错误”而不是“编译错误”或“运行超时”说明不是语法不行而是边界没处理。比如字符统计题样例字符串里没有换行你统计出来的结果自然是对的但OJ实际测试数据里可能有空行、可能有行尾空格。日期题的样例年份都在2000年前后int完全够用但实际数据可能把年份拉到了很远。矩阵题样例规模都是3×3或4×4肉眼就能看出形状但n1时你的方向数组可能直接就越界了。这些细节不会在样例里露出来只在裁判器的隐藏数据里等着。所以刷这批题的关键不是把算法背熟而是把“处理不确定情况”的方法练熟。后面两章我会专门讲这批题里最容易挂的细节。2. 真正浪费我时间的地方输入方式和变量类型2.1 先搞清楚OJ到底给你几组数据我记得很清楚第67题第一次做的时候我以为只有一组日期写完提交直接“答案错误”。后来回看题面才发现人家写的是“多组测试数据”第一行给个T后面每组两行。这个教训让我之后每道题都先看输入模式。在线题库里常见的有三种输入模式我把对应的写法都放进来了。模式一第一行告诉你一共有T组测试数据int T; scanf(%d, T); while (T--) { // 处理一组 }模式二不知道几组一直读到文件结尾while (scanf(%d%d, n, m) ! EOF) { // 处理一组 }模式三题目明确说“输入以0 0结束”while (scanf(%d%d, n, m) 2 (n ! 0 || m ! 0)) { // 处理一组 }这三种模式只要写错结果就是要么只处理第一组、要么死循环、要么把结束标记也当成有效输入。我推荐一个习惯拿到题先把输入描述里第一句话圈出来看有没有“多组测试数据”这样的提示。如果是在网页上刷题那就把题目拖到文本末段通常那里会写“输入包含多个测试用例以EOF结束”。另外要注意有些题的“0 0结束”是同时要求两个都是0才结束有些题则只要n为0就算结束还有的是“0 0 0”三个数。别想当然拿题目原话作准。2.2 本地正常的代码为什么提交就不行一个经常出问题的地方是输出提示信息。比如你在本地为了调试写了printf(请输入n: ); scanf(%d, n);本地当然没问题因为你是人眼看输入但OJ是拿标准输入喂给你的程序然后只比较标准输出。你多打印了“请输入n:”这一行裁判器会认为这是你的输出内容的一部分几乎必然判“答案错误”。这不是逻辑问题而是调试输出没清干净。所以提交之前我会用一行注释把所有调试输出全部关掉或者在编译时把调试代码包在#ifdef DEBUG里。这个习惯养成之后能省掉很多无意义的失败提交。另外还有一个本地和OJ行为不一致的点本地编译器可能默认把所有未初始化的局部变量清零而OJ的编译器不一定。比如你声明了int cnt[256];但没有memset或{0}初始化本地跑起来可能碰巧全是0提交就随机错。这类问题最坑表现形式也是“答案错误”而且时对时不对。处理办法很简单数组一律初始化。2.3 日期题必须用对变量类型第67题是典型的日期差计算。很多人一开始会写“从date1逐日加到date2”这种做法本身没错但如果年份跨度大、还要求跨过多个闰年逐日循环虽然能过但代码又长又容易漏。更稳的做法是先把日期转换成一个绝对数值再求差。这里有个很容易被忽略的细节日期累加时千万不要小看年份数量。比如要处理公元1年到公元3000年就算只算天数累加结果也在百万级别int其实扛得住但如果题目要求继续换算成秒、毫秒或者把结束年份放宽到很大int就有风险。我用一个统一的模板直接用long long存天数省得每次都要重新推一遍会不会溢出。int isLeap(int y) { return (y % 4 0 y % 100 ! 0) || (y % 400 0); } int daysOfMonth(int y, int m) { int days[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (m 2 isLeap(y)) return 29; return days[m]; } long long dateToInt(int y, int m, int d) { long long sum 0; for (int i 1; i y; i) { sum isLeap(i) ? 366 : 365; } for (int i 1; i m; i) { sum daysOfMonth(y, i); } sum d; return sum; }两个日期之间的天数差就是long long diff dateToInt(y2, m2, d2) - dateToInt(y1, m1, d1); if (diff 0) diff -diff;有些题会要求“头尾都算”这时候要diff 1有些题只要求相隔天数直接用diff。我每次写完都会对比样例里的结果确认这个1要不要加。别小看这个差异一个1就能让整道题从AC变WA。2.4 行尾空格和换行也算输出的一部分第68题给矩阵按某种规律填数输出要求通常是每一行数字之间用一个空格隔开最后一列后面不能有空格。很多第一次写的人会直接在循环里写printf(%d , a[i][j]);结果每一行末尾都多了一个空格。OJ的裁判器对这种情况一般不会判“答案错误”而是判“Presentation Error”大概意思是你答案内容对但输出格式不太对。东华oj对格式同样有严格检查PE本身也算没通过。我的做法是要么把每行先拼成一个字符串再输出要么用“第一个元素前不加空格其余元素前加空格”的模式for (int j 1; j n; j) { if (j 1) printf( ); printf(%d, a[i][j]); } printf(\n);这样最后一个元素后面不会多出空格。这个小模板我后来在几乎所有二维数组输出里都用上了顺手也解决了“换行是否多余”的焦虑。3. 五道题可以直接复用的代码模板3.1 字符统计模板第66题如果题目说“统计一段文字里不同字符的个数”最简单的做法是开一个大小为256的计数数组。因为C语言里的char本质是一个整数大多数时候我们只需要把字符的ASCII值当作数组下标。#include stdio.h #include string.h int main() { char s[1005]; while (fgets(s, sizeof(s), stdin)) { int cnt[256] {0}; int len strlen(s); // 去掉fgets读进来的换行符 if (len 0 s[len - 1] \n) { s[len - 1] \0; len--; } for (int i 0; i len; i) { cnt[(unsigned char)s[i]]; } int ans 0; for (int i 0; i 256; i) { if (cnt[i] 0) ans; } printf(%d\n, ans); } return 0; }这里有几个细节容易翻车一是fgets会把换行符读进字符串如果直接统计换行符会被当成一个“字符”计入结果二是有些题问的是“不同字符”有些题问的却是“出现次数最多的字符”这俩一个用计数器大于0一个还要再遍历找最大值三是遇到空格时不能简单跳过得看题面是否把空格计入。如果题目允许用C那用mapchar, int会更直观但C的数组计数法在比赛里更快所以我个人还是推荐这种写法。另外要注意如果字符串里可能有中文字符或其他多字节编码数组计数法就不适用了好在OJ的字符统计题一般只涉及ASCII字符。3.2 日期工具模板第67题上面第2.3节已经给了isLeap、daysOfMonth、dateToInt三个函数组合起来基本能解决所有日期类问题。我再补一个经常用到的变体判断某天是星期几。只要知道一个基准日期是星期几就能通过天数差对7取模算出来。比如公元1年1月1日是星期一这个基准在不少题目里都会出现但每个题给的基准可能不一样所以关键还是先把“天数差”算对。日期题还有一个常见陷阱闰年判断公式很多人只写了y % 4 0忘了“整百年必须被400整除”这个条件。东华oj里出现过类似“1899年不是闰年2000年是闰年”的细节所以别把公式写漏。另一个容易错的地方是月份天数表2月不能单独写死成28天要看年份决定是否改成29天。还有一个细节我要特别提醒很多日期题的数据范围会写到“年份在1到10000之间”这种情况下dateToInt里的for循环要从1累加到当前年份虽然看起来循环很长但实际也就是几万次运算性能完全不是问题。怕就怕你图省事直接用某个公式跳过累加结果公式记错反而出错。累加法反而是这类题里最稳的写法。3.3 矩阵填充的方向增量法第68题矩阵填数题不管是螺旋矩阵、蛇形矩阵还是回字形矩阵都可以用同一个核心思路维护当前坐标(x, y)和当前方向dir每次先按方向尝试走一步如果走出去或者撞到已填过的格子就右转方向加1再对4取模然后继续走。以螺旋矩阵为例#include stdio.h #include string.h int a[105][105]; int dx[4] {0, 1, 0, -1}; int dy[4] {1, 0, -1,
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
