OJ刷题这件事我是从一份网上的入门清单开始的。断断续续刷了六天从一开始连输入输出格式都搞不明白到现在能静下心把一道题从读题到AC完整走下来中间踩过的坑比想象中多得多。这篇文章就是我Day6的学习笔记复盘记录前六天里验证过的学习方法、实际踩过的坑以及一套可以直接照着上手的刷题流程。如果你也刚开始在OJ平台刷题或者刷了一两周还在原地打转这篇应该对你有用。第六天是个很微妙的时间点新鲜感消退了算法能力还没形成质变最容易在这个阶段放弃。但恰恰是这几天把“提交代码→看评测结果→定位问题→再提交”的循环跑顺了后面刷任何题都会轻松很多。这篇笔记不罗列流水账只讲真正影响刷题效率的几件事从平台操作、输入输出、数据范围判断到一道经典贪心题的完整拆解再到WA之后的排查套路希望对你有参考价值。1. 前六天到底在做什么学习节奏与阶段复盘1.1 Day6这个微妙节点意味着什么我第一天做的事情现在回头看相当“原始”注册账号、逛题目列表、挑了一道标着“入门”的水题结果连编译错误都没绕过去。第一天到第三天基本是在跟OJ平台的规则搏斗——怎么提交、评测状态长什么样、为什么本地运行正常却一直报错。这个阶段谈不上算法更多是熟悉一套新的反馈系统。到了第四五天开始能顺着题目给的样例把代码跑通但换个测试数据就原形毕露最典型的表现就是“样例过了提交WA”。第六天最大的变化是我终于肯在写代码之前先把题目在纸上理一遍再动手。这个转变很关键它意味着刷题开始从“写代码”转变为“解决问题”前者靠手感后者靠逻辑。如果你正处在这个阶段我想说前几天的混乱是正常的。OJ刷题本质上是一项需要“人机互相适应”的技能你得先习惯机器评判的确定性——它不会因为你写得辛苦就网开一面只看结果对不对。接受这个逻辑心态会稳很多。1.2 从裸写代码到读懂评测结果前端时间我统计了六天里遇到的评测反馈最常见的几类分别是编译错误CE、答案错误WA、运行超时TLE、运行错误RE当然还有最想看到的正确AC。第一天看到WA心里会咯噔一下三天之后再看WA第一反应是“好开始排错”这个心态转变实际就是熟练度提升的信号。我总结出来的一条经验是第一周最该练的不是算法技巧而是读懂反馈并用反馈修正代码的循环能力。具体来说就是把每次提交变成一次信息收集CE告诉你语法或编译环境有问题RE提示你数组越界或非法访问TLE在暗示算法复杂度太高WA则说明逻辑和题目要求之间有偏差。每种反馈对应不同的排查方向这个映射关系我放在后面第4节详细拆这里先记住一个结论评测结果不是宣判是调试信息。给自己定一个简单目标也有帮助前六天不求多每天AC两到三道题就够了。我见过不少人一上来就给自己安排一天十道结果第三天就放弃了。频率比数量重要保持每天碰题的节奏比周末狂刷十小时划算得多。2. 核心细节解析与实操要点输入输出、数据范围与算法选择2.1 为什么OJ的输入输出格式是第一个坑对刚接触OJ的人来说输入输出格式往往是第一道隐形的墙。本地写程序数据是自己给的OJ平台上数据是评测系统喂进来的程序必须按题目要求的格式读入并输出多一个空格、少一个换行可能直接判WA甚至PE格式错误。以最常见的“多组测试数据”为例题目可能完全不告诉你有多少组而是要求读到文件末尾为止。C/C里标准的写法是int n; while (scanf(%d, n) ! EOF) { // 处理一组数据 }有些题目则会约定“输入以0 0结束”那就要在循环里判断并break。我在前三天里至少因为这两种读入方式理解偏差WA了五六次。后来养成一个习惯读题时先把输入输出说明单独划出来看清楚三件事——有几组数据、每组数据包含哪些字段、输出时有没有Case编号。这三件事确定之后再动手写代码。另一个容易被忽略的坑是读入性能。数据量一大cin和cout会比scanf和printf慢不少尤其在多组数据叠加的时候。如果你习惯用C的流必须在主函数开头加上这两行ios::sync_with_stdio(false); cin.tie(nullptr);实测下来加上这两行之后cin/cout的性能基本能追平C标准IO。但如果题目数据量到10^6级别我建议直接无脑用scanf和printf省得在性能边缘纠结。2.2 读题时先看数据范围再定算法第六天学到的最有用的习惯可能跟具体算法关系不大而是读题时先看数据范围。数据范围直接决定了你能用什么复杂度的算法。很多新手拿到题就开始想解法我前三天也这样结果常常是写了个暴力算法数据一大直接TLE白忙活。我整理了一个简单的对照表看了数据范围基本能锁定思考方向数据规模 n可接受的复杂度典型算法思路n ≤ 20O(2^n) 或 O(n!)状态压缩、DFS全排列n ≤ 1000O(n^2)双重循环枚举、简单DPn ≤ 10^5O(n log n)排序扫描、二分、贪心、线段树n ≤ 10^7O(n)线性扫描、线性DP、前缀和更大的范围O(log n) 或 O(1)数学公式、快速幂、倍增举个例子如果题目给了一个长度为10^5的数组要求找某个子区间的最值你脑子里应该立刻闪过O(n^2)的枚举一定会超时得往O(n log n)或O(n)的方向想。这个“反向约束”特别省时间相当于直接把一批不可能的思路提前排查掉了。2.3 一次“从暴力到线性”的小优化示范光说理论容易飘我拿一道每个OJ都有的经典题来说明给定一个整数数组求连续子数组的最大和。第一天我写的是三重循环暴力枚举int best INT_MIN; for (int i 0; i n; i) for (int j i; j n; j) { int sum 0; for (int k i; k j; k) sum a[k]; best max(best, sum); }这个写法逻辑完全正确但O(n^3)的复杂度数据量稍微大一点就会TLE。第二步我用了前缀和优化把内层求和变成O(1)整体降到O(n^2)。第三步才是关键——能不能只用一趟扫描完成答案是能这就是著名的Kadane算法int cur 0, best INT_MIN; for (int i 0; i n; i) { cur max(a[i], cur a[i]); best max(best, cur); }核心思想是在遍历每个位置时维护“以当前位置结尾的最大子数组和”要么从当前元素重新开始要么把当前元素接在前面的最优子数组后面。这个转变给我的触动很大——同一道题三个版本复杂度从O(n^3)降到O(n)这就是刷OJ最直接的收获你被迫去优化而不是停留在“能跑就行”。3. 实操过程与核心环节实现一道经典贪心题的完整拆解3.1 活动安排题目分析与思路推导第六天主要卡在贪心算法上其中印象深刻的是“活动安排问题”。题目描述大致是有n个活动每个活动有开始时间s[i]和结束时间e[i]你一个人同一时间只能参加一个活动问最多能参加多少个完整活动。输入格式是多组数据每组第一行是n接下来n行每行两个整数表示开始和结束时间n为0时结束。我第一反应是“按开始时间早的优先”但仔细一想就不对一个活动开始得很早但持续一整天会堵死后面所有活动。换思路按持续时间短优先也不行一个短活动正好横跨在另外两个活动的中间反而会挤掉两个能共存的活动。试了几种直觉策略都有反例最后才想到按结束时间最早排序这个经典做法。这里我想分享一个判断贪心策略是否靠谱的小技巧先构造反例再试图证明。一条贪心策略如果连你自己都能找出反例那它一定有问题如果构造了很久都找不到反例那它很可能就是对的这时候再尝试从数学上论证它。这个过程比直接看题解有价值得多。3.2 贪心策略的证明与边界处理选定了“按结束时间升序排序依次选择不冲突的活动”这个策略之后还需要说服自己它为什么正确。我用的是教科书上常见的“交换论证”思路假设某个最优解选的第一个活动不是结束时间最早的那么用结束时间最早的那个活动替换掉它替换后剩余的时间只会更宽裕不会影响后续活动的选择。所以存在一个最优解它的第一个活动就是按这个策略选出来的活动。接着对剩余活动重复同样的论证归纳可得这个贪心策略整体最优。证明的意义不只在数学上对实际编码也有直接帮助。明确了策略边界条件自然就浮出来了第一个活动直接选后续活动只要开始时间不小于当前已选活动的结束时间就选它。还要注意结束时间相同时排序的稳定性会影响谁排在前面但因为我们的策略只比较结束时间顺序不影响最终结果。有一个细节容易踩坑题目里说的时间都是整数排序后第一个活动的结束时间如果恰好等于第二个活动的开始时间能不能连着参加答案是看题目描述。多数活动安排问题里“参加完一个活动立刻开始另一个”是允许的条件写的是a.start lastEnd等于号千万不要丢。3.3 完整C实现与踩坑点把上面的分析落地成C代码大概是这个样子#include bits/stdc.h using namespace std; struct Activity { int start, end; }; bool cmp(const Activity a, const Activity b) { return a.end b.end; } int main() { int n; while (scanf(%d, n) ! EOF) { if (n 0) break; vectorActivity acts(n); for (int i 0; i n; i) { scanf(%d%d, acts[i].start, acts[i].end); } sort(acts.begin(), acts.end(), cmp); int count 1; int lastEnd acts[0].end; for (int i 1; i n; i) { if (acts[i].start lastEnd) { count; lastEnd acts[i].end; } } printf(%d\n, count); } return 0; }代码不长但有几个地方值得单独说。第一排序函数cmp用return a.end b.end;而不是这是因为std::sort要求比较器是严格弱序用在部分编译环境下会导致未定义行为。第二循环里从i 1开始因为第一个活动已经被选中了count的初始值是1而非0这个细节错一次就记住了。第三变量名count与标准库函数同名虽然在大多数OJ上编译没问题但为了保险起见我后面都改成了cnt。还有一点如果n可能为0时直接结束那代码开头就return 0避免后面访问acts[0]越界。3.4 一个变式带来的复杂度思考同样是区间类问题换一层皮就是“区间覆盖”给定一个总区间给你若干个子区间问最少用多少个子区间能覆盖整个区间。这题看着跟活动安排很像但策略完全不同——它要按起点排序然后贪心选择能覆盖当前点且右端点最远的区间。两道题正好说明一个道理贪心策略不是背出来的是结合题目目标分析出来的。活动安排本身的复杂度是排序O(n log n)加扫描O(n)整体O(n log n)。在做题的时候可以顺手把这个复杂度写进笔记以后看到n在10^5量级又涉及选择的区间问题优先想想排序之后能不能贪心。这个“题型算法复杂度”的组合记忆比零散刷题效率高很多。4. 常见问题与排查技巧实录4.1 从WA到AC我的排错顺序第六天晚上我被一道模拟题折磨了很久本地跑得好好的一提交就是WA。后来总结了一套排错顺序现在每次WA都按这个顺序走不说百发百中但能节省至少一半的排查时间。第一步重新读一遍题尤其是输入输出说明和样例。我六天里遇到不少WA其实是自己没看清题目要输出的是“Case #1: 最大和”这种带编号的格式我直接输出了一行数字题目说输入有多组数据我只处理了第一组。读题永远是最便宜的排查方式。第二步检查边界条件。重点看三个地方数组大小够不够n10^5时数组千万别开成n1以下、循环边界有没有越界、有没有除以零的可能。拿活动安排来说n等于1时程序会不会崩这就是边界条件问题。第三步用更小的数据手算验证。不是看样例是自己造几个极端数据最小规模、最大规模、重复数据、逆序数据。把程序输出和手工推导结果对着看往往能让逻辑错误暴露得很明显。第四步检查数据类型。很多WA其实是精度或溢出问题。int的范围大概是2.1×10^9题目如果涉及10^9以上的累加或乘法必须换成long long。前六天我至少被这个坑绊倒过三次后面看到“和”“总数”“乘积”这类词直接条件反射用long long。4.2 常见评测错误类型速查我把这些天遇到过的评测反馈整理成一张速查表方便对照评测状态含义常见原因排查方向AC通过无不用管下一题CE编译错误语法错误、缺头文件、C标准不匹配看编译报错信息按行号修WA答案错误逻辑错误、输出格式不对、数据类型不符重读题构造边界数据TLE运行超时算法复杂度过高、死循环优化算法检查循环条件RE运行错误数组越界、除零、栈溢出查数组下标查递归深度MLE内存超限数组开太大、结构体内存浪费查数组维度减少内存占用PE格式错误多余空格、缺少换行严格对照输出样例这里多说一句TLE。第六天我做了一道排序题数据范围写着10^5我想都没想写了个冒泡排序结果TLE。换成sort之后秒过。这个案例让我意识到多数TLE不是代码写错了是选错了算法。所以排查TLE时先看数据范围再回头审视复杂度不要只想着微调代码细节。4.3 不传之秘本地对拍与文件调试还有一个特别适合OJ刷题的技巧就是文件重定向。在本地调试的时候反复手动输入数据太慢了尤其是多组数据的题目几乎能把人逼疯。我一般这么处理freopen(in.txt, r, stdin); freopen(out.txt, w, stdout);把题目给的数据放进in.txt跑完直接看out.txt省去了每轮手动输入的时间。提交之前把这两行注释掉或者删掉新手最容易犯的错就是忘记删freopen导致评测系统读不到输入直接RE。更进阶一点的叫对拍写一个暴力但保证正确的程序A再写一个待验证的优化程序B用随机数据生成器生成多组数据比较A和B的输出是否一致。一旦输出不一致就把那组数据保存下来缩小范围定位B的问题。while true; do ./generator input.txt ./bf input.txt bf_out.txt ./fast input.txt fast_out.txt if ! diff -q bf_out.txt fast_out.txt /dev/null; then break fi done这个做法尤其适合验证贪心、动态规划这类“策略型”算法因为贪心策略的细节一多就容易出错用暴力程序做参照物能轻松抓到策略上的反例数据。5. 学习效率与复盘体系个人经验总结5.1 笔记怎么记才有用前三天我刷完题就完事既不记笔记也不复盘结果就是同样的错误换个马甲反复踩。第四天开始认真做记录到第六天已经攒了八十多条笔记每条都很短但信息密度很高。我的笔记格式固定为四行题目编号与来源、问题类型模拟/贪心/DP/图论等、解题核心思路一句话、踩坑记录。举个例子HDU 2037 今年暑假不AC | 类型贪心·区间 思路按结束时间升序排序能选就选。 坑输入多组数据直到0结束条件用 start lastEnd 等号别丢。这样做的好处是复习的时候不用重新读题扫一眼就能回忆整个思考链。尤其是“类型”和“踩坑记录”这两行过两周回看仍然有参考价值。我还给每道题标了难度等级和是否需重刷定期把标了“重刷”的题拿出来再看一遍效果比盲目刷新题要好。5.2 刷题节奏与卡题应对刷OJ最怕的就是卡题。我给自己定了一个“三步走”先独立思考30分钟别急着看题解如果30分钟没有思路去找题解里关于思路的说明看完思路自己动手写代码而不是直接看参考代码AC之后再花十分钟复盘看自己的解法和标准解法差距在哪。这套节奏的核心逻辑是卡住不可怕直接抄答案才是真正的损失。一道题卡两小时以上边际收益已经很低了这时参考题解理清思路然后把代码一步步敲出来对思维的锻炼一样有效。我见很多新手卡题后心态崩了然后连续几天不想碰OJ反而得不偿失。合理的做法是卡题要么换题要么在思路上寻求一点提示就是不要“死磕到天亮”。另外提一下专题刷题和随机刷题的选择。对刚起步的阶段我更推荐专题式一个周末专门刷贪心下一个周末专门刷简单动态规划同类题连刷三五道套路就刻进脑子里了。随机刷题容易东一榔头西一棒槌每个类型都浅尝辄止感觉刷了不少题到真正做题的时候反而啥都想不起来。至于平台选择杭电OJ、洛谷、POJ都是免费而且题库量大、适合新手起步的地方。不用同时开好几个平台选定一个主平台把它的题目按难度递进刷下去就够了。不同平台对C的编译标准可能有细微差异主要注意自己本地的编译选项和OJ的环境是不是一致当初我在一个老平台上用了C11的特性编译直接报错后来乖乖按平台支持的版本写代码。写到这里我发现第六天最大的收获不是AC了多少题而是把一套稳定的刷题流程跑顺了读题先看数据范围策略先找反例再证明提交WA之后按固定顺序排查每AC一题总结四行笔记。跟我前五天那种想到哪写到哪的状态比完全是两种体验。如果你也正好刷到第六七天卡在某个TLE或WA上不用着急把输入输出格式、数据范围判断、排错顺序这三件事理顺后面的路真的会顺很多。回看这六天把坑记录下来这件事本身可能比AC本身更有价值。
从输入输出到贪心算法：OJ刷题六天实战复盘
OJ刷题这件事我是从一份网上的入门清单开始的。断断续续刷了六天从一开始连输入输出格式都搞不明白到现在能静下心把一道题从读题到AC完整走下来中间踩过的坑比想象中多得多。这篇文章就是我Day6的学习笔记复盘记录前六天里验证过的学习方法、实际踩过的坑以及一套可以直接照着上手的刷题流程。如果你也刚开始在OJ平台刷题或者刷了一两周还在原地打转这篇应该对你有用。第六天是个很微妙的时间点新鲜感消退了算法能力还没形成质变最容易在这个阶段放弃。但恰恰是这几天把“提交代码→看评测结果→定位问题→再提交”的循环跑顺了后面刷任何题都会轻松很多。这篇笔记不罗列流水账只讲真正影响刷题效率的几件事从平台操作、输入输出、数据范围判断到一道经典贪心题的完整拆解再到WA之后的排查套路希望对你有参考价值。1. 前六天到底在做什么学习节奏与阶段复盘1.1 Day6这个微妙节点意味着什么我第一天做的事情现在回头看相当“原始”注册账号、逛题目列表、挑了一道标着“入门”的水题结果连编译错误都没绕过去。第一天到第三天基本是在跟OJ平台的规则搏斗——怎么提交、评测状态长什么样、为什么本地运行正常却一直报错。这个阶段谈不上算法更多是熟悉一套新的反馈系统。到了第四五天开始能顺着题目给的样例把代码跑通但换个测试数据就原形毕露最典型的表现就是“样例过了提交WA”。第六天最大的变化是我终于肯在写代码之前先把题目在纸上理一遍再动手。这个转变很关键它意味着刷题开始从“写代码”转变为“解决问题”前者靠手感后者靠逻辑。如果你正处在这个阶段我想说前几天的混乱是正常的。OJ刷题本质上是一项需要“人机互相适应”的技能你得先习惯机器评判的确定性——它不会因为你写得辛苦就网开一面只看结果对不对。接受这个逻辑心态会稳很多。1.2 从裸写代码到读懂评测结果前端时间我统计了六天里遇到的评测反馈最常见的几类分别是编译错误CE、答案错误WA、运行超时TLE、运行错误RE当然还有最想看到的正确AC。第一天看到WA心里会咯噔一下三天之后再看WA第一反应是“好开始排错”这个心态转变实际就是熟练度提升的信号。我总结出来的一条经验是第一周最该练的不是算法技巧而是读懂反馈并用反馈修正代码的循环能力。具体来说就是把每次提交变成一次信息收集CE告诉你语法或编译环境有问题RE提示你数组越界或非法访问TLE在暗示算法复杂度太高WA则说明逻辑和题目要求之间有偏差。每种反馈对应不同的排查方向这个映射关系我放在后面第4节详细拆这里先记住一个结论评测结果不是宣判是调试信息。给自己定一个简单目标也有帮助前六天不求多每天AC两到三道题就够了。我见过不少人一上来就给自己安排一天十道结果第三天就放弃了。频率比数量重要保持每天碰题的节奏比周末狂刷十小时划算得多。2. 核心细节解析与实操要点输入输出、数据范围与算法选择2.1 为什么OJ的输入输出格式是第一个坑对刚接触OJ的人来说输入输出格式往往是第一道隐形的墙。本地写程序数据是自己给的OJ平台上数据是评测系统喂进来的程序必须按题目要求的格式读入并输出多一个空格、少一个换行可能直接判WA甚至PE格式错误。以最常见的“多组测试数据”为例题目可能完全不告诉你有多少组而是要求读到文件末尾为止。C/C里标准的写法是int n; while (scanf(%d, n) ! EOF) { // 处理一组数据 }有些题目则会约定“输入以0 0结束”那就要在循环里判断并break。我在前三天里至少因为这两种读入方式理解偏差WA了五六次。后来养成一个习惯读题时先把输入输出说明单独划出来看清楚三件事——有几组数据、每组数据包含哪些字段、输出时有没有Case编号。这三件事确定之后再动手写代码。另一个容易被忽略的坑是读入性能。数据量一大cin和cout会比scanf和printf慢不少尤其在多组数据叠加的时候。如果你习惯用C的流必须在主函数开头加上这两行ios::sync_with_stdio(false); cin.tie(nullptr);实测下来加上这两行之后cin/cout的性能基本能追平C标准IO。但如果题目数据量到10^6级别我建议直接无脑用scanf和printf省得在性能边缘纠结。2.2 读题时先看数据范围再定算法第六天学到的最有用的习惯可能跟具体算法关系不大而是读题时先看数据范围。数据范围直接决定了你能用什么复杂度的算法。很多新手拿到题就开始想解法我前三天也这样结果常常是写了个暴力算法数据一大直接TLE白忙活。我整理了一个简单的对照表看了数据范围基本能锁定思考方向数据规模 n可接受的复杂度典型算法思路n ≤ 20O(2^n) 或 O(n!)状态压缩、DFS全排列n ≤ 1000O(n^2)双重循环枚举、简单DPn ≤ 10^5O(n log n)排序扫描、二分、贪心、线段树n ≤ 10^7O(n)线性扫描、线性DP、前缀和更大的范围O(log n) 或 O(1)数学公式、快速幂、倍增举个例子如果题目给了一个长度为10^5的数组要求找某个子区间的最值你脑子里应该立刻闪过O(n^2)的枚举一定会超时得往O(n log n)或O(n)的方向想。这个“反向约束”特别省时间相当于直接把一批不可能的思路提前排查掉了。2.3 一次“从暴力到线性”的小优化示范光说理论容易飘我拿一道每个OJ都有的经典题来说明给定一个整数数组求连续子数组的最大和。第一天我写的是三重循环暴力枚举int best INT_MIN; for (int i 0; i n; i) for (int j i; j n; j) { int sum 0; for (int k i; k j; k) sum a[k]; best max(best, sum); }这个写法逻辑完全正确但O(n^3)的复杂度数据量稍微大一点就会TLE。第二步我用了前缀和优化把内层求和变成O(1)整体降到O(n^2)。第三步才是关键——能不能只用一趟扫描完成答案是能这就是著名的Kadane算法int cur 0, best INT_MIN; for (int i 0; i n; i) { cur max(a[i], cur a[i]); best max(best, cur); }核心思想是在遍历每个位置时维护“以当前位置结尾的最大子数组和”要么从当前元素重新开始要么把当前元素接在前面的最优子数组后面。这个转变给我的触动很大——同一道题三个版本复杂度从O(n^3)降到O(n)这就是刷OJ最直接的收获你被迫去优化而不是停留在“能跑就行”。3. 实操过程与核心环节实现一道经典贪心题的完整拆解3.1 活动安排题目分析与思路推导第六天主要卡在贪心算法上其中印象深刻的是“活动安排问题”。题目描述大致是有n个活动每个活动有开始时间s[i]和结束时间e[i]你一个人同一时间只能参加一个活动问最多能参加多少个完整活动。输入格式是多组数据每组第一行是n接下来n行每行两个整数表示开始和结束时间n为0时结束。我第一反应是“按开始时间早的优先”但仔细一想就不对一个活动开始得很早但持续一整天会堵死后面所有活动。换思路按持续时间短优先也不行一个短活动正好横跨在另外两个活动的中间反而会挤掉两个能共存的活动。试了几种直觉策略都有反例最后才想到按结束时间最早排序这个经典做法。这里我想分享一个判断贪心策略是否靠谱的小技巧先构造反例再试图证明。一条贪心策略如果连你自己都能找出反例那它一定有问题如果构造了很久都找不到反例那它很可能就是对的这时候再尝试从数学上论证它。这个过程比直接看题解有价值得多。3.2 贪心策略的证明与边界处理选定了“按结束时间升序排序依次选择不冲突的活动”这个策略之后还需要说服自己它为什么正确。我用的是教科书上常见的“交换论证”思路假设某个最优解选的第一个活动不是结束时间最早的那么用结束时间最早的那个活动替换掉它替换后剩余的时间只会更宽裕不会影响后续活动的选择。所以存在一个最优解它的第一个活动就是按这个策略选出来的活动。接着对剩余活动重复同样的论证归纳可得这个贪心策略整体最优。证明的意义不只在数学上对实际编码也有直接帮助。明确了策略边界条件自然就浮出来了第一个活动直接选后续活动只要开始时间不小于当前已选活动的结束时间就选它。还要注意结束时间相同时排序的稳定性会影响谁排在前面但因为我们的策略只比较结束时间顺序不影响最终结果。有一个细节容易踩坑题目里说的时间都是整数排序后第一个活动的结束时间如果恰好等于第二个活动的开始时间能不能连着参加答案是看题目描述。多数活动安排问题里“参加完一个活动立刻开始另一个”是允许的条件写的是a.start lastEnd等于号千万不要丢。3.3 完整C实现与踩坑点把上面的分析落地成C代码大概是这个样子#include bits/stdc.h using namespace std; struct Activity { int start, end; }; bool cmp(const Activity a, const Activity b) { return a.end b.end; } int main() { int n; while (scanf(%d, n) ! EOF) { if (n 0) break; vectorActivity acts(n); for (int i 0; i n; i) { scanf(%d%d, acts[i].start, acts[i].end); } sort(acts.begin(), acts.end(), cmp); int count 1; int lastEnd acts[0].end; for (int i 1; i n; i) { if (acts[i].start lastEnd) { count; lastEnd acts[i].end; } } printf(%d\n, count); } return 0; }代码不长但有几个地方值得单独说。第一排序函数cmp用return a.end b.end;而不是这是因为std::sort要求比较器是严格弱序用在部分编译环境下会导致未定义行为。第二循环里从i 1开始因为第一个活动已经被选中了count的初始值是1而非0这个细节错一次就记住了。第三变量名count与标准库函数同名虽然在大多数OJ上编译没问题但为了保险起见我后面都改成了cnt。还有一点如果n可能为0时直接结束那代码开头就return 0避免后面访问acts[0]越界。3.4 一个变式带来的复杂度思考同样是区间类问题换一层皮就是“区间覆盖”给定一个总区间给你若干个子区间问最少用多少个子区间能覆盖整个区间。这题看着跟活动安排很像但策略完全不同——它要按起点排序然后贪心选择能覆盖当前点且右端点最远的区间。两道题正好说明一个道理贪心策略不是背出来的是结合题目目标分析出来的。活动安排本身的复杂度是排序O(n log n)加扫描O(n)整体O(n log n)。在做题的时候可以顺手把这个复杂度写进笔记以后看到n在10^5量级又涉及选择的区间问题优先想想排序之后能不能贪心。这个“题型算法复杂度”的组合记忆比零散刷题效率高很多。4. 常见问题与排查技巧实录4.1 从WA到AC我的排错顺序第六天晚上我被一道模拟题折磨了很久本地跑得好好的一提交就是WA。后来总结了一套排错顺序现在每次WA都按这个顺序走不说百发百中但能节省至少一半的排查时间。第一步重新读一遍题尤其是输入输出说明和样例。我六天里遇到不少WA其实是自己没看清题目要输出的是“Case #1: 最大和”这种带编号的格式我直接输出了一行数字题目说输入有多组数据我只处理了第一组。读题永远是最便宜的排查方式。第二步检查边界条件。重点看三个地方数组大小够不够n10^5时数组千万别开成n1以下、循环边界有没有越界、有没有除以零的可能。拿活动安排来说n等于1时程序会不会崩这就是边界条件问题。第三步用更小的数据手算验证。不是看样例是自己造几个极端数据最小规模、最大规模、重复数据、逆序数据。把程序输出和手工推导结果对着看往往能让逻辑错误暴露得很明显。第四步检查数据类型。很多WA其实是精度或溢出问题。int的范围大概是2.1×10^9题目如果涉及10^9以上的累加或乘法必须换成long long。前六天我至少被这个坑绊倒过三次后面看到“和”“总数”“乘积”这类词直接条件反射用long long。4.2 常见评测错误类型速查我把这些天遇到过的评测反馈整理成一张速查表方便对照评测状态含义常见原因排查方向AC通过无不用管下一题CE编译错误语法错误、缺头文件、C标准不匹配看编译报错信息按行号修WA答案错误逻辑错误、输出格式不对、数据类型不符重读题构造边界数据TLE运行超时算法复杂度过高、死循环优化算法检查循环条件RE运行错误数组越界、除零、栈溢出查数组下标查递归深度MLE内存超限数组开太大、结构体内存浪费查数组维度减少内存占用PE格式错误多余空格、缺少换行严格对照输出样例这里多说一句TLE。第六天我做了一道排序题数据范围写着10^5我想都没想写了个冒泡排序结果TLE。换成sort之后秒过。这个案例让我意识到多数TLE不是代码写错了是选错了算法。所以排查TLE时先看数据范围再回头审视复杂度不要只想着微调代码细节。4.3 不传之秘本地对拍与文件调试还有一个特别适合OJ刷题的技巧就是文件重定向。在本地调试的时候反复手动输入数据太慢了尤其是多组数据的题目几乎能把人逼疯。我一般这么处理freopen(in.txt, r, stdin); freopen(out.txt, w, stdout);把题目给的数据放进in.txt跑完直接看out.txt省去了每轮手动输入的时间。提交之前把这两行注释掉或者删掉新手最容易犯的错就是忘记删freopen导致评测系统读不到输入直接RE。更进阶一点的叫对拍写一个暴力但保证正确的程序A再写一个待验证的优化程序B用随机数据生成器生成多组数据比较A和B的输出是否一致。一旦输出不一致就把那组数据保存下来缩小范围定位B的问题。while true; do ./generator input.txt ./bf input.txt bf_out.txt ./fast input.txt fast_out.txt if ! diff -q bf_out.txt fast_out.txt /dev/null; then break fi done这个做法尤其适合验证贪心、动态规划这类“策略型”算法因为贪心策略的细节一多就容易出错用暴力程序做参照物能轻松抓到策略上的反例数据。5. 学习效率与复盘体系个人经验总结5.1 笔记怎么记才有用前三天我刷完题就完事既不记笔记也不复盘结果就是同样的错误换个马甲反复踩。第四天开始认真做记录到第六天已经攒了八十多条笔记每条都很短但信息密度很高。我的笔记格式固定为四行题目编号与来源、问题类型模拟/贪心/DP/图论等、解题核心思路一句话、踩坑记录。举个例子HDU 2037 今年暑假不AC | 类型贪心·区间 思路按结束时间升序排序能选就选。 坑输入多组数据直到0结束条件用 start lastEnd 等号别丢。这样做的好处是复习的时候不用重新读题扫一眼就能回忆整个思考链。尤其是“类型”和“踩坑记录”这两行过两周回看仍然有参考价值。我还给每道题标了难度等级和是否需重刷定期把标了“重刷”的题拿出来再看一遍效果比盲目刷新题要好。5.2 刷题节奏与卡题应对刷OJ最怕的就是卡题。我给自己定了一个“三步走”先独立思考30分钟别急着看题解如果30分钟没有思路去找题解里关于思路的说明看完思路自己动手写代码而不是直接看参考代码AC之后再花十分钟复盘看自己的解法和标准解法差距在哪。这套节奏的核心逻辑是卡住不可怕直接抄答案才是真正的损失。一道题卡两小时以上边际收益已经很低了这时参考题解理清思路然后把代码一步步敲出来对思维的锻炼一样有效。我见很多新手卡题后心态崩了然后连续几天不想碰OJ反而得不偿失。合理的做法是卡题要么换题要么在思路上寻求一点提示就是不要“死磕到天亮”。另外提一下专题刷题和随机刷题的选择。对刚起步的阶段我更推荐专题式一个周末专门刷贪心下一个周末专门刷简单动态规划同类题连刷三五道套路就刻进脑子里了。随机刷题容易东一榔头西一棒槌每个类型都浅尝辄止感觉刷了不少题到真正做题的时候反而啥都想不起来。至于平台选择杭电OJ、洛谷、POJ都是免费而且题库量大、适合新手起步的地方。不用同时开好几个平台选定一个主平台把它的题目按难度递进刷下去就够了。不同平台对C的编译标准可能有细微差异主要注意自己本地的编译选项和OJ的环境是不是一致当初我在一个老平台上用了C11的特性编译直接报错后来乖乖按平台支持的版本写代码。写到这里我发现第六天最大的收获不是AC了多少题而是把一套稳定的刷题流程跑顺了读题先看数据范围策略先找反例再证明提交WA之后按固定顺序排查每AC一题总结四行笔记。跟我前五天那种想到哪写到哪的状态比完全是两种体验。如果你也正好刷到第六七天卡在某个TLE或WA上不用着急把输入输出格式、数据范围判断、排错顺序这三件事理顺后面的路真的会顺很多。回看这六天把坑记录下来这件事本身可能比AC本身更有价值。
