从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++里最直接的方法是用vector<vector >存储地图：
int n, m; cin >> n >> m; vector<vector<char>> grid(n, vector<char>(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(pair<int,int> start, vector<vector<int>>& dist) { queue<pair<int,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 -std=c++17 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++去“战胜白蚁”，其实真正要战胜的是拿到题目时那一瞬间的慌乱。沉着下来，一切都只是数组、循环、判断和队列的组合游戏。
