收到复赛通知的那天晚上我盯着屏幕上的“时间黑客”四个字看了很久。这个比赛的名字起得挺妙——初赛刷掉一批人之后能走进复赛的选手几乎没有谁不会写最短路径和动态规划。但真正拉开差距的恰恰就是“时间”本身你能不能比对手更快看懂题意能不能在罚时和暴力分之间做出正确取舍能不能在一道题卡住四十分钟后果断放手。说白了时间黑客大赛比的不是谁会写代码而是谁能在有限时间里把正确率、覆盖率和稳定性同时调到最优。我参加的是线上赛区的复赛赛制是三个半小时六道题覆盖图论、动态规划、贪心、数据结构外加两道偏建模的题。这篇文章把我这次复赛的完整复盘写下来包括题目思路、代码实现、踩坑记录以及我在赛前整理的一套通用打法。无论你是准备参加下一届比赛还是单纯想提升竞赛实战能力这篇内容应该都能给你一些参考。1. 复赛整体赛况与考察方向拆解1.1 赛制回顾与六道题分布先说说整体赛制。线上复赛统一在评测平台上进行三个半小时A到F六道题每道题分值相同但难度差异很大。测试点分为若干组部分题目设置子任务通过小数据规模的简单版本也能拿到20%到40%的分。这个设计很关键它决定了复赛的底层策略其实不是“每道题都AC”而是“在有限时间内最大化总分”。复盘一下我自己的时间分配。A题是签到题数组操作模拟15分钟通过。B题是带时间表的地铁换乘写了1小时才AC中间WA了两次。C题是区间调度变种35分钟AC。D题是二维网格上的时间窗口BFS做了1小时10分拿了70%的分。E题是动态规划优化最后40分钟拼了一个朴素O(n²)过了30%的测试点。F题直接放弃看了一眼题目就知道是网络流短时间内写不出来的那种。这个成绩不算顶尖但足够晋级下一轮。我想说的重点是如果你把目标定成“每道题都要AC”这场比赛一定会打崩。正确策略是“保A争B拿满暴力分留时间检查”。1.2 “时间黑客”这个命题到底在考什么比赛名字里的“时间”有两层含义。第一层是字面意思。复赛多道题目都带着明确的时间维度比如真实班次表、截止时间、时刻限制、时间窗口。这类题考察的是你如何建模“随时间变化的系统”。最典型的就是B题边的权重不是固定的你到达一个站点后必须等下一班车所以从u到v的代价取决于你到达u的时机。第二层是Meta含义。比赛本身就是一场时间博弈。算法竞赛圈对这类能力有个说法叫“赛时时间管理能力”这不只是说“你敲代码快”而是你会不会给每道题合理分配时间预算。很多选手死在一种典型情况里B题写了一个小时调不出来不甘心继续死磕结果后面三道题连看题的时间都没有。我在比赛时见过很多人在最后半小时疯狂提交、疯狂罚时就是这种心态崩盘的表现。所以这篇文章的题目“寻找时间黑客”实际上是两件事怎么解时间类算法题以及怎么做好自己在这场限时游戏里的策略管理。2. “时间”类题目的核心解题模型2.1 带时刻表的最短路问题B题我记得很清楚。题目大意是城市有n个地铁站、m条线路每条线路有一组发车时刻表你从某个站出发知道每条线路在哪些分钟发车坐完这条线路到达下一站需要一定时间问最早几点能到达终点。n的规模是几千时刻表总长度也不小。这道题的本质是单源最短路但边权不固定。你到达某个站点后必须等待下一班车所以“从u到v的代价”取决于你到达u的时刻。这个动态边权就是核心考点。做法是把Dijkstra中的dist定义成“到达某个站点的最早时刻”松弛的时候不再是dist[v] dist[u] w而是dist[v] nextDeparture(dist[u], route) travelTime。下面是简化版的代码#include bits/stdc.h using namespace std; struct Edge { int to, travel; vectorint dep; // 发车时刻列表升序 }; int main() { int n, m, start, target; cin n m start target; vectorvectorEdge g(n); for (int i 0; i m; i) { int u, v, t, k; cin u v t k; Edge e; e.to v; e.travel t; for (int j 0; j k; j) { int x; cin x; e.dep.push_back(x); } sort(e.dep.begin(), e.dep.end()); g[u].push_back(e); } const int INF 1e9; vectorint dist(n, INF); priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; dist[start] 0; pq.push({0, start}); while (!pq.empty()) { auto [curTime, u] pq.top(); pq.pop(); if (curTime dist[u]) continue; for (auto e : g[u]) { auto it lower_bound(e.dep.begin(), e.dep.end(), curTime); if (it e.dep.end()) continue; // 当天没有车了 int depart *it; int arrive depart e.travel; if (arrive dist[e.to]) { dist[e.to] arrive; pq.push({arrive, e.to}); } } } cout (dist[target] INF ? -1 : dist[target]) endl; return 0; }这里有几个细节值得展开。Dijkstra用优先队列按最早时间出队这很自然因为每次取出的都是当前已知最早到达的站点最先弹出的站点不会再被其他路径更新得更早。lower_bound是核心操作。它在一组升序发车时刻里找到第一个不小于当前到达时间的班次。这比你手动循环扫描快得多时间复杂度从O(k)降到O(log k)。我第一次WA就是因为没排序、直接线性找下一班车在时刻表长度为10^5的测试点上直接超时。关于“当天没有车了”的处理这道题里可以直接continue因为所有线路都是按当天班次给的错过末班车说明这条线路不可用。有些题会设置跨天运行比如地铁开到第二天凌晨那时要把发车时间加1440分钟再取模dist要按绝对时间计算而不是只算当天时刻。我建议比赛时优先把“跨天”情况考虑到宁可多写几个if也不要等WA了再补。2.2 截止时间与“最多完成任务”贪心C题是一个经典的任务调度问题有若干任务每个任务有截止时间deadline和所需时长duration一次只能做一个任务求最多能完成多少个任务。贪心策略是把所有任务按截止时间排序用一个小根堆维护当前已选任务的时长。每加入一个新任务时先把它的duration放进堆里累加总耗时如果总耗时超过了当前任务的截止时间就弹出耗时最长的那个任务。这个做法的核心思想是在完成同样数量任务的前提下尽可能减少总耗时为后面的任务留出更多空间。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorpairint,int tasks(n); // first deadline, second duration for (int i 0; i n; i) { cin tasks[i].second tasks[i].first; } sort(tasks.begin(), tasks.end()); priority_queueint pq; // 大根堆存已选任务的耗时 long long total 0; for (auto [deadline, duration] : tasks) { pq.push(duration); total duration; if (total deadline) { total - pq.top(); pq.pop(); } } cout pq.size() endl; return 0; }为什么按截止时间排序因为如果你先处理截止时间晚的任务后面截止时间早的任务可能就来不及做。而先处理截止时间早的任务万一有冲突可以通过“踢掉耗时最长任务”的方式保证总数最优。这道题我AC得很快原因很俗——赛前我刚好背过这个模型。算法竞赛里很多题是“模型题”你见过这个模型10分钟就能秒掉没见过就得从头推导一小时。所以我要给一个非常实际的建议赛前多刷近两年的区域赛原题重点不是刷难题而是刷“模型识别能力”。看到“截止时间 最多完成数量”这个组合就应该条件反射地想到堆贪心。还有一类变种值得注意如果每个任务还带有权重问题就变成了“在截止时间内最大化总权重”那就不能用普通堆贪心解决了通常需要排序后做动态规划。如果数据范围是n≤2000DP是正解如果n≤10^5还要观察题目有没有其他特殊约束。2.3 时间维度上的BFS与状态压缩思路D题是个带时间窗口的网格搜索题地图里有“安全区”和“危险区”危险区只在特定时间开放你需要在限制时间内从起点走到终点。BFS需要带上时间维度。最直观的做法是开一个三维数组dist[x][y][t]记录每个坐标在每个时刻的最早到达时间。但如果地图是1000×1000时间上限是10^5直接开三位数组内存就炸了。我当时的优化思路是因为危险区的开放时间是周期性的可以记录每个格子的开放周期然后用dist[x][y]记录最早到达时间。每次尝试进入一个格子时用当前时间和格子周期的关系判断此时是否可进入。这样状态从三维压缩成两维内存占用直接降了一个数量级。这类“时间维度过大无法直接开数组”的题目有一个通用判断顺序时间维度是否能压缩成周期如果能用“当前时间 % 周期”判断状态。是否只关心最早到达时间如果是可以用dist[x][y]一维压二维。时间是否单调递增如果BFS过程中时间只会增加可以按“时间从早到晚”的顺序逐层扩展避免用优先队列。这种压缩思想不只用于BFS在很多动态规划问题里同样适用。DP中经常有“状态数量 位置 × 时间”的题目时间维很大时可以先看能不能把某一维设计成“值”而不是“下标”比如用dist[x]表示“到达x所需的最短时间”而不是用dist[x][t]表示所有时间点的状态。3. 如何在有限比赛时间内拿最高分3.1 我的做题顺序与时间预算表进比赛第一件事不是看题而是把所有题快速读一遍。我给自己做了一张时间预算表时间段动作目标0-15分钟全部题读一遍确认每道题的数据范围标记“能写”“能暴力”“先跳过”15-30分钟搞定签到题A题稳定拿基础分30-90分钟主攻性价比最高的B题套路题必须AC90-150分钟换一道套路题C题争取AC150-210分钟冲刺有暴力分的题D题拿部分分最后20分钟全面检查已提交代码防罚时不要写新题有人会问为什么不先做最难的题拿高分因为线上赛所有题分值相同AC一道难题的时间够你写好几个暴力分。简单题AC靠一次通过难题的提交往往伴随着罚时——每WA一次加20分钟罚时最后排名靠后基本就是被罚时拖垮的。我实际执行时略有偏差B题多花了一些时间导致E题只剩40分钟。这个偏差提醒我即使有了预算表也要在“超过预算10分钟还没AC”时果断止损。止损的方式不是直接放弃而是先写一个保证能过小数据的暴力版提交至少把部分分抓在手里再回头想正解。3.2 二分答案快速拿下“可行解判断”题复赛里有多道题可以用二分答案的方式切入。这类题的共性是问题是“求最大/最小可能值”并且给定一个候选答案后判断它是否可行非常快。判断到这种题型后套路很清晰确定答案范围一般是0到某个最大可能值。写一个check(x)函数返回当前取值是否可行。用二分法逼近答案。bool check(int x) { // 具体判断逻辑O(n) 或 O(n log n) } while (l r) { int mid (l r 1) / 2; if (check(mid)) l mid; else r mid - 1; } cout l endl;二分的细节在于mid的取整方向和l、r的更新方式。我习惯用mid (l r 1) / 2配合l mid来求“最大可行答案”用mid (l r) / 2配合r mid来求“最小可行答案”。这个看起来琐碎但写错会造成死循环或者漏掉边界值初学者最容易在这里栽跟头。C题其实也可以用二分答案二分“最多能完成多少任务”然后在check里判断前mid个任务能否都被安排。但堆贪心的复杂度更优所以当时没走二分这个分支。我之所以对二分这么敏感是因为它几乎不依赖特定模型只要问题满足“可行解单调”就能套。这在比赛里是一个非常可靠的保底策略。3.3 暴力分是比赛里的战略储备我反复强调子任务的重要性。复赛很多题测试点里都有n≤20的小数据组这种规模下直接枚举子集、全排列、BFS搜索都能过。我给自己定了一个硬规矩每道题在没有满分解时先想清楚“暴力版能不能在10分钟内写出来”。如果能就先写暴力版提交拿保底分再继续冲正解。这样做有两个好处一是心态稳手里有分了想正解时不会慌二是有暴力版当对拍器正解写完后可以随机生成小数据用暴力输出和正解输出做比对快速定位错误。D题我当时就是先写了一个不带时间压缩的暴力BFS通过了30%的小数据测试点然后才逐步优化成带状态压缩的版本。这个过程虽然多花时间但每一步都有明确交付物不会出现“写了一小时最后全部WA”的局面。4. 复赛现场踩过的坑与Debug方法论4.1 本地能跑、提交WA的几个隐形杀手B题我WA了两次。第一次是lower_bound用错前面已经说过。第二次是整数溢出。当时n的最大值是10^5所有时刻数据累加后可能超过int的范围。这类问题如果你不在一开始就用long long就只能等着debug到比赛结束。我整理了一份高频踩坑清单几乎每次比赛都用得上症状常见原因排查方法本地AC、提交WA数组大小开小越界访问核对n上限与数组长度输出异常大或为负数int溢出累加量统一用long long偶尔TLE死循环或递归栈溢出检查二分边界和递归深度部分测试点WA初始化位置不对确认每组数据dist/vis都重置多组测试数据时如果把初始化放在读数据之前而后一组数据的n更小上一组残留的值就可能污染答案。比赛时我习惯在while(T--)内部的开头把所有要用的数组重新fill一遍宁可多花一点点时间也要保证每组数据都是全新状态。4.2 在线评测系统的输入输出细节线上赛的评测系统对输入输出格式要求很严格。多一个空格、少一个换行通常不会判错但遇到格式敏感的场景还是要按样例精确输出。输入数据很大的时候建议用快速输入输出不要用cin/cout的默认同步模式。我自己的模板里常备快读函数static inline int read() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; }说句实话大部分时候cin加上sync_with_stdio(false)就够用了。快读模板是用来应对极端数据的最后一张底牌平时写熟了比赛时直接调用不占用思考带宽。4.3 对拍程序证明自己的解法不是“运气AC”赛后复盘或者赛时排错的时候我都强烈推荐写一个对拍器。流程很简单写一个数据生成器随机生成小规模输入。用你的正解跑一次用暴力解法跑一次。比对输出如果不同就说明找到了正解的反例。这一招在比赛进行中同样能用。如果正解写完但一直WA花5到10分钟把暴力版写出来随机生成几万组小数据十有八九能找到一组让正解出错的数据。根据这组数据定位逻辑错误比盯着代码干瞪眼效率高一个数量级。D题我后期就是用对拍器发现了一个边界条件当起点格子在危险区且开放周期刚好是0的时候我的判断逻辑会误判为不可进入。这个情况非常隐蔽单靠手推测试数据很难想到但随机生成器一秒就能发现。5. 三个半小时赛时的节奏和心态控制5.1 卡题40分钟后的止损策略这次复赛我在D题上卡的时间比预想长。中间有一度很想继续死磕但理智告诉我如果一道题想了40分钟还没有明确思路就该主动降级——要么写暴力要么直接跳过进入下一题。算法比赛最怕的不是“不会做”而是“觉得会做但做不出来”的题。这种题最消耗时间因为你总觉得自己再想一会儿就能突破但实际很可能是在赌。我的判断标准是如果40分钟内既没有写出一个稳定通过的算法也没有写出一版可运行的暴力代码说明自己对这个模型的掌握程度确实不足继续投入的期望收益很低。实际情况是我跳过了D题正解先去把E题的朴素DP写了出来拿下了30%的部分分。之后再回头用状态压缩优化D题反而因为在E题上换了一下脑子思路突然清晰了最终把D题从30%提升到了70%。这个反转很能说明问题暂时跳出去不是放弃而是给大脑一个重新组织信息的机会。5.2 赛前15分钟的准备工作进比赛前几分钟我有固定的准备工作把编译器语言环境调好模板代码准备好快读、常用头文件、取模运算等。把“心理清单”过一遍先读全部题、按难度排序、保暴力分、控制罚时。确认好时间节点比如第一个小时结束前必须至少有一个AC。这些看似和算法无关的细节实际直接影响你能否在高压下把水平发挥出来。模板准备好意味着不用现场敲那些固定代码减少不必要的低级错误心理清单则是防止自己一紧张就乱了节奏。另外一点是比赛前夜不要刷难题。我一般只做几道手热题难度控制在“一眼能看出思路”的老题目的是保持手感不是学新知识。新知识留给赛后复盘去学赛前临时抱佛脚只会增加焦虑。6. 赛后复盘与后续训练建议6.1 复盘时看的不是答案是知识缺口赛后我把六道题全部重新做了一遍。F题其实是一个标准的最小费用最大流模型我当时没做出来只是因为模型储备不足不是能力问题。所以复盘最重要的不是把题目AC掉而是给知识缺口定位。我习惯用一张表记录题目考点我的状态缺口类型A模拟AC无BDijkstra变体WA 2次后AC细节控制C贪心堆AC无D时间维度BFS70%部分分状态压缩EDP优化30%部分分模型储备不足F最小费用最大流0%知识盲区这样下一阶段训练方向就很明确先补斜率优化DP再做网络流基础题最后多刷带时间窗口的搜索题。每一类针对性训练两三天效果远好于漫无目的地刷题。6.2 把比赛节奏练成肌肉记忆最后分享一个我长期在用的训练习惯每周固定做一场完整的模拟赛严格按竞赛时间计时结束后写复盘。模拟赛的关键不是找难题虐自己而是练“时间分配的直觉”。练多了之后看到一道题大概几秒内能判断出它的暴力分是否好拿、正解方向是否清晰、值不值得投入。这种判断力在正式比赛里比任何一招具体的算法都值钱。时间黑客大赛这个名字很有意思它提醒我代码能力到达一定阈值后比赛胜负手往往在于“能不能在正确的时间做正确的取舍”。真正的高手不是把每一秒都压榨干净而是把每一秒都花在回报率最高的地方。这个道理不只是适用在比赛里做项目、写业务代码、甚至安排日常工作都是同一个逻辑。