1. 项目概述与核心价值最近在准备华为OD机试的朋友尤其是目标C岗位的应该都听说了今年2025年机考系统的一个重大变化双机位监考。这个变化直接让很多传统的“刷题”和“背答案”策略失效了对考生的真实编程能力和临场应变能力提出了更高要求。我最近刚带几个学员复盘了一套据称是2025年A卷的真题——“敌情监控”感触颇深。这道题本身算法难度属于中等偏上但在双机位的新环境下如何稳定、高效地实现并规避各种潜在的扣分点就成了新的挑战。简单来说“敌情监控”这道题是一个典型的图论搜索与动态规划结合的问题场景设定通常与监控覆盖、资源调度相关。它考察的不仅仅是你能不能写出一个能跑通的DFS或BFS更考察你在时间压力下代码的健壮性、可读性以及边界条件处理的完备性。因为双机位意味着你的屏幕和周围环境都被实时监控任何卡壳、频繁调试、甚至因为紧张而写出混乱代码的行为都可能被记录并影响评分。这篇文章我就以这道“敌情监控”题为蓝本结合C实现来深度拆解一下在新机考模式下我们应该如何备战。我会从题目本质解析、双机位环境下的编码策略、完整的C实现与逐行注释以及最重要的——临场避坑指南这几个方面把我知道的干货都倒出来。无论你是第一次接触华为OD机试还是老手面临新规相信都能从中获得直接的帮助。2. 题目“敌情监控”的本质与算法拆解首先我们得抛开题目那层“军事化”的外衣直击它的算法内核。根据常见的题型描述“敌情监控”问题通常可以抽象为以下模型问题抽象在一个N x M的网格区域中存在若干监控设备源点和若干需要监控的目标点敌情点。每个监控设备有一个特定的监控范围比如可以覆盖自身所在行和列或者以其为中心的曼哈顿距离R以内的区域。目标是判断现有的监控设备是否能覆盖所有目标点如果不能则需要计算至少还需要新增多少个监控设备假设新增设备监控范围相同才能实现全覆盖。这立刻让我们联想到两类经典算法图的可达性分析搜索将网格视为图监控设备的覆盖范围就是从这个点出发能遍历到的所有节点。我们需要检查每个目标点是否至少被一个监控设备“访问”到。集合覆盖问题贪心/回溯当需要计算最少新增设备时这变成了一个典型的“集合覆盖问题”的变种。这是一个NP-Hard问题但在机试限制下N和M以及目标点数量不会太大通常允许使用回溯法DFS或者基于特定策略的贪心算法来求解。核心难点解析覆盖规则的实现如何高效地计算一个监控点能覆盖哪些格子直接嵌套循环遍历整个网格再判断距离是最直观但效率最低的。更优的做法是预先根据规则如曼哈顿距离生成一个“覆盖偏移量”模板或者使用BFS/DFS从监控点开始进行有限步数的扩散。状态压缩与去重目标点可能很多。在判断覆盖和计算最少设备时我们需要一种高效的方式来表示“哪些目标点已经被覆盖了”。常用的技巧是位运算Bitmask如果目标点数量K 20甚至30取决于数据类型我们可以用一个整数的每一位来代表一个目标点的覆盖状态。这能极大提升DFS回溯的效率。双机位下的思维显化你不能再像以前一样脑子里有个模糊思路就开始闷头写调试半天。你需要非常清晰地将问题分解为几个模块并且让代码结构反映出你的思考步骤。这会让你的代码在监控视角下显得逻辑清晰即使最终没有完全AC也能展示出良好的问题分析和解决能力。3. 双机位环境下的C编码策略与准备双机位考试第一个机位是你的电脑屏幕第二个机位通常是手机放在侧后方监控你的桌面环境和你的操作。这带来了几个新的挑战点我们的编码策略必须相应调整。3.1 开发环境与心态准备环境选择华为OD机试环境通常是定制的在线IDE。但平时练习我强烈推荐使用你最熟悉的本地环境比如VS Code或CLion并配好稳定的C编译调试环境如MinGW-w64。练习时就要模拟考试环境——全屏编辑器关掉所有无关通讯软件和网页。熟悉你的环境快捷键编译、运行、格式化这能在考试时为你节省大量时间。心态管理双机位会放大紧张感。我的建议是把监控摄像头想象成一个沉默的队友。你的任务是向它清晰地展示你的思考过程。遇到难题时不要长时间发呆或面露难色可以动笔在草稿纸上画图、列举样例、写伪代码。这些动作在监控里是“积极思考”的表现。3.2 代码结构与书写规范这是双机位模式下最重要的生存法则。凌乱的代码在监控下会显得非常糟糕。模块化函数设计不要写一个几百行的main函数。根据题目逻辑清晰地拆分成几个函数vectorpairint, int getCoverage(int x, int y, int range, const vectorstring grid): 获取一个监控点的覆盖坐标列表。bool isAllCovered(const vectorpairint, int targets, const vectorvectorbool visited): 判断所有目标点是否已被覆盖。int dfs(int idx, int mask, const vectorint coverMasks, int targetCount): 使用位掩码的回溯函数计算最少新增设备。 这样的结构即使某个函数一时没写对其他部分依然清晰可读方便你定位和修改。详尽的注释在关键步骤、复杂逻辑处写上简洁的注释。这不是给编译器看的是给“监控视角”和阅卷人看的。例如// 使用位掩码mask表示当前覆盖状态bit[i]1表示第i个目标点已被覆盖 // coverMasks[i]表示第i个监控设备或可选位置能覆盖的目标点掩码这展示了你的编程意图和算法理解。统一的命名与格式使用有意义的变量名targetPoints,sensorCoverMask避免a,b,c。保持一致的缩进通常4个空格。考前可以准备一个包含常用头文件、快速输入输出ios::sync_with_stdio(false);和基本框架的代码模板考试时直接复制粘贴节省时间并保证格式整洁。防御性编程在读取输入后立即添加输入数据的校验和打印调试用提交前可注释掉。例如// 调试打印读取到的地图和目标点 #ifdef DEBUG cout “网格尺寸” n “ “ m endl; for (const auto p : targetPoints) { cout “目标点(” p.first “, “ p.second “)” endl; } #endif这能帮你快速定位是思路错误还是输入处理错误。4. “敌情监控”C实现与逐行精讲下面我将基于一个典型的题目假设监控范围是曼哈顿距离≤R来给出一个完整的、注重可读性和健壮性的C实现。我会假设我们需要计算最少新增监控点。题目假设输入网格大小n m监控范围R现有监控点数量s及坐标目标点数量k及坐标。网格坐标从1开始。输出一个整数表示需要新增的最少监控设备数量。如果初始已全覆盖则输出0。#include iostream #include vector #include queue #include utility #include algorithm #include climits #include cstring // for memset using namespace std; // 工具函数计算从点(x1,y1)到点(x2,y2)的曼哈顿距离 int manhattan(int x1, int y1, int x2, int y2) { return abs(x1 - x2) abs(y1 - y2); } // 核心函数1计算一个位于(x, y)的监控设备能覆盖哪些目标点返回覆盖掩码 int getCoverMask(int x, int y, int range, const vectorpairint, int targets) { int mask 0; for (int i 0; i targets.size(); i) { if (manhattan(x, y, targets[i].first, targets[i].second) range) { mask | (1 i); // 将第i位置1 } } return mask; } // 核心函数2深度优先搜索回溯计算覆盖所有目标所需的最少新增设备 // idx: 当前考虑的可选监控点索引 // currentMask: 当前已覆盖的目标点掩码 // coverMasks: 所有可选监控点的覆盖掩码数组 // targetCount: 目标点总数用于判断是否全部覆盖 // best: 引用传递记录当前找到的最优解最少设备数 void dfs(int idx, int currentMask, const vectorint coverMasks, int targetCount, int cnt, int best) { // 剪枝1如果当前使用的设备数已经大于等于已知最优解无需继续 if (cnt best) return; // 剪枝2如果已经覆盖所有目标点更新最优解 int allCoveredMask (1 targetCount) - 1; if (currentMask allCoveredMask) { best min(best, cnt); return; } // 如果已经考虑完所有可选点返回 if (idx coverMasks.size()) return; // 分支1选择当前监控点 int newMask currentMask | coverMasks[idx]; // 只有选择后覆盖状态有变化选择才有意义可以作为一个微优化 if (newMask ! currentMask) { dfs(idx 1, newMask, coverMasks, targetCount, cnt 1, best); } // 分支2不选择当前监控点 dfs(idx 1, currentMask, coverMasks, targetCount, cnt, best); } int main() { // 关闭同步提升cin/cout速度但注意不能再混用C的scanf/printf ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, R; cin n m R; int s; cin s; vectorpairint, int sensors(s); for (int i 0; i s; i) { // 题目坐标通常从1开始我们存储时也保持从1开始计算时注意即可 cin sensors[i].first sensors[i].second; } int k; cin k; vectorpairint, int targets(k); for (int i 0; i k; i) { cin targets[i].first targets[i].second; } // 步骤1计算初始覆盖状态 int initialMask 0; for (const auto sensor : sensors) { initialMask | getCoverMask(sensor.first, sensor.second, R, targets); } int allCoveredMask (1 k) - 1; if (initialMask allCoveredMask) { cout 0 endl; // 初始已全覆盖 return 0; } // 步骤2生成所有可能新增监控点的位置及其覆盖掩码 // 假设可以在网格内任意空位置非已有监控点放置新设备。这里简化考虑所有格子。 // 注意这是一个潜在的优化点如果n*m很大需要根据题目约束缩小候选集。 vectorint candidateMasks; for (int i 1; i n; i) { for (int j 1; j m; j) { // 可以跳过已经是监控点的位置如果题目允许重叠则不用 // bool isExistingSensor false; // for(...) 判断这里为了清晰省略 int mask getCoverMask(i, j, R, targets); if (mask ! 0) { // 只收录能覆盖至少一个目标点的位置 candidateMasks.push_back(mask); } } } // 步骤3使用DFS回溯寻找最少新增数量 int best INT_MAX; // 初始化为最大值 dfs(0, initialMask, candidateMasks, k, 0, best); // 步骤4输出结果 if (best INT_MAX) { // 理论上因为候选点覆盖所有目标应该能找到解。这里出于健壮性保留。 cout -1 endl; } else { cout best endl; } return 0; }关键代码段讲解位掩码Bitmask的使用这是本解法的效率核心。int类型有32位每位代表一个目标点索引0~31。mask | (1 i)表示将第i个目标点纳入覆盖。(1 targetCount) - 1生成了一个所有位都是1的掩码代表全部覆盖。用位运算|或来合并覆盖范围用来判断是否全覆盖效率极高。DFS回溯与剪枝dfs函数遍历每一个候选监控点做出“选”或“不选”的决策。剪枝1 (if (cnt best) return;)): 如果当前路径使用的设备数已经不少于当前最优解这条路径不可能更优直接放弃。剪枝2 (覆盖检查): 一旦发现全覆盖立即更新最优解并返回。这两个剪枝能大幅减少搜索空间是回溯法能应对稍大规模数据的关键。候选点生成优化上面的代码遍历了所有n*m个格子。在实际题目中这可能过于庞大。一个常见的优化是只考虑那些至少能覆盖一个当前未被覆盖目标点的位置。我们可以先找出未被初始覆盖的目标点然后反向推导出能覆盖它们的格子集合作为候选集。这能极大缩小candidateMasks的大小。5. 双机位临场实战避坑指南与调试技巧即使代码逻辑正确在高压的双机位环境下也可能因为细节失误导致功亏一篑。下面是我总结的“血泪”经验。5.1 输入输出与边界条件处理这是机试中最常见的失分点没有之一。仔细阅读输入格式题目是先输入n, m还是先输入R坐标是(行列)还是(x, y)索引从0开始还是1开始务必用笔在草稿纸上标出。我们的示例代码假设坐标从1开始如果题目从0开始所有坐标计算都要调整manhattan函数和getCoverMask中的判断逻辑依然成立但候选点循环范围要改为(0, n-1)和(0, m-1)。处理多组输入很多机试题包含多组测试用例。我们的示例代码只处理了一组。如果题目是多组的需要用一个while(cin n m R)或while(scanf(...) ! EOF)循环包裹主逻辑。初始化与重置对于多组用例所有全局变量和容器必须在每组用例开始前清空重置。忘记重置vector或best变量是经典错误。// 多组用例模板 while (cin n m, n || m) { // 假设以两个0结束 // 1. 清空上一组数据 sensors.clear(); targets.clear(); candidateMasks.clear(); // 2. 读取本组数据... // 3. 计算并输出... }5.2 算法优化与复杂度估算机试通常有时间和内存限制。双机位下一个跑不出结果的低效算法会消耗你大量时间并增加焦虑。复杂度心里有数对于我们的DFS回溯最坏复杂度是O(2^C)其中C是候选点数量。如果C超过20就非常危险。这时就要考虑贪心或其他启发式算法。在动手前先估算一下数据范围。如果n, m 10,k 10那么暴力回溯是可行的。如果k很大可能需要转换思路例如将问题建模为二分图的最小点覆盖等。使用更高效的数据结构如果目标点很多K30位掩码用int就不够了可以使用bitset或long long最多64位。对于更大规模可能需要用布尔数组或集合来记录覆盖状态但DFS效率会下降。5.3 双机位下的调试策略你不能指望像平时一样用IDE的调试器一步步跟。必须掌握“打印调试法”。设计小样例在编码前设计一个最简单的样例比如2x2网格1个目标点和一個稍复杂的样例。用它们来验证你的核心逻辑如getCoverMask,manhattan。分段打印在代码关键节点插入打印语句输出中间变量。// 在dfs函数开头可以打印 // cout “[DFS] idx” idx “, curMask” bitset32(currentMask) “, cnt” cnt endl;注意提交前务必注释或删除所有调试输出否则可能因输出格式错误判0分。使用条件编译像之前示例的#ifdef DEBUG那样可以优雅地管理调试代码。利用自测用例机考平台通常允许自测。把你设计的小样例输入进去快速验证。如果出错根据错误输出Wrong Answer, Runtime Error, Time Limit Exceeded快速定位。WA: 检查算法逻辑、边界条件、输入输出格式。RE: 检查数组越界、除零、栈溢出递归太深。TLE: 算法复杂度太高需要优化或换思路。5.4 时间分配与应急方案5-10分钟审题与设计绝对不要一上来就敲代码。在草稿纸上画出网格标出点手动模拟一下覆盖过程。明确算法步骤、数据结构、函数接口。这步在监控下是“有效思考”。20-25分钟核心编码按照模块化设计逐个函数实现。先实现输入解析和工具函数如manhattan再实现核心逻辑如getCoverMask,dfs。确保每个小模块都能通过你设计的小样例。10-15分钟测试与调试用自测功能测试边界情况网格大小为1没有监控点没有目标点监控范围R为0等。如果遇到难题卡住超过10分钟果断考虑暴力解法保分。例如如果DFS想不出来可以写一个遍历所有子集for (int i 0; i (1 candidateSize); i)的暴力枚举对于小数据也能过部分用例。最后5分钟检查全局变量是否重置删除调试输出确保代码格式整洁然后提交。6. 从“敌情监控”延伸的常考题型与备战建议“敌情监控”综合了图、搜索和状态压缩。通过这道题我们可以梳理出华为OD C机试的一些高频考点和备战方向。图论与搜索BFS求最短步数、扩散、DFS回溯、连通块是绝对核心。必须熟练掌握它们的递归和非递归写法并能处理二维网格上的移动四方向/八方向。动态规划尤其是线性DP和背包问题。状态压缩DP像本题的位运算是难点也是高分点。数据结构应用哈希表unordered_map/set用于快速查找去重优先队列priority_queue用于Dijkstra等算法并查集处理连通性问题。字符串处理KMP字符串匹配、模拟题中复杂的字符串解析。贪心与模拟一些看似复杂的题目本质是找到贪心策略或者耐心模拟过程。备战建议刷题平台牛客网的华为机试真题库是最贴近的。LeetCode上可以针对性练习“回溯”、“BFS”、“状态压缩DP”等标签的题目。专题突破不要盲目刷题。按上述考点分成专题每个专题集中练习5-10道经典题直到能独立、快速、正确地写出代码。模拟考试每周进行1-2次全真模拟使用计时器在无干扰环境下完成2-3道题。用手机架在侧后方录制自己的考试过程事后回看检查自己的编码习惯、时间管理和应急反应。代码模板准备自己熟悉的、经过大量测试的代码模板包括快速IO、常用数据结构初始化、DFS/BFS框架、并查集类等。考试时直接套用能提升速度和信心。双机位带来的不仅是监督更是一种对开发者综合素质的考察。它要求你在压力下依然能保持清晰的逻辑、规范的编码和稳健的心态。把每一次练习都当成真实考试注重过程而非仅仅结果当你对题目本质和编码本身足够熟练时监控摄像头就不再是压力而是你专业表现的见证。最后再分享一个小心得在考试开始前对着摄像头微笑一下给自己一个积极的心理暗示这简单的动作有时能有效缓解初始的紧张感。
