C++竞赛模拟题实战：从BFS扩散到边界调试，复盘白蚁赛题

从2025年8月13日往回看“战胜白蚁”这五个字还是有点戏剧性。去年暑假备战2024全国信息素养大赛C组的时候我给自己定了一个小目标把历年赛题里跟模拟、搜索、数值计算相关的题目全部吃透白蚁赛题就是其中一道印象最深的模拟题——不是因为它算法多难而是它几乎把C竞赛里常踩的坑全踩了一遍。这篇文章就当是给后来者的一份复盘笔记聊聊我拿到这道题之后怎么拆解、怎么实现、又在哪些地方翻了车。1. 先聊清楚“战胜白蚁”这个赛题到底想考什么1.1 题目背景与实际场景分析全国信息素养大赛的C赛项整体难度不是那种竞赛ACM级别的硬核但胜在题目覆盖面广从基础语法、简单算法到综合模拟都可能涉及。“战胜白蚁”这类题目常见的设计思路是给出一个二维平面区域白蚁从某些初始位置开始扩散扩散规则和地形、时间、障碍物有关要求参赛者用程序模拟白蚁的移动轨迹、统计被侵蚀的区域面积或者在特定约束下求出消灭白蚁的最优方案。这类题目在赛事中几乎年年都有变体它能很好地考察几个核心能力状态建模是否清晰、边界条件考虑是否周全、以及在大规模数据下程序能否在限定时间内跑完。很多人觉得模拟题就是“按规则写代码”但真正的难点在于规则往往描述得很自然语言化你需要把它翻译成精确的数据结构表达。“白蚁扩散”题目里最典型的翻译就是把二维平面抽象成网格每个网格记录白蚁出现的时间点按时间步迭代更新。这题的时间限制一般在1秒左右数据范围可能达到10^5甚至10^6个网格所以不能写得太随意。它不像纯数学题那样只有一个标准解法更像一道“工程题”考验的是你能不能又快又稳地把规则落地成可运行的C代码。1.2 拿到题目后第一件事拆解输入输出很多第一次参赛的同学拿到题就急着写代码这是最大的误区。我习惯先把输入输出格式抄在草稿纸上再标注每一行对应什么含义。“白蚁”这类题输入通常包括地图大小比如n行m列、白蚁初始坐标列表、扩散规则参数、以及可能的障碍物坐标。输出一般是最终被侵蚀的格子数量、扩散所需轮数或者类似“能否在指定步数内达到目标”的判断结果。建议把样例输入手动推一遍不要直接看样例解释。“手动推演”这一步能帮你发现建模时漏掉的状态比如白蚁是否会重复进入同一格、障碍物是永久阻断还是可以被侵蚀、扩散是按曼哈顿距离还是按8方向这些细节直接决定算法的选择。如果按4方向扩散可以用BFS如果白蚁数量多且地图大可能要用优先队列模拟时间序如果涉及“消除白蚁”的策略可能还要用到贪心或二分答案。拿到题目后先花10分钟做三件事用自然语言复述一遍规则确认每一条都对应到代码里的某个判断。手动走一遍样例记录每一步的状态变化。把所有可能改变状态的边界情况列出来——比如地图只有1行1列、初始位置就在边界、障碍物把区域完全隔断。这三步做踏实了后面写代码就是“翻译工作”不会被突如其来的规则变化打乱节奏。2. 备赛阶段我重点抓的C知识点从输入优化到算法模板2.1 输入输出优化与竞赛码风“白蚁”这类模拟题数据量不小赛前我特意把C的输入输出方式做了调整。很多教材教的是cin和cout但竞赛场景里直接用cin读大批量数据容易超时我一般这样处理#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 正常使用 cin }这两行代码的作用是取消C标准输入输出与C标准IO的同步以及解绑cin和cout的关联。实测在数据量10^6级别时性能差距可能有2到3倍。如果你还是不放心直接用scanf和printf也是稳妥的选择只是字符处理时稍微繁琐一些。代码风格上也别忽视。“竞赛码风”不是玄学而是减少失误的手段。我习惯统一用大括号换行、变量名见名知意、核心算法单独封装成函数。虽然在考场上时间紧但清晰的结构能让你在调试时快速定位问题。“战胜白蚁”这道题的规则比较多我拆成了几个函数读入地图、初始化状态、单步扩散、统计结果。这样即使某个环节出bug也只需要检查一个函数内部逻辑。竞赛和平时写业务代码不一样不需要过度追求封装和抽象但必要的模块化还是值得保留。我见过不少同学把几百行逻辑全部塞进main函数里出问题时上下来回翻白白浪费大量时间。2.2 算法基础排序、二分、快速幂、单调栈信息素养大赛C组对算法基础的要求很明确排序、二分查找、快速幂、单调栈这些是常客贪心和动态规划也会偶尔出现。“战胜白蚁”虽然是个模拟题但解题过程中这些基本功都会用到。以排序为例如果题目要求按“白蚁到达某格的时间”排序后处理C的sort就是首选。它内部是混合排序算法平均复杂度O(n log n)对常规数据量完全够用。但要注意sort的比较函数必须严格弱序不能出现a b和b a同时为真的情况否则会引发未定义行为。二分查找在赛题里最常见的用途是“求满足条件的最小值/最大值”比如判断“是否存在某个消灭方案能在t步内完成”。这时把判断逻辑封装成一个check(t)函数然后在可能的步数范围内二分答案就能把复杂度从O(n^2)降到O(n log n)。快速幂和质数判断是数值计算题的高频考点这和模拟题看似无关但“白蚁”类题目有时会嵌套数值规则比如扩散速度随时间指数变化。快速幂模板并不复杂long long qpow(long long a, long long b, long long mod) { long long res 1; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }这题里如果用不上也没关系但模板还是要滚瓜烂熟因为赛事不同年份的题型会调整说不准下一场就用上了。单调栈的典型应用是求“下一个更大元素”维护一个栈内元素单调递增或递减的序列。它在“白蚁”题里不算核心但如果你需要对地图上的障碍高度做处理很可能会用到类似思路。学会单调栈的关键不是背代码而是理解它为什么能把O(n^2)的暴力比较优化到O(n)——每个元素最多入栈出栈一次。2.3 数据结构字符串处理与模板类链表很多人觉得数据结构在模拟题里用不上其实不然。“白蚁”赛题的地图信息通常以字符形式读入比如 ‘.’表示空地、‘#’表示障碍、‘B’表示白蚁。这里就涉及字符串处理如何把一串字符拆成二维网格的每一行。C里最直接的方法是用vectorvector 存储地图int n, m; cin n m; vectorvectorchar grid(n, vectorchar(m)); for (int i 0; i n; i) { string row; cin row; for (int j 0; j m; j) { grid[i][j] row[j]; } }string到字符数组的转换看似基础但真到了赛场上有人会因为忘记处理换行符或者没考虑行末空格导致读取出错。建议在本地测试时专门构造带空格、空行的完整输入文件来验证。关于模板类链表这个知识点在信息素养大赛中属于选学内容。如果题目需要频繁插入删除比如维护“活着的白蚁列表”STL里的list直接能用不需要手写。但有一种情况必须手写题目要求不能使用STL或者你需要对链表节点做自定义扩展比如记录每只白蚁的剩余生命值。手写链表时最容易翻车的地方是指针操作顺序删除节点前一定要先把next指针保存好否则一旦释放内存后访问就是野指针。3. 核心算法实现白蚁扩散模拟的框架与性能优化3.1 一个可复用的扩散模拟框架针对“战胜白蚁”这种模拟扩散的题我总结了一套比较通用的框架核心就是“网格状态 队列驱动的BFS”。假设每轮白蚁从当前格子向相邻4个方向扩散一格障碍物不可穿越空地只能进入一次那么const int dx[] {0, 0, 1, -1}; const int dy[] {1, -1, 0, 0}; void bfs(pairint,int start, vectorvectorint dist) { queuepairint,int q; q.push(start); dist[start.first][start.second] 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (grid[nx][ny] #) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } }这个框架的思路是dist数组初始化为-1表示“未被白蚁到达”起点设为0然后按层扩展。BFS天然能保证每个格子第一次被访问时就是最短时间不需要额外处理“更优路径覆盖”的情况。如果题目要求“多只白蚁同时扩散”只需要把所有白蚁初始位置全部压入队列dist都设为0再统一做BFS。这样得到的dist含义是“最早被任意一只白蚁到达的时间”完全符合题目常见的统计需求。3.2 快速幂与二分查找在赛题中的结合“战胜白蚁”如果只到BFS就结束充其量是道中等题。但实际赛题有时候会加一个操作你可以每隔t轮释放一次药剂药剂能立刻杀死半径r内的白蚁问能否在有限步数内控制住局面。这种设计就需要二分答案和快速幂思想。二分答案的思路是枚举“释放药剂的次数上限k”写一个check(k)函数判断是否可行——如果k次药剂足够控制局面就尝试更小的k反之则增大k。check函数内部则要模拟药剂效果可能用优先队列维护“当前威胁最大的白蚁群”。快速幂在这里的应用更隐蔽如果白蚁数量按指数方式增长比如每一轮数量翻倍那么当轮数很大时直接模拟会超时可以用快速幂直接计算出第x轮的数量。前提是数据范围不超过long long能承载的极限否则要配合取模处理。这种“看似模拟题实则算法嵌套”的出题风格是近几年信息素养大赛比较明显的变化趋势。如果你只准备了一套BFS模板就上考场大概率会在进阶问上吃大亏。所以我备赛时特别强调“模板的复合使用”基础模板单独练组合场景也要专门练几道。3.3 边界条件与时间复杂度控制的实战取舍边界条件是模拟题最大的扣分点没有之一。白蚁扩散题目的边界条件主要集中在三块地图边界、障碍物包围、初始状态重叠。我常用的检查方式是构造“最小输入”——比如1×1的地图、白蚁初始位置就是边界上的点、障碍物围成一圈。这些极端情况在样例里往往不出现但评测数据里一定有。时间复杂度控制上BFS的复杂度是O(n×m)也就是和地图格子数线性相关。如果n、m都是1000就是10^6次操作在1秒内完全没问题。但如果你不小心用了重复扫描地图的方式比如每一轮都遍历全图找白蚁复杂度会变成O(轮数×格子数)地图稍微大一点就会超时。更优的做法是“用队列记住当前活跃的白蚁位置”每轮只需处理队列里的格子而不是全图扫描。这也是为什么我推荐BFS而不是for循环轮次模拟的原因。BFS的天然优势就是它只在有状态变化的地方工作。提示评测环境对时间的把控通常以“某步操作超时则整题判0分”为原则所以宁可多写几行保证效率的代码也不要为了图省事留下性能隐患。4. 赛场上的三次惊险瞬间从栈溢出到评测差异4.1 递归爆栈DFS和BFS的生死抉择第一次练“白蚁”类似题时我随手写了一个DFS版本思路是从起点递归访问相邻格子。样例跑得飞快但一到大数据量就直接崩溃排查后确认是栈溢出。递归深度超过系统栈上限通常几万层就危险程序就异常退出。解决方案有两种一是递归改循环用显式栈模拟DFS二是直接用队列做BFS。对扩散类题目BFS本来就是更自然的选择因为你需要的是“逐层扩散”的顺序而不是“一条路走到黑”。那次之后我给自己定了个规矩只要题目涉及“最早时间”“最短路径”一律BFS优先只有涉及“是否存在一条路径”这类连通性问题时再考虑DFS而且非递归版本优先。4.2 整型溢出的隐蔽陷阱int与long long的权衡有一版代码我统计被侵蚀格子数量时用了int第一版样例没问题但换成随机大数据测试时结果出现了负数。查了半天才发现是格子总数超过了int约21亿的上限——虽然单个地图维度不大但多组数据累加统计时仍然可能越界。很典型的一个教训不要在赛场上赌“数据不会那么大”。只要涉及累加计数、坐标运算、轮数统计直接使用long long更稳妥。虽然理论上long long会多占一点内存但现代评测机的内存限制通常都放得比较宽时空权衡上选择安全一侧更划算。4.3 本地通过但评测出错文件读写与系统差异有的参赛同学习惯在本地IDE里手动输入数据提交时才发现评测系统要求的是读文件。这种“环境差异”导致的问题在赛场上相当常见。我用的固定套路是freopen(ant.in, r, stdin); freopen(ant.out, w, stdout);这两行放在main函数开头就能把标准输入输出重定向到文件。提交前只要保证文件名和题目要求一字不差即可。另一个隐藏问题是行尾空格有些评测系统开启严格模式多一个空格或者少一个换行都会判WA。我开发的检查习惯是输出循环里统一用“空格隔开最后换行”的模板for (int i 0; i cnt; i) { if (i) cout ; cout ans[i]; } cout \n;这个小模板能避免99%的输出格式问题。5. 复盘总结下次参赛我会调整的五件事5.1 赛前一周的竞赛化训练安排经过这次备赛我对“临时抱佛脚”和“系统化训练”的差别有了更直观的认识。赛前一周我没有再盲目刷新题而是把以前的错题和模板重新过了一遍每天固定做三件事上午限时训练用完整的一小时模拟比赛环境做一套历年真题混合卷中间不看资料不上网。下午专题补漏根据上午暴露的问题集中刷对应知识点比如快速幂不熟就专练快速幂字符串处理易错就多写相关解析。晚上复盘笔记把当天写错的代码在本地重新调通并在笔记里记录错误原因和解决方案。这种节奏比考前冲刺十天更有效因为它在保持手感的同时给了大脑沉淀吸收的时间。5.2 环境配置与调试技巧从Dev-C到命令行编译很多人问我校赛用哪个IDE。我的回答是顺手最重要但一定要熟悉命令行编译。因为评测系统本质上就是在命令行环境下调用编译器运行的你在图形界面里跑通不代表命令行环境也能跑通。我用的组合是写代码用VS Code编译测试用g命令行g -O2 -stdc17 ant.cpp -o ant ./ant sample.in sample.out这里的-O2是开启二级优化很多性能问题在-O0下不会暴露但评测系统默认开启优化提前用相同参数测试能减少“意料之外的超时”。调试技巧上我习惯在代码里加条件宏输出中间状态#ifdef DEBUG cerr step step : erased cells erased endl; #endif本地编译时加-DDEBUG提交时去掉这样既不影响提交代码的体积又能随时看到中间过程比单纯用调试器打断点更高效。5.3 心态与时间分配1小时赛题的时间预算赛场上的时间分配我总结出一个“黄金比例”30%时间审题与建模40%时间编码实现20%时间测试修错10%时间提交前检查。很多同学把大部分时间花在“写代码”上却忽略了审题和测试。实际上“白蚁”这样的模拟题规则没理清楚就动手写大概率要返工重写。更推荐的做法是先把规则变成流程图式的伪代码确认没有逻辑漏洞后再开始写。哪怕多花10分钟在草稿纸上推演也可能节省30分钟的改错时间。提交前检查环节不能省略。我通常花两分钟检查几个点文件名是否正确、freopen路径是否对、输出格式是否与样例一致、有没有调试用的cerr残留、变量类型有没有用错。5.4 对“信息素养”几个字的理解编程不只是敲代码备赛过程中我越来越认识到C竞赛考察的从来不只是语言本身。信息素养大赛强调的“素养”二字更接近一种数字化时代的思维方式定义问题、拆解问题、设计流程、验证结果。“战胜白蚁”这道题教会我的不只是BFS怎么写更是“拿到一个模糊的大问题如何一步步把它拆成可计算的小模块”的工程能力。比如白蚁扩散可以拆成“位置状态记录”和“相邻关系扩散”两个子问题消灭白蚁的方法可以拆成“策略选择”和“结果校验”两个阶段。这种拆解能力放在任何领域都是通用的。5.5 给下一届选手的一句话建议如果让我给下一届参赛者留一句话建议我会说把历年真题当“收藏品”反复研究而不是当“任务”刷完就扔。每年赛题虽然不一样但底层思路高度相似——模拟题考状态建模数值题考算法复杂度综合题考知识迁移。我在备考“战胜白蚁”过程中意识到我犯的错误不是刷题量不够而是刷题后缺乏深度整理。后来每做一道有价值的题我都会建立“四维笔记”题目模型的抽象描述、我最初的错误思路、正确的解法框架、可以迁移的知识点清单。6. 写在最后从“战胜白蚁”到战胜自己赛后复盘时我翻看自己备赛初期写的第一版BFS代码和最终提交的版本对比差别几乎是一道“重写题”。第一版连队列初始化都写错把起点坐标弄成了二维数组的索引单位最终版则考虑了多起点、障碍物隔离、时间统计等完整边界。那次经历之后我明白了一个道理竞赛比的不是谁更能背模板而是谁更能冷静地把一个陌生的、看起来有点吓人的题目转化成自己熟悉的模型。“白蚁”虽然名字听起来像偏题怪题本质上就是一次带权重的连通性遍历和你练过的其他BFS没有本质区别。如果你也在备赛遇到看不懂的题目名字先别慌。把名字放在一边去看输入输出格式去看样例数据去看约束范围答案就在这些信息里。用C去“战胜白蚁”其实真正要战胜的是拿到题目时那一瞬间的慌乱。沉着下来一切都只是数组、循环、判断和队列的组合游戏。