CF1075复盘：从切比雪夫距离到排序+二分的算法竞赛解题思路-北京尧图网络

1. 先说说这场比赛CF 1075的难度定位与做题节奏Codeforces Round #1075Div. 2这场我印象挺深。它不算那种难到劝退的场次A、B题都属于“想明白就一行代码想不明白就绕远路”的典型div2开胃菜C题则是中段分水岭专门卡那些只会套模板、缺少题目定位能力的人。如果你刚入坑算法竞赛或者正在刷Codeforces的div2场次用来热身这场绝对适合拿来复盘。先说结论A题考的是棋盘上的步数建模本质是切比雪夫距离B题考的是排序、二分和“最近点匹配”的扫描思路这俩都是高频考点在LeetCode必刷基础算法题里也经常以变形形式出现。C题我不打算在这里硬编一个“原题面”来误导你而是想借这场的结构聊一聊div2中段题最常见的几个突破口怎么在赛场上快速判断一道C题该往哪个方向想。毕竟真正参赛的时候你需要的不是“背过某道题”而是“看到题就知道它在考什么”。我自己的做题习惯是前30分钟先稳定拿下A、B给C留出至少40分钟思考时间如果C题20分钟内没有明显思路就把草稿纸上列出的所有暴力/特殊性质全过一遍而不是干坐着盯题面。这场比赛正好适合用来练这个节奏因为它A题骗你模拟B题骗你贪心实际解法都很简洁过程里能踩的坑还不少。下面一道一道说。2. A题题解棋盘上的国王赛跑其实是一道切比雪夫距离2.1 题意复述与核心建模题目大意很简短一个 n×n 的棋盘白王从 (1,1) 出发黑王从 (n,n) 出发两王轮流走每一步可以移动到周围的 8 个格子之一现在给定一个目标格 (x,y)问谁先到达。白方先手。我刚看到这题的第一反应是写BFS或者模拟四方向跳跃甚至还有人会去想“两王会不会在中途碰面拦截”这种问题。实际上这就是个步数比较题因为两个国王互不影响谁先到谁赢根本不存在拦截。你只需要分别算出白王到目标的最少步数和黑王到目标的最少步数比较大小即可。关键点是步数怎么算。一个王从 (x1,y1) 走到 (x2,y2)横着、竖着、斜着都能走那么每走一步最多可以让横坐标差减少1、纵坐标差减少1。也就是说最少步数不是曼哈顿距离而是横纵坐标差的较大值这就是切比雪夫距离max(abs(x1-x2), abs(y1-y2))。把两个起点分别代入得到白王max(x - 1, y - 1)黑王max(n - x, n - y)因为每一步都可以斜着走所以横纵坐标是“同时被消耗”的谁剩得多谁就是瓶颈。生活化理解就是你从房间左下角走到右上角如果允许斜着穿房间那需要的步数不是“先横着走完再竖着走”而是“横竖同时推进”步数等于较长那条边的长度。这个点想通了A题就结束了。2.2 为什么用 long long以及一行判断的代码先上代码C17#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long n, x, y; cin n x y; long long white max(x - 1, y - 1); long long black max(n - x, n - y); if (white black) cout White\n; else cout Black\n; return 0; }这里的不是手滑是规则白方先手所以步数相同时白王先到输出 White。我见过有人在这里写成结果样例都过不了有点可惜。为什么要用long long而不是int虽然 cf 这类题 n 一般不会超过 1e9int理论够用但n - x这种表达式在极端边界上不会溢出真正的问题是“养成习惯”。很多div2 B/C题的中间运算远不止 2e9 这个量级你如果连这种入门题都习惯性开long long后面就不容易在溢出上翻车。我自己的模板里第一行就是#define int long long虽然被部分选手嫌弃但实测下来省心得多尤其是在跨平台评测环境里。2.3 这类题的易错点边界和“同时到达”的处理我自己第一次做这题时踩过一个很蠢的坑想当然以为黑王从右下角出发目标在右上角比如 n6, x6, y1白王要走max(5,0)5步黑王要走max(0,5)5步这时候因为白方先手所以输出 White。这个逻辑我一开始想反了以为“黑王更靠近右上角”结果样例都给我纠正了。所以提醒一下同距离时先手方赢不要凭感觉判断谁“看起来近”。另一个边缘情况是目标格就是起点本身。比如目标 (1,1)白王步数0黑王步数max(n-1,n-1)显然白赢。这题不会出这种阴间数据但你要在代码里保证max不会对负数求值因为输入一定在棋盘内所以x-1和n-x都非负没什么好担心的。总结A题就一句话用切比雪夫距离算两王步数比较时带上先手优势。写起来五分钟但想明白“为什么是最少步数而不是曼哈顿距离”才是这题真正留给你的东西。3. B题题解出租车司机和乘客排序二分一次搞定3.1 题意复述与算法思路B题是一道经典的“最近点分配”问题一条坐标轴上有若干出租车司机和若干乘客每个司机位置已知每个乘客位置已知乘客会选离自己最近的出租车如果距离相等则选择坐标更小的那辆在按坐标排序的前提下等价于选左边的司机。最后要求输出每个司机服务的乘客数。这题我在赛场上第一反应是“对每个乘客枚举所有司机找最近”但一看数据范围就知道不行。n 和 m 加起来能到 2e5暴力是 O(n*m)直接 TLE。正确做法是排序后二分读入所有坐标用第三行的类型字段区分谁是司机、谁是乘客。只把司机的坐标和编号存成pair坐标, 编号按坐标从小到大排序。遍历每个乘客坐标 p用lower_bound找到第一个坐标不小于 p 的司机位置it。候选司机只有两个it指向的右边司机以及it-1指向的左边司机。比较两边的距离左边距离更小或等于时选左边否则选右边。为什么只需要看左右两个司机因为在一条直线上最近的司机不可能跳过左边第一个司机去选更左边的也不可能跳过右边第一个去选更右边的。这个结论看起来是废话但真到了赛场上很多人会不由自主地想用“维护两个堆”或者“双端队列”等复杂方案其实完全不必要。我把这题归类为“排序二分”的典型模板题跟很多LeetCode基础算法题里的“最近位置匹配”一个套路。3.2 完整代码与细节解释#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorlong long pos(n m); for (int i 0; i n m; i) cin pos[i]; vectorint typ(n m); for (int i 0; i n m; i) cin typ[i]; vectorpairlong long, int taxi; vectorlong long pass; for (int i 0; i n m; i) { if (typ[i] 1) { taxi.push_back({pos[i], (int)taxi.size()}); } else { pass.push_back(pos[i]); } } sort(taxi.begin(), taxi.end()); vectorint ans(m, 0); for (long long p : pass) { auto it lower_bound(taxi.begin(), taxi.end(), make_pair(p, -1)); int best -1; // 右边候选 if (it ! taxi.end()) best it-second; // 左边候选 if (it ! taxi.begin()) { auto jt prev(it); long long dL p - jt-first; long long dR (it taxi.end() ? LLONG_MAX : it-first - p); if (dL dR) best jt-second; } if (best ! -1) ans[best]; } for (int i 0; i m; i) { if (i) cout ; cout ans[i]; } cout \n; return 0; }这里有几个容易写错的地方单独拿出来说。第一lower_bound(taxi.begin(), taxi.end(), make_pair(p, -1))为什么第二维传 -1因为pair比较时先比较第一维再比较第二维。我们要找的是“坐标不小于 p 的第一个司机”如果直接用make_pair(p, 0)万一有司机坐标正好等于 p且编号为 0会正常返回但为了稳妥传一个比所有合法编号都小的 -1可以确保lower_bound一定返回第一辆坐标不小于 p 的车而不是因为第二维比较越界到更后面的同坐标车辆。这个细节是我自己拍脑袋调试时发现的不写清楚很容易在坐标相同的数据上WA。第二dR的计算要防止空指针。当it taxi.end()时说明所有司机都在乘客左边右边没有候选此时把dR设成LLONG_MAX保证必然选左边。这个写法比单独判if (it taxi.end()) { ... } else { ... }更紧凑但你要理解为什么它不会出错。第三距离相等的处理。题目要求选坐标更小的司机也就是左边的司机所以判断条件是dL dR。如果你写成那么在等距情况下会错误地选右边司机答案直接错。这个等号是我在赛场上最容易漏掉的地方B题WA一次的人里有一大半都是栽在这。3.3 复杂度分析与另一种双指针思路排序需要 O(m log m)每个乘客二分一次需要 O(log m)总复杂度 O((nm) log m)。对于 nm ≤ 2e5 的数据量这个复杂度毫无压力。如果你用的是 Python二分照样轻松过别怕。除了二分还有另一种更“扫描线”的写法把乘客坐标也排序维护两个指针分别指向左右最近的司机然后线性扫一遍。这种写法常数更小但代码细节更多比如要处理“当前乘客移动后左指针能不能往右推进”的逻辑。我个人推荐先掌握二分版本因为思路更直白不容易在细节上翻车。双指针版本适合你在二分版本已经写熟之后再研究它对你理解“单调性”这件事有帮助但不适合作为赛场上第一次写B题的首选方案。4. 从A/B到C题div2中段题的通用突破口4.1 为什么C题才是分水岭很多刚上分的选手有个误区以为div2的C题一定需要什么高深算法。实际上C题的知识点往往还是前缀和、二分答案、双指针、贪心、构造这些基础内容难点在“识别”而不在“实现”。我在复盘1075这场的时候发现A题是“数学一眼题”B题是“排序二分板子题”那C题大概率就是在这两种基础上做文章要么把B题的数据结构再复杂化搞成区间查询、计数、配对要么直接跳到构造/思维题让你找规律。如果你在赛场上花20分钟还读不懂C题在做什么我一般会先问自己三个问题题目里有没有“最小化最大值”或“最大化最小值”这种字眼有的话基本是二分答案。题目是不是要统计满足某个条件的区间/子数组个数有的话基本是前缀和哈希表或者双指针。题目给的数据范围是不是特别大迫使你只能O(n log n)或者O(n)有的话基本是排序后贪心或扫描。这三个问题解决不了再看有没有特殊的数学性质比如奇偶性、倍数、二进制位。div2的C题再绕也逃不出这个范畴。4.2 以“数组划分”为例异步看二分答案的思考过程我随便拿一个div2 C题最常见的原型来说给你一个数组要求划分成 k 段让所有段的和的最大值尽量小。这是一道经典二分答案题但真正理解它的人并不多。二分的对象不是位置而是“答案”。你猜一个值 X然后从数组左边开始贪心累加一旦当前段的和超过 X就立刻开新段。如果能用不超过 k 段装下所有数说明 X 是个可行解可以把上界往下压否则说明 X 太小需要调大。整个过程 O(n log sum)非常标准。这题难在哪里难在“为什么可以二分”。因为“能不能在不超过 k 段的情况下让最大段和 ≤ X”这件事对 X 是有单调性的X 越大越容易满足X 越小越难满足。有单调性就能二分。很多C题你看着不像二分本质就是隐藏了单调性你只要把 check 函数写出来一切就豁然开朗了。这也是我建议刷题时多练“二分答案”类题目的原因它是性价比最高的C题突破口之一。4.3 扫描线思想的迁移再举一个例子数轴上有一堆区间问哪些点被覆盖次数最多。这种题的常规做法是差分数组区间左端点 1、右端点后面 -1最后前缀和扫一遍。用前面B题打下的“排序后扫描”基础你会发现这其实只是把“乘客选司机”换成了“区间增减”底层思维一模一样。所以我在复盘1075的时候有个很深的体会div2的A、B题不是独立存在的它们的解法往往就是C题的“零件”。你在写B题时用到的二分、排序、扫描、比较距离到了C题会原封不动地组合翻新。因此如果C题卡住不要急着去看题解先回头想想刚才B题用了哪些技巧能不能把它的框架套到C题上。这个习惯帮我至少在三场CF里救回过C题。5. 复现过程中的踩坑记录与检查清单5.1 我复现A、B题时踩过的真实坑第一坑是输入格式。B题第二行是 nm 个坐标第三行是 nm 个类型标记两者是一一对应的。我第一遍写的时候以为坐标就是“前n个是乘客后m个是司机”直接按位置取结果样例都过不了。后来才反应过来必须用第三行的类型字段来过滤。这个坑其实很普遍所以我说读题时一定要看“类型标记”和“坐标”是分两行给的别想当然。第二坑是pair的二分查找写错。我最早写的是lower_bound(taxi.begin(), taxi.end(), make_pair(p, 0))在坐标相同的边界数据上WA。后来改成make_pair(p, -1)才稳定。原因前面已经说了pair比较会看第二维-1能保证找到的是第一个坐标不小于 p 的司机。如果你用的是struct而不是pair记得自定义比较器时只比较坐标忽略编号效果也一样。第三坑是距离用int存。虽然坐标上限可能不大但减法p - jt-first一旦出现负数比如左边司机坐标大于乘客坐标结果会变成巨大的无符号数直接导致比较逻辑崩掉。最稳的写法是只在确定了“左候选确实在左边”之后才计算距离或者干脆全部转成long long再做减法。我后来干脆把所有坐标都声明成long long再也不纠结。5.2 本地测试与对拍建议频繁在CF上WA的选手一定要学会对拍。我自己在做这种排序二分题的时候会先写一个暴力版本然后写一个随机数据生成器把两个程序跑的结果对比。举例子B题的暴力就是遍历每个乘客寻找最近的司机数据范围小的时候完全可行。只要随机跑几十组你的二分版本有没有逻辑漏洞立刻现形。数据生成器不用写得多复杂核心就是生成随机坐标和随机类型然后输出到文件两个程序读同一个输入文件比较输出。这个过程在Linux下用几行脚本就能搞定Windows下也可以用命令行循环。你要是连本地编译环境都没有配好那就更应该先解决环境问题不然光靠提交评测去猜错误效率太低了。5.3 一份我压箱底的提交前检查清单我每次提交div2题目前会逐项过一遍这些问题变量类型是不是都是long long有没有可能溢出读入用没用ios::sync_with_stdio(false)和cin.tie(nullptr)二分查找的边界条件想清楚了吗it begin和it end两个分支都考虑了吗距离相等时选谁规则是还是输出格式对不对行尾有没有多余空格数组开够了吗vector的容量和下标访问是否可能越界这些检查看起来琐碎但实战里救过我不止一次。尤其是二分边界和等号选择属于那种“样例过了、提交WA”的典型元凶。CF的div2 A、B题数据量通常不大但边界数据又毒又狠你不想栽在这些地方。6. 赛后我习惯做的几件事每次打完一场CF我除了补题还会花半小时写点复盘笔记内容不限于题解还包括赛场上卡住的原因。比如这场1075我复盘时发现自己在B题上磨太久的原因是下意识想用“双优先队列”去处理最近司机结果越想越复杂直到重新读题才发现“只需要看左右两边”。这种“思维惯性”远比某个具体算法更值得记录。另一个我常用的技巧是给每道题在笔记里标注标签比如“A题切比雪夫距离先手判定”“B题排序二分等号细节”“C题方向二分答案/扫描线”。过两个月再翻出来看到标签就能快速回忆起整个思路框架。这种做法对我的rating提升帮助很大比盲目刷题有效得多。如果你也是刚接触Codeforces不久我建议你从div2的老场次复盘开始不要一上来就追最新比赛。老场次的题解多、讨论多你在网上搜的时候还能看到各路选手的奇葩经验和更简洁的写法。像1075这种场次A、B题拿来练基础C题拿来练“题目定位”性价比很高的。尤其提醒一句网上搜“1075”很容易搜到Windows错误码之类无关内容记得把关键词限定在“codeforces 1075”或者“CF Round 1075”再开始找题解不然会被干扰。我个人到现在还留着当年第一次切掉B题时用的那个二分模板每次遇到“最近点匹配”类问题都会先把它抄出来改造一下。刷算法题就是这样很多题看似不同骨子里共享同一套思维模块。你积累的模块越多赛场上就越从容这也是我写这篇复盘最想传达的东西。

CF1075复盘：从切比雪夫距离到排序+二分的算法竞赛解题思路

相关推荐

C++ auto关键字详解：类型推导原理、使用场景与避坑指南

wscript.exe丢失别乱下载！SFC和DISM免费修复系统文件

降AI率实战指南：从统计特征到人类化重写的正确路径

更多资讯

Python实现KMeans聚类算法：源码、数据集与实战避坑指南

激光雷达接收芯片选型实战：APD、SiPM与SPAD阵列对比

SpringBoot+Vue 项目申报管理系统源码实战解析

QwenPaw本地部署与调用指南：从安装到批量处理

Python+Twilio搭建短信通知系统，实现服务器监控与告警

基于S7-200 PLC与组态王的中小型污水处理控制系统设计与实现

今日更新

45个经典Linux面试题：从命令到网络排障的完整考点解析

SAP生产预留实战指南：MB21/MB23/MB25协同与MRP集成

编译原理实验：递归下降分析器消除左递归与避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？