每年新生赛系列赛里总有一两道题能让人在赛后复盘时反复回味。第二场那题《谍战风云》就是其中之一题目本身不是系列里最难的但它把“特工送情报、敌方拦截”这个背景包装得相当有迷惑性很多人一看以为是图论搜索或者复杂模拟结果把自己绕晕了。这篇复盘写给当时参赛的新生也写给带新人的同学以及所有想练建模能力的刷题者。这题实际上要解决的事情非常朴素给定一条路线、双方固定的移动步数和视野半径判断我方特工在最优走法下能不能安全抵达目标点。难点不在算法模板而在把谍战故事翻译成数学模型。下面我按照当时赛后复盘的顺序来写先拆题再聊暴力模拟为什么超时接着给出正解推导最后把提交时踩过的坑和题目变形一并整理出来。1. 拆解《谍战风云》先搞清楚题目到底在问什么1.1 去掉故事外壳之后的输入输出比赛时很多同学读完题就懵了因为题目给了大量背景描写某特工携带机密情报要从安全屋出发穿过敌方封锁线敌方守卫在另一侧巡逻双方都在暗处行动一旦进入对方视野范围就会被发现。文字写得像短篇小说但剥干净之后核心就是下面这个模型。我方起点设为坐标 0目标情报点坐标为 L敌方守卫初始站在 L 附近双方沿同一条一维直线相向移动。规定我方每个回合向前走 a 米敌方每个回合向前走 b 米双方走完之后如果二者距离小于等于视野半径 k则我方暴露任务失败。若我方能够抵达 L 点任务成功。读入就是四个整数目标点距离 L、我方步长 a、敌方步长 b、敌方视野半径 k。输出任务能否成功是则输出 Yes否则输出 No。需要说明的是这道题不同学校流传的版本细节可能略有差别有的版本要求“送完情报再撤回起点”有的版本把敌人设定成固定岗哨。但无论外壳怎么换核心就是一条直线上的相对距离变化理解这个模型其它版本都能迎刃而解。1.2 数据范围决定思路方向数据范围是出题人最温柔的提示。如果题目给定 L 在 1e9 级别a 和 b 通常远小于 L那么几乎所有选手的第一反应——用一个 while 循环逐回合模拟移动——都会在极限数据面前崩塌。1e9 除以单次移动距离最坏情况可能需要跑 1e9 个回合再乘以多个测试用例暴力解法根本没有生存空间。反过来数据大到不能用循环处理时基本可以断定出题人希望选手从“每回合状态都在变化”这件事里跳出来去观察状态变化的规律。换句话说要找一个不用一步步走就能直接算答案的数学关系。新生赛里出现这种思路非常正常它不考高级数据结构考的就是最基础的数学建模能力。1.3 哪些细节容易被忽略新手最容易漏掉的细节有两处。第一双方是同时走还是轮流走。很多题目描述里写的是“双方每回合各行动一次”这时统一按一个回合结束后双方距离减少 (a b) 来处理就可以。第二视野半径 k 是“小于等于”还是“小于”题目里通常会用“距离不超过 k 即被发现”这种表达对应的是小于等于。这两个细节如果看错公式写出来就会差一点点偏偏 OJ 的测试数据就把这种差一点点卡得很死。我在当时复盘时跟新生说读题的前三分钟不要碰键盘先把题面里的动作场景翻译成数学对象翻译完再想算法。这一步看似浪费时间实际是最快路径。2. 暴力模拟为什么走不通从超时现场看复杂度的杀伤力2.1 第一反应while 循环把每个回合走一遍正常选手看到“移动、判断距离、再移动、再判断”这种描述第一反应就是模拟。伪代码大概是下面这样while (我方还没到达目标 距离大于 k) { 我方移动 a 米 计算双方距离 如果距离小于等于 k任务失败 敌方移动 b 米 计算双方距离 如果距离小于等于 k任务失败 回合数加一 }逻辑看起来无懈可击样例也轻松通过因为样例里 L 很小跑几十个回合就出结果了。于是很多同学信心满满交了第一版心里想着这题稳了。2.2 能过样例却过不了大数据问题出在极端数据上。假设 L 是 1e9a 和 b 都是 1k 是 0那 while 循环要跑接近 5 亿次才能让双方距离缩减到 0 并判定失败。5 亿次简单运算在 C 里大约需要一两秒看着还能扛但题目往往不止一组测试数据一旦来上几十组 1e9 规模的数据总运算次数轻松突破百亿级别超时就是板上钉钉的事。有同学会想我让循环早停不就行了敌方和我方相向而行每回合距离都在减少确实可以提前退出。但这个“提前退出”的回合数仍然与 L 同数量级L 取 1e9 时依然要跑几亿次。更麻烦的是有些测试点里 L 巨大但 a 也很巨大模拟很快就结束了有些测试点则精心构造了每一步都很小、需要走到天荒地老的场景。OJ 构造数据的人不会让你舒舒服服跑完的。2.3 从超时倒推这题想让你用除法看一下每一回合结束后的距离变化规律我方走 a敌方走 b双方距离一次性减少 (a b)。这个减少量在整道题里是恒定不变的。既然每一步减少量固定那么“经过多少回合后距离会小于等于 k”就不再需要一步步数直接用除法就能算出来。这就好比你去凑满减活动满 99 元减 50手上有面值 20 元的优惠券你不会真的拿 20 元一张一张加到购物车去数而是直接用 99 除以 20向上取整就知道需要几张券。题目里的循环模拟就是那张一张数券的笨办法除法公式才是真正想让你发现的东西。暴力模拟没有错它只是把可以一步算出的答案拆成了无数次重复加法。看清这一点正解就呼之欲出了。3. 正解推导把循环换成公式3.1 先算“到达回合数”再算“暴露回合数”成功条件可以拆成两个时间点的比较。第一个时间点是我方抵达目标需要的回合数记作 need。第二个时间点是双方距离首次收缩到 k 以内的回合数记作 expose。如果 need 不超过 expose说明我方能在被发现之前到达目标任务成功否则任务失败。到达回合数很好算总路程 L每回合走 a 米需要向上取整的 L / a 个回合也就是need ⌈L / a⌉ (L a - 1) / a暴露回合数同样直接算。初始双方距离为 L每个回合结束后距离减少 (a b)设这个净减少量为 s。经过 t 个回合后剩余距离为 L - t * s暴露条件是剩余距离小于等于 k也就是L - t * s k移项得到 t 的最小值t (L - k) / s因为回合数必须是整数所以向上取整expose ⌈(L - k) / s⌉ (L - k s - 1) / s注意上面的 L - k 必须是正数才能套用向上取整公式所以初始距离 L 小于等于 k 的情况要单独判掉——起跑线就在敌人视野里这仗没法打。3.2 完整代码代码极短但每一步都对应上面的公式推导建议没看过推导的同学先理解再抄。我的习惯是比赛时顺手把三种边界都写上L 等于 0 直接成功a 小于等于 0 直接失败初始距离小于等于 k 直接失败。#include bits/stdc.h using namespace std; typedef long long ll; int main() { ll L, a, b, k; while (cin L a b k) { if (L 0) { cout Yes\n; continue; } if (a 0) { cout No\n; continue; } if (L k) { cout No\n; continue; } ll s a b; // 每回合相对距离的净减少量 ll need (L a - 1) / a; // 到达目标所需回合数 ll expose (L - k s - 1) / s; // 暴露回合数 if (need expose) cout Yes\n; else cout No\n; } return 0; }需要注意当敌方步长 b 为 0 时公式依然成立敌方站桩不动每回合相对距离仍会减少 as 就等于 a没有任何除以零的风险。只有当 a 也为 0 时双方彻底静止才需要特判。3.3 为什么必须向上取整向上取整是这道题最容易讲不清的点。拿到达回合数来说如果我方距离目标 10 米每回合走 3 米那么第 3 回合走到 9 米第 4 回合走到 12 米。严格说在第 4 回合移动的过程中就已经抵达了目标点所以需要 4 个回合而不是 10 除以 3 得到的 3.33。算式 (L a - 1) / a 就是手动实现“除不尽的都进一”。暴露回合数同理。如果算出来 t 等于 2.1那意味着第 2 回合还没暴露第 3 回合才会暴露所以最小暴露回合数是向上取整后的 3。换句话说向上取整是在找“第一次满足条件”的整数时间点。3.4 一个随手验证的小例子拿 L 10, a 3, b 2, k 1 来手工验证。need 4s 5expose (10 - 1 5 - 1) / 5 13 / 5 2。意思是第 2 回合后双方距离就小于等于 1而我方要第 4 回合才能到显然任务失败。再拿 L 10, a 5, b 1, k 1。need 2s 6expose (10 - 1 6 - 1) / 6 14 / 6 2。第 2 回合我方刚好到达目标第 2 回合结束双方距离也进入了视野范围但到达先发生任务算成功。这类“同归于尽但先完成任务”的边界情况不同题目的判定可能不同提交前必须看清题面要求。4. 提交现场的真实状况测评结果教会我的事4.1 把 int 当 long long 用新生第一节课就讲 int 范围但真到比赛里看到 1e9 就条件反射用 int 的人太多了。L 是 1e9a 和 b 也都是 1e9 时L - k 加 s 再减一的结果是 2e9 左右已经顶到 int 上限边缘再加几个测试用例的累积就很危险。这题只要顺手写 long long就永远不会因为溢出错掉代价只是多打几个字符。赛后我问了几个提交失败的选手不少人的日志里都出现过莫名其妙的负值那就是 int 溢出后的典型表现。4.2 判定方向写反还有一类错误很隐蔽公式对着呢边界也处理了但 if (need expose) 输出 Yesif (need expose) 输出 No整段逻辑全部反了。这通常是因为脑子里先想的是“什么时候失败”写代码时却直接套了“成功输出 Yes”的框架两个时间点的大小关系就写反了。自检办法很简单拿样例手推一遍把 need 和 expose 的数值代进去人脑模拟一次输出再和 OJ 样例结果对比。样例数据设计得非常善意推导一遍就能抓住逻辑方向的问题。如果连样例都过不去就不要再怀疑编译器了回头检查比较符号。4.3 忽略了“初始就暴露”的测试点L 小于等于 k 的时候我方刚出发就在敌方视野里任务直接失败。很多同学的代码里完全没有考虑这个分支因为样例里 L 一般比 k 大很多样例不会暴露这个漏判。但只要测试数据里出现一个 L 5、k 7 的用例代码输出就和标准答案不一致。凡是涉及区间或距离判定的题我都会在写完核心逻辑后下意识问自己一句初始状态满足结束条件怎么办这个习惯能救回不少分数。4.4 多组测试数据的残留问题题面没有明说但实际上多数 OJ 题都是多组输入用 while (cin ...) 循环读。有的同学在循环外面定义了变量或者用一个全局数组保存中间结果下一组数据进来时没清干净就会出现“上一组的结果影响下一组答案”的灵异事件。解决思路很简单循环体内部的变量尽量局部化每次从输入重新读入不依赖任何上一次的状态。4.5 对拍暴力模拟与正解互相验证赛后我建议所有新生做一件事把最开始的 while 循环暴力版保留下来和正解公式版放到一起然后写一个随机数据生成器生成一万组小数据让两个程序分别跑看结果是否有差异。这就是最朴素的对拍。for i in $(seq 1 10000); do echo $((RANDOM % 100)) $((RANDOM % 10 1)) $((RANDOM % 10)) $((RANDOM % 10)) input ./brute input out_brute ./smart input out_smart if ! diff -q out_brute out_smart /dev/null; then echo 找到差异数据 cat input break fi done对拍能在一分钟内找出你压根没想过会错的边界用例。我当时就靠对拍抓到过 k 为 0 时的整除边界问题这是只靠人脑测试很难发现的东西。5. 赛后变式谍战风云还能怎么考5.1 版本一要求送达后返回起点有的版本里任务不只是送到目标点还要带着情报撤回起点。这时候需要走的路线从单程变成往返总路程从 L 变成 2L到达回合数直接替换成 need (2 * L a - 1) / a。暴露回合数的公式完全不变因为暴露只取决于双方相对距离的缩短速度跟我方是否折返没有关系。比赛时如果发现读题读慢了看到“返回”两个字也别慌无非是多算一段路的回合数。5.2 版本二敌人从后方追击而不是迎面拦截把方向改成同向追击后模型从“相向而行”变成“同向追赶”。此时双方距离的变化量不再是 a b而是敌方步长与我方步长的差值。如果敌人跑得比我方快每回合距离净减少 (b - a)如果敌人追不上那距离永远在拉大任务必然成功。这个变式的本质是高中物理里的追及问题核心提醒只有一句先判断相对运动方向再决定公式里的减号该长在哪。5.3 版本三地图出现岔路当一维变成二维地图多出可选择的路径时问题性质就变了。每条路径都有长度每条路径上也可能有不同的敌人巡逻参数选择一条能避开敌人的路本质上变成了最短路或动态规划问题。从《谍战风云》这种“一条直线走到黑”的题升级到岔路版本刚好是新生从入门数学题走向图论算法的第一步。很多同学觉得进阶难其实难的不是算法本身而是没有意识到学过的公式和套路都是同一套抽象思维的产物。5.4 对后续学习路线的启发赛后复盘时我反复跟新生强调一个判断标准看到数据范围是 1e9先把思路从“循环”切换到“公式”再从“模拟”切换到“推导”。这不是经验主义而是出题人用数据范围传达的潜台词。学算法不等于背模板真正的能力是把“重复动作”压缩成“一个算式”把“每回合都变”的理解成“每回合按固定规律变”。谍战风云这类题最好的地方就在于它用一层薄薄的剧情包装逼着你完成一次从过程到公式的抽象。那次复盘之后我一直跟新生说能一眼看穿题目包装的人不是他刷题多而是他习惯先找不变量。《谍战风云》里唯一的不变量就是每回合双方距离的净减少量找到它这道题就从小说变成了除法。下次再看到任何“谍战”“追逐”“封锁”背景的题不妨先问自己一句这里有没有一个每回合都固定变化的东西如果有答案多半就藏在那道除法里。