OJ刷题实战复盘：二分答案、最短路与状态压缩DP的避坑指南

2026年3月5日外面的天气还有点凉我照常泡了杯茶坐到电脑前。今年的春招算法题已经陆陆续续放出来了我自己也在校OJ和一些公开题库上刷了不少题。这个日子不算特殊就是普通的一个训练日但今天的状态和手感都还不错上午在杭电OJ上AC了4道下午又去了洛谷和东方博宜各刷了几道整体下来大概过了十几道题有几个题值得单独复盘。借着今天这个机会正好把最近一段时间在OJ刷题的经历做个阶段性的总结也算给后面准备继续刷题的朋友一条可以参考的路径。先说说背景我目前是普通本科计算机相关专业在读从大一暑假开始接触算法竞赛说实话算不上天赋型选手就是靠时间和题量一点点磨。前几年一直用C在杭电OJ和洛谷刷最近因为要准备几场机试也开始关注华为OD那种偏业务逻辑的题目风格所以这段时间的刷题范围比以前广了不少。今天的总结我会按照“题型复盘—踩坑记录—刷题方法—下一步计划”四块来写尽量把每个题的核心思路、我在提交过程中遇到的问题以及解法背后的原因讲清楚而不是简单贴几个题号和结论。1. 今日刷题概况平台、题量与状态1.1 今天在哪些平台刷了题先说今天跑了哪些地方。上午主要在杭电OJHDU做了一套经典题目下午转到洛谷刷了几道带模拟性质的题目晚上又抽出半小时去郑轻OJ和东方博宜各看了看。很多人可能会问为什么要同时在好几个平台刷我的习惯是杭电OJ和洛谷用来打基础、练经典算法东方博宜的题目偏基础适合巩固郑轻OJ是朋友推荐的题目风格比较有意思适合在零散时间当思维训练。实际刷题的时候不同平台各有各的“脾气”。杭电的题目题干普遍精简样例给得比较直白但有些题对输入输出格式卡得很严稍不留神就Presentation Error。洛谷的话题解氛围好讨论区干货多更适合学思路。东方博宜的代码环境对新手友好即使写错也会给出比较详细的错误提示我用它来给学弟学妹推荐入门题。郑轻OJ的题目数量不多但有几道二分和图论题出得相当讲究后面会专门提到。1.2 今天的战绩和总体状态今天一共提交了36次AC了15道题其中有2道是之前卡了好几天没过的老题今天换了个思路终于过了心情还是挺舒畅的。另外还有3道题交了多次都是超时最后靠换用更优的算法才跑过去。这个AC率放在大佬眼里肯定不算什么但对我来说算是在正常范围之内毕竟今天的题目里混了好几道需要认真抠细节的题。今天的状态比较有意思。上午一开始略微浮躁前两题做得很快各种小错误频出WA了好几次。后来我强迫自己放慢节奏每道题先花5分钟把边界条件想清楚再动手后面就顺很多了。下午做题的时候心态明显稳一些尤其是做图论题的时候能更专注地抠状态转移和边界条件。刷完今天这些题目最大的感受是“基础不牢地动山摇”——很多题看起来是新题实际上还是那些老算法在换包装。2. 核心题型复盘今天真正吃透的几类题2.1 二分答案不是“会二分”就行要会证明单调性今天的重点题型之一是二分答案这也是我最近刻意加强训练的模块。以前我写二分总是靠模板遇到整数二分就开始在l mid 1还是r mid - 1之间反复横跳代码改来改去还是错。今天做的一道经典题目大意是给定若干任务点和机器数量要求最小化完成所有任务的最长时间本质上就是一个“最小化最大值”的二分答案题。这类题的核心不在于你会写二分循环而在于你是否能想清楚“当时间是x时能不能完成任务”这个判定函数以及判定结果是否随x单调变化。比如上面的题如果给的时间x越大机器能完成任务的概率就越高这就是单调性。一旦想清楚这个就可以直接套二分框架把原问题转成判定问题复杂度从O(n^2)降到了O(n log n)级别。今天在写这道判定函数的时候踩了一个坑我一开始用贪心模拟机器分配任务但没注意任务是有先后顺序依赖的导致判定函数写错二分的结果自然也不对。后来我把任务按依赖顺序排好序再用优先队列维护机器的空闲时间判定函数才写对。所以二分答案的难点从来不在“二分”本身而在判定函数你怎么设计得既正确又高效。2.2 最短路问题的一次深刻教训堆优化Dijkstra的细节第二类值得说的是最短路。今天做了一道带点权图的题目要求是求从起点到终点的最小代价每条边和每个点都有不同的通过成本。一开始我直接用裸的Dijkstra跑结果发现点权没有处理好程序输出的答案比实际答案大原因是我把点权的代价重复累加了好几次。这个错误很有代表性。最短路本身不难难在状态里有额外约束时你要不断提醒自己当前这个“代价”到底包含了哪几个部分每个部分是被更新了几次正确的做法是把点权在“离开该点”的时候统一加入代价而不是在每次经过此点时都累加一次。再或者可以把每个点拆成“入点”和“出点”中间连一条代价为点权的边这样就能完美地把点权转换成边权用标准Dijkstra直接跑。今天还复习了堆优化Dijkstra的一个关键细节用priority_queue维护当前最小距离节点时必须在出队时判断该节点是否已经被确定过最短距离。很多人写堆优化Dijkstra容易忽略这个判断导致同一个节点被多次扩展严重拖慢运行速度甚至可能出现错误结果。正确做法是维护一个vis数组出队时如果发现当前距离大于dis[u]直接跳过。这个细节虽然不起眼但在密集图场景测试下影响非常明显。2.3 动态规划从暴力递归到状态压缩的一步之遥今天有两道动态规划题一题是经典的背包类变形另一题是状态压缩DP。背包题大概背景是有n种不同体积和价值的物品每种物品可以拿无限件但是有一个额外限制是总体积不能超过m同时还要保证某类特殊物品的选择数量是偶数。前面一半是裸的完全背包加上“偶数为限制”就变成了二维状态DP。这种题如果想清楚状态设计解法并不复杂dp[i][j][k]表示前i种物品体积不超过j且当前特殊物品数量奇偶性为k时的最大价值转移时注意奇偶性翻转。但实际上大多数人的问题在于一开始想不到要加一维状态来表示奇偶性而是试图在转移前后做各种判断然后把状态搞得乱七八糟。我的经验是遇到约束条件先想这个约束是“限制数量”还是“限制关系”如果是限制关系就大胆地把它拆成DP状态的一维这一步想清楚了递推公式自然就出来了。另一道状态压缩DP的题是求一个哈密顿路径类的变种给定一个图要求从某个起点出发访问每个节点恰好一次的最小花费。这种题目的n范围非常小不超过15所以一眼就要意识到状压DP。dp[mask][i]表示已访问节点集合为mask最后停在节点i的最小花费转移时枚举下一个节点j更新状态即可。这类“看数据范围定算法”的能力很重要。n是15暴力枚举是15!肯定不行但2^15乘以n再乘以n的转移只有几十万次完全可跑。我和很多初学者交流过发现很多人不是不会写状压DP而是根本意识不到“n这么小的时候可以用状压”。所以我建议看到数据范围特别小比如n小于20的图论、排列类问题优先往状态压缩的方向想。2.4 字符串处理与模拟OJ中最“阴”的题今天还做了几道和字符串相关的模拟题。说实话我最怕的就是这类题因为它们在算法上不难但在细节处理上往往能卡死人。有一道题是计算一个自定义日期格式之间的天数差要求处理闰年、大小月以及格式中的各种大小写问题。这种题不存在算法难度纯粹考察你能不能把逻辑写清楚。我研究了一套通用的模拟题处理思路先读清楚题目中所有边界条件把输入数据的格式用正则或者手动解析好接着在草稿纸上写出每种可能的情况最后再写代码。写代码的时候把所有特殊情况单独抽成函数例如“判断闰年”“计算某天是全年的第几天”这样后面查错会容易很多。字符串处理还有一个小坑是scanf读入字符串时遇到空格会断开所以遇到包含空格的输入要用fgets或者getline。今天在郑轻OJ就碰到一道这样的题我一开始用scanf(%s, str)读结果字符串在空格处被切断程序行为跟我预期完全不符白白浪费了好几次提交。后来换成一次读完一整行再用手动遍历处理每个字符问题就解决了。这个坑非常典型值得写进笔记里。这类偏业务逻辑的模拟题其实和华为OD机试风格很像——不是考多高深的算法而是考你能否在有限时间内写出不Loose的工程代码。3. 提交过程中的踩坑与排查那些防不胜防的细节3.1 输入输出格式WA和PE的一生之敌如果让我说OJ提交中最常见的问题输入输出格式绝对排在第一位。今天在杭电OJ上有一道非常简单的题我的算法逻辑一点问题都没有但连续两次交上去都报了“Presentation Error”。原因是我多输出了一行空行或者两个数字之间的空格数量不对。这类错误不仔细看真看不出来但OJ会非常严格地区分“Wrong Answer”和“Presentation Error”后者通常意味着逻辑是对的、但输出格式不符合预期。很多人觉得OJ判题只看答案对不对这种想法容易吃亏。我在处理输出格式时已经养成了几个习惯第一任何两个数据块之间严格按题目要求控制换行个数不要想当然地“多加一行空行把结果隔开”第二如果用printf输出浮点数必须要留意题目说的“保留几位小数”是四舍五入还是直接截断不同OJ可能有不同实现第三多组测试数据时每组输出的末尾换行数也要一致不要出现第一组后面有一个空行、第二组后面没有的情况。在输出浮点数时还有一个经典陷阱是精度问题。你计算出来的结果可能是0.9999999但题目要求答案是1.0。这种情况通常是浮点误差造成的应该在输出前对结果做一次1e-9之类的修正或者直接使用round函数。今天有一道几何题就这么坑了我一下算三角形面积时用海伦公式开根号后浮点误差导致输出不满足预期后来加了一个很小的eps再输出才过。3.2 数据范围与溢出一个int引发的连环惨案今天下午在东方博宜OJ做的一道题题目背景是“求区间内所有数的平方和”看起来极其简单我用int类型存答案结果样例都过了但一提交就WA。后来仔细一算才发现n最大到100000平方和直接翻到几百亿早就超出了int的2^31-1上限。改用long long之后一提交就过了。这种数据范围题太常见了刷OJ建议从一开始就形成肌肉记忆凡是涉及累加、相乘、求和的变量在没有仔细计算范围之前一律开long long能开long long就不开int。还有一类数据范围陷阱是数组越界。今天在洛谷做一道邻接表存图的最短路题时我初始化边数组大小为n但实际上无向图要存2倍边数结果遍历邻接表时越界程序行为怪异一会儿WA一会儿RE。后来检查才发现是数组开小了。在OJ题里数组开小很少直接提示“越界”往往会表现为莫名其妙的错误。我的排查经验是只要出现“本地运行正常、OJ报RE”的情况第一件事就是检查所有数组大小是否足够是否漏乘了2倍或加1。3.3 STL使用细节为什么我的优先队列总是慢今天有几道题都用了priority_queue有一个题因为数据量特别大我的第一次提交直接超时。原因是我在优先队列的节点里存了整个结构体而结构体比较大每次push和pop都要复制很多数据。换成存pairint, int之后时间立刻降了三分之一。在写算法题时优先队列的模板参数里尽量存小的、轻量的类型如果必须存自定义结构体也尽量只存关键信息比如编号和当前距离其他信息通过数组另存。另一个STL坑是vector的动态扩容。在一些复杂度敏感的题目中频繁push_back可能导致常数增大极限数据下容易被卡超时。我现在的习惯是如果提前知道最大容量直接reserve好内存不要依赖自动扩容。这样不只是图那一点点性能提升更重要的是能让心里有底知道这个容器在极端情况下不会因为内存分配而产生额外开销。3.4 多组数据的“清空”问题多组输入是OJ题目里特别常见的形式也是最容易出隐蔽bug的地方。今天杭电OJ有一道题是多组输入直到文件结束每组里面会构建一张图。我第一次只记得重用变量但忘记清空上一组的邻接表导致第二组的数据还残留着第一组的边信息结果一组数据污染了后面所有组的答案。这种问题的排查方式也很简单如果你发现“第一组对、第二组错、第三组又对”这样的奇偶规律多半是有些全局变量或容器没有在循环开始时清空。我的做法是在每组数据处理的开头统一调用一个init()函数把所有要用的数组、容器、计数器全部重置。有时候为了省事用memset清空数组但这里也有坑——如果数组是vectormemset不能直接清理其内部动态分配的空间必须用clear。所以对象是什么类型就按什么类型来清理别混着来。4. 时间管理与刷题效率怎么让每天的刷题真正涨分4.1 先易后难还是先难后易很多人刷题有个习惯上来就挑最难的题死磕一天下来颗粒无收。我自己试过这种玩法除了挫败感一无所有。现在我的策略是每天开始先做两到三道热身题难度低于当前水平目的是把状态“热”起来。然后再去做一道核心目标题这道题要稍微高于当前能力值得花30-60分钟去思考。如果实在没思路我会找题解看思路但不是直接抄代码而是看完思路后自己重新写一遍。这个策略背后的逻辑是题目想不出来的时候硬耗时间是一种很低效的打磨方式不是说完全不该耗而是别从头耗到尾。先做简单题积累正确率会给大脑一个正反馈信号后面做难题的时候心态明显不一样反过来一上来就被难题卡住容易一整天的状态都不好。4.2 题解怎么看才能不白看我在刷题时经常会看别人的题解但有一个原则绝不直接复制代码。我会先看评论区对解题思路的描述理清核心算法的框架然后自己从头实现。如果卡住了再回头看看某一步的状态定义或者边界处理是怎么写的但坚持在理解的基础上重写。今天在做那道状态压缩DP时我先自己想了20分钟没有完全想清转移顺序于是看了题解里关于“枚举子集”的提示。看懂后我合上题解自己写写出了dp[mask][i] min(dp[mask ^ (1 i)][j] dist[j][i])的转移。虽然最后AC了但代码习惯和题解不一样这反而让我印象更深。看题解的目的不是把答案背下来而是打开思路后把这道题真正变成自己的东西。4.3 刷题笔记比刷题本身更重要的一件事今天的总结能写得这么细其实全靠平时刷题时写的笔记。我从大二开始用Markdown记录每道题的核心思路、错因、复杂度刚开始觉得麻烦后来发现这几乎是提升最关键的一环。因为算法题的知识点是相互关联的定义一个很精妙的状态可能过两个月就忘了当时不记录之后再遇到类似题目又要重新摸索。我做笔记有一套固定格式题目链接、难度、考察知识点、我的初始思路、卡住的地方、正确解法、同类题扩展。这套格式看起来很平常但时间长了积少成多会形成一本自己的“错题集”。尤其到了准备机试的阶段翻翻笔记比重新做题效率高得多——因为笔记里记录的正是自己最容易出错、最需要关注的盲区。4.4 适当挑战新平台的重要性以前我一直窝在一个OJ平台上刷题舒服是舒服但也容易产生依赖因为熟悉那个平台的题风和格式。今年我开始刻意去别的OJ刷题比如郑轻OJ、东方博宜OJ也会每周做一些华为OD风格的模拟题。这不是因为哪个平台更好而是因为不同平台的出题风格、边界设置、难度曲线差异很大多刷一个平台能让自己适应各种奇怪的题目包装方式这对临场机试的帮助是很大的。就拿华为OD机试风格的模拟题来说它们不考特别复杂的算法更多是考逻辑判断、字符串处理、模拟实现和信息组织能力。这种题在传统ACM OJ里其实不算主流但真到面试环节反而是很多人最头疼的。所以我现在的安排是周一、三、五以经典算法为主周二、四针对性做这种“业务逻辑题”周末再做一场完整的模拟赛。这种交叉训练能兼顾算法深度和工程思维的宽度。5. 下一步目标与训练计划调整5.1 专项加强树形DP和区间DP通过这段时间的刷题我发现自己对树形结构相关的DP还是比较薄弱。今天在洛谷看到一道树形DP题求树的最小点覆盖我第一反应是想用贪心结果反例一推就破。这种题在笔试里出现频率很高尤其和公司业务数据结合时经常被拿来当压轴题。未来两周我计划集中刷20道左右的树形DP题从最简单的“树上最大独立集”入门再逐步过渡到“树上背包”和“换根DP”。区间DP也同样需要加强虽然考的少但搞清楚它的套路对其他DP很有启发。我做专项训练的方法是“112法则”1天理解模板题的经典解法、1天不看题解默写思路、2天用同类题巩固。这个节奏不会太紧张又能保证每个知识点有足够的重复次数。很多知识点不是难是练得不够多练多了就自然形成肌肉记忆。5.2 手感保持每天至少保证一次完整提交这段时间因为临近机试我给自己定了一个硬规矩每天至少提交一次代码并且获得一个AC。题目难度可以不高但“当天有AC”这个状态要保持住。这样做有几个好处第一保持连续的做题手感不会出现休息几天后手生第二每天AC一道题会产生一种微小的成就感这种正反馈对长期坚持刷题非常重要第三它逼着我把零散时间用起来——比如排队打饭的间隙也能打开手机看一眼简单题。今天的15道AC就是从“至少一次”这个底线开始滚起来的。很多事情都是这样开始的理由很简单坚持的时间久了效果自然会显现出来。刷OJ不需要什么天赋异禀真正拉开差距的往往是做到“稳定、持续、总结”这六个字。今天写了这么多也算给自己过去一个阶段的努力做一个标记。如果你也在刷OJ的路上希望这份总结能带给你一些可以参考的细节和思路。我的经验是哪怕每天只AC一道题只要持续在做、在记录站在几个月后再回头看你会发现自己早就走完了一段不小的路。这也是今天“2026.3.5 OJ总结”最想留下来的一个观点。