网安考研复试编程Day25机试冲刺期的刷题复盘与实战记录先交代一下背景。我报考的是某高校网络空间安全方向复试里有一项机试编程占的比重还不小。今天是我集中训练的第25天距离正式上机大概还有四五天。前面的24天我大概刷了80多道题从一开始照着模板写都会报错到现在能比较快地定位考点、把边界条件处理干净。这篇文章就把Day25这天的完整训练过程记录下来包括当天做的题目、完整代码、当时卡住的地方以及这20多天里总结出来的避坑经验。如果你也在准备网安复试机试或者正在刷OJ里面的题目和解法可以直接拿去用踩坑部分更是花时间换来的建议重点看看。1. 机试到底考什么先把游戏规则弄清1.1 考试环境与判分方式先说一个很多人容易忽略的事实复试机试和你平时在本地写代码完全是两回事。机试通常是在一个固定的OJ在线评测系统上进行你提交代码后系统会用一组事先准备好的测试用例来评判满足所有用例才给满分部分通过给部分分。这意味着两个很重要的点一、你的程序必须能够在别人的机器、别人的编译器环境下正确编译运行。自己电脑上能跑通不代表评测机上能跑通环境差异可能会带来意想不到的问题。二、判分只看输出结果不看代码风格。你写得再优雅输出格式错一个空格同样零分。我见过不少同学算法思路完全正确却因为多打了一个换行或者少了一个空格痛失分数这种情况太可惜了。机试的语言一般以C/C为主。我全程用C语言训练原因很简单复试机试几乎不涉及大型工程核心就是算法逻辑和编码能力C语言够用而且编译快、调试直观。如果你准备用C也完全可以但建议从头到尾只用一种语言不要今天C明天C手感会乱。1.2 25天后的定位从“会写”到“敢写”整个备考周期里我把刷题分成了三个阶段。前10天是基础热身熟悉基本输入输出、数组、字符串、结构体的处理第11天到第24天是集中刷题重点覆盖排序、二分、栈、队列、二叉树、简单图论和动态规划第25天开始就进入了考前冲刺阶段。冲刺阶段和一阶段的区别在于你不再需要大量接触新知识点而是要把已经学过的内容尽量练熟、练透。网安方向机试的题目量一般不大常见的是4到6道题难度梯度明显基础题占一半中等题占两三道压轴题一道。Day25这个节点我每天的任务就是三道题一套限时训练完全模拟考试节奏做完之后逐题复盘分析每道题的考点、最优解和我的解法之间的差距。这个阶段特别重要的是处理考试状态下会犯的错误读题漏条件、变量名写错、数组开小了、忘记初始化这些低级错误在练习时不容易暴露限时训练时会频频出现。提前踩一遍坑真正考试时才能绕开。2. 网安方向机试的算法重点与选题逻辑2.1 基础数据结构与算法要求翻了目标院校近几年的机试题目可以发现考来考去就那些东西不会特别偏。大体可以分成以下几类第一类是线性结构处理数组、链表、字符串的操作。这部分是基础中的基础熟练度要求极高因为很多中等题都是在基础题外面包了一层壳。第二类是经典算法包括快速排序、归并排序、二分查找、前缀和/差分。这些内容代码量不大但边界条件特别容易出错比如二分查找的左右闭区间问题写不好就是死循环。第三类是树和图。二叉树的前中后序遍历、层序遍历、最近公共祖先、图的深搜广搜都属于高频考点。网安方向尤其爱考树的遍历和链表操作因为这类题目既能考察数据结构的理解又能考察递归和迭代两种写法的掌握情况。第四类是动态规划和贪心。这部分通常作为压轴题出现但实际上对于复试来说考到的动态规划多数是比较基础的背包问题、最长递增子序列、最长公共子序列等。能把状态定义和状态转移方程推导清楚基本就能应对。2.2 网络安全特色的编程题目除了通用算法网安方向的机试还有一个特点部分题目会结合安全领域的场景来出题。常见的有异或加密与解密。这类题目表面上是一道位运算题实际上考察的是异或运算的性质。给定一个密钥和一个明文要求实现加密或解密或者反过来给你加密后的数据让你还原。解法就是利用a XOR b XOR b a这个性质代码不超过十行但需要你对异或的特性有清晰认识。哈希与编码处理。比如要求计算字符串的哈希值或者实现简单的字符映射替换。有些题目会把 Base64 编码、URL编码等作为背景知识来出题但不会要求你完整实现编码算法往往是给定格式让你按规则处理数据。数的进制转换。二进制、八进制、十六进制之间的转换有时候会结合IP地址、端口号、二进制数位运算来出题。这类题本身不难但特别容易在格式转换上出错比如负数怎么处理、大数怎么存储。简单密码学逻辑。比如凯撒密码、仿射密码、单表替换密码的加解密过程实现。这些题目本质上是字符串处理和数学计算的结合难度不大但需要你仔细读题弄清楚字母映射的具体规则。这些特色题不会专门考察某一个密码学算法更多是把安全领域的常见逻辑包装成编程题。知道这个规律之后平时练习就会有意识地做上几道这类题目上考场看到熟悉的场景就不慌。3. Day25训练实录三道题的完整复盘今天限时训练做的是三道题难度梯度大概是有易有难其中有并查集背景的数组处理题、异或编码题和字符串数组公共前缀题。下面把每道题的思路、代码和分析完整记录下来。3.1 题目一检查重复数字并查集简化版题目描述大概是给定一个长度为n的整数数组进行m次操作每次操作输入两个位置下标a和b表示把下标a对应的值累加到下标b对应的位置上然后输出每次操作后数组中非零元素的个数。第一眼看着像是模拟题但如果直接模拟每一步操作之后都要遍历一遍数组统计非零元素个数时间复杂度是O(n*m)n和m稍微大一点就直接超时。我一开始就按模拟写了样例能过提交上去超时。后来想到用并查集来维护。思路是这样一个位置上的数一旦被累加出去它自己就变成零了之后这个位置就不再参与计数了。我们用一个并查集维护非零位置的链表结构每次操作时先通过并查集找到当前需要操作的实际位置然后执行值的累加如果某个位置的值变成了零就把它的父节点指向它的下一个位置表示它已经消失了。这样一来每次操作只需要处理发生变化的两个位置并且维护一个非零元素数量的计数器。整体时间复杂度可以降到接近O(nm)的水平也就是并查集近乎常数的均摊复杂度。核心代码如下#include stdio.h #define MAXN 200005 int parent[MAXN]; int val[MAXN]; // 并查集查找路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } int main() { int n, m; scanf(%d %d, n, m); int nonzero 0; for (int i 1; i n; i) { scanf(%d, val[i]); parent[i] i; if (val[i] ! 0) nonzero; } // 哨兵位置方便边界处理 parent[n 1] n 1; while (m--) { int a, b; scanf(%d %d, a, b); if (a b) { int t a; a b; b t; } int rb find(b); if (rb ! n 1 val[a] ! 0) { if (val[rb] 0) { // b的值已经被移走了需要找到下一个非零位置 rb find(rb 1); } if (rb ! n 1) { val[rb] val[a]; if (val[a] ! 0) nonzero--; // a位置变零 val[a] 0; parent[a] find(a 1); // a位置从链表中移除 if (val[rb] ! 0 rb ! a) { // 检查rb是否变零变零则移出 if (val[rb] 0) { nonzero--; parent[rb] find(rb 1); } } } } printf(%d\n, nonzero); } return 0; }这道题我最开始写的时候犯了一个错误没有考虑值累加之后可能恰好变成0的情况。比如某个位置上本来是0但是根据操作规则它不能被当作有效目标位置我却没有处理导致计数错误。后来通过构造边界数据才发现问题加上了对累加结果是否为0的判断才通过。这个题目本质上是一个数据结构优化题看起来是模拟实际上是并查集维护动态删除场景。复试机试里面有不少这种包装过的题目表面是模拟实际需要你想到更优的数据结构所以平时训练时不要只满足于把样例过掉要养成估算复杂度的习惯。3.2 题目二异或加解密题目描述给定一个由字符组成的字符串S和一个整数密钥key对字符串中的每个字符做异或操作规则是S[i] ^ key输出结果字符串。而后给定一个加密后的结果要求你还原原始字符串。这道题其实就是一个异或运算性质的应用比较简单。核心知识点就是异或运算的三个性质交换律、结合律、以及一个数连续异或两次同一个数会回到本身。所以加密和解密是完全相同的操作给定密文和密钥再对每个字符异或一次key就能还原明文。我当时写的代码如下#include stdio.h #include string.h int main() { char s[1005]; int key; scanf(%s, s); scanf(%d, key); int len strlen(s); for (int i 0; i len; i) { char c s[i] ^ (key 0xFF); printf(%c, c); } printf(\n); return 0; }这里有一个细节容易踩坑key是int类型而字符是char类型直接s[i] ^ key在做整数提升时如果key的高位不是0最终结果中可能会产生一些超出可打印ASCII范围的值。虽然题目通常允许输出任意字节但如果后续还有字符判断操作就会出问题。稳妥的做法是把key转换到低8位也就是key 0xFF确保异或结果落在单字节范围内。这道题虽然简单但它代表了一类网安特色题。很多同学觉得这类题简单得像送分题恰恰在这种题目上容易大意比如没有考虑多组测试数据输入、没有注意字符串首位不能有空格等格式要求。我在这类题上的原则是代码再简单提交之前也要仔细读一遍题目里的输出格式要求格式错误就直接零分。从复习角度来说这类题最值得练习的是位运算与字符处理结合的组合按位与、按位或、异或、移位操作在不同题目里会组合出各种花样的要求。把常见的位运算操作练熟遇到变体就不会慌。3.3 题目三字符串数组的最长公共前缀题目描述给定n个字符串求它们的最长公共前缀。如果有多个结果取字典序最小的那个。如果不存在公共前缀输出空行。这道题其实是经典的水平扫描法但加了一个字典序最小的附加条件很多人会在这里翻车。先说基本解法可以每次取相邻两个字符串的公共前缀不断缩小结果范围。时间复杂度O(S)S是所有字符串的总长度。空间复杂度O(1)。但要注意字典序最小这个条件。一开始我的思路是求出公共前缀之后再去找所有字符串中是否有更短的公共前缀然后取字典序最小。后来发现不对因为公共前缀本身是唯一的不需要找多个这个条件真正限制的地方在于当存在多个字符串全体共享的公共前缀时结果只有一个但题目可能是要求你从所有可能的前缀候选中选字典序最小者因此必须对所有前缀候选进行字典序比较。重新分析之后其实最稳的做法是先排序然后只比较排序后第一个和最后一个字符串的公共前缀这就是所有字符串的最长公共前缀。因为字典序排序后第一个和最后一个字符串共同拥有的前缀就是所有字符串共同拥有的前缀的极端情况。如果这两个的前缀长度是L那他们之间的所有字符串也至少有长度为L的公共前缀。这里还有一个细节空行怎么输出要求是不存在公共前缀时输出空行。很多人用printf(\n)就能过但有些OJ要求输出一个空字符串也就是直接换行这两种做法是一致的。关键是不要画蛇添足加额外的空格。我之前在C语言里处理字符串比较和复制时踩过一个坑用strcpy之前要确保目标数组足够大否则会越界。复试OJ上这类错误往往不报编译错误而是运行时报错系统给出的信息可能是运行时错误或段错误排查起来特别耗时。后来我养成了一个习惯凡是用到字符串拷贝优先用strncpy并手动加\0避免越界问题。3.4 今天训练的总结三道题做下来用时大概90分钟一道题卡了比较久就是并查集那道其余都比较顺畅。复盘下来有几个值得记录的发现懂得算法原理和能在有限时间内写出无Bug的实现中间隔着很大的训练量。并查集我会写但一加上具体操作场景还是会乱关键还是在链表的删除逻辑上思考不够清楚。简单题不能大意异或题目里数据类型转换问题要是没处理好输出结果可能完全不可读。字符串题的核心难点永远是边界处理和内存安全而不是算法本身。4. 高频失分点与实战对策4.1 超时问题一开始就要算复杂度复试机试给的时间通常是1到2小时题目数量4到6道。很多同学一开始写代码不估算复杂度上去就是暴力模拟小数据能过大数据直接超时。我自己的经验是看到题先花30秒估算一下数据范围。如果数组长度是10^5O(n^2)的算法基本没戏如果长度是10^3O(n^2)勉强可以如果长度是10^5但操作次数也是10^5那必须想到O(nlogn)甚至O(n)的解法。如果你平时练习时估算复杂度的习惯还没养成就在每道题提交之前问自己三个问题我的算法在最好情况下的复杂度是多少最坏情况下是多少最坏情况的输入在评测数据中可能出现吗只要最坏情况过不了就得想优化的方法。另一个和超时紧密相关的坑是输入输出效率。使用C语言的scanf和printf通常没问题但如果数据量大循环中频繁调用就会变慢。必要的时候可以用getchar自己写快读不过复试机试一般不太需要这么极致的优化除非数据范围给得特别大。4.2 数组越界与初始化问题我在训练中遇到过不下十次本地没问题OJ上运行错误的情况绝大多数是数组越界或者未初始化导致的。常见的错误有三种。第一种是数组开小了题目说最多输入n个但是你在处理过程中会访问到第n1个位置的哨兵节点没留出位置就会越界。第二种是二维数组的维度搞反了行当列、列当行很容易造成访问越界。第三种是定义了局部数组但没有初始化里面的值是随机的在一些需要默认值为0或默认值为-1的场景中会导致错误逻辑。解决办法也很朴素在本地写代码时把数组大小开成题目上限多一点留几个哨兵位置对需要初始化的数组不管是全局数组还是局部数组用循环或者memset显式清零写完代码后重点检查所有数组下标的最大可能取值养成数组下标永远不要越界的条件反射。4.3 调试技巧和编成习惯复试机试时你没法使用IDE的图形化调试器很多时候只能靠打印和读代码来排查问题。我平时训练用的几个土办法很有效分段打印法。如果某个答案不对就先在关键计算节点打印中间结果观察哪个步骤开始跑偏。小数据手算对照。构造一个小的测试用例用手算一遍期望的输出然后和程序的实际输出对比。这样可以快速判断是算法逻辑错还是代码实现错。构造边界数据。特别关注空输入、单元素输入、最大值输入、重复值输入这些边界情况最容易暴露问题。还有一个建议是平时就规范命名变量不要用a1、b_2这种毫无意义的名称。复试机试时长有限变量名太难记容易自己把自己绕晕。我用idx、pos、nonzero_cnt、parent这类有语义的名字代码写出来自己看得懂调试的时候也省时间。4.4 限时训练的三个要点到了Day25这个阶段纯粹刷题已经不够了必须限时。我每天的安排是挑3到4道难度递增的题给自己计时90分钟期间不看题解、不翻笔记完全模拟考试状态。训练结束后再花半小时复盘。复盘的时候不要只看自己做没做对要看这三个问题第一时间分配是否合理。如果前面的简单题花了太多时间后面的中等题就会紧张下次遇到简单题就要强迫自己加速。第二卡在哪一个环节。是做不出来还是做错了还是做出来了但没时间检查不同环节对应的应对策略不同。做不出来是知识点有盲区需要回去补基础做错了可能是审题或边界问题需要专门训练细致程度没时间检查则是速度问题需要多练。第三考场上的心态变化。限时训练很真实地模拟了考场的紧张感如果每次训练都因为紧张而失误那就要刻意练习深呼吸、提醒自己按部就班地分析题目。这些听起来很玄但确实影响实际发挥。5. 冲刺阶段的每日执行清单Day25之后的这几天别再做新题了。新题做不完而且容易打击信心。我当时给自己列的每日清单是这样上午用一套限时训练保持手感题目难度和正式机试接近。下午只做三件小事第一复习自己整理过的错题本重点看易错点和格式要求第二把并查集、二分查找、二叉树遍历、最长公共子序列这些高频算法的模板代码手写一遍不看任何参考确保肌肉记忆是准确的第三回顾一遍网安特色题的常见套路就是前面提到的异或、编码、进制转换、简单密码学逻辑这几类每类找一两个最经典的题目重新过一遍。晚上不写代码了翻一翻常见OJ报错信息的含义。比如Compile Error是编译错误Runtime Error是运行错误Time Limit Exceeded是超时Wrong Answer是结果错误。这些英文提示在考场上看到不要慌对应到解决方案就能很快定位。如果时间富余可以练一练手写伪代码的能力。复试机试有时候会要求先描述思路再写代码或者面试官会问你的解题思路。能清晰地把思路表述出来和能写出正确代码一样重要。我在家训练时每做完一道题会自己在心里或者对着手机录音用一分钟讲一遍这题的考点是什么、我为什么用这个算法、复杂度是多少。坚持几天后上机的时候明显感觉思路更清晰不会边写边想。我个人在Day25这天最大的体会是要舍得放弃。如果一道题10分钟还没有任何靠谱的思路果断跳到下一道先把能拿的分拿到手。复试机试的题目通常有梯度前面基础题的分数占比很高把基础题全部做对就已经可以拿到一大半分后面的中等题和压轴题是加分项不是必选项。很多同学在压轴题上死磕最后连基础题都没时间检查这种策略非常不划算。还有就是考前一定要把编译环境相关的细节确认清楚。用哪个编译器版本支持C99还是C11是否允许使用gets有没有bits/stdc.h这种头文件这些信息虽然琐碎但直接影响你现场写代码的方式。我在某次模拟训练的时候因为使用了某个高版本编辑器特有的语法换到评测环境后直接编译报错折腾了五分钟才改回来那五分钟如果在考场上就是实打实的分数损失。最后再分享一个实战技巧在评测系统上做题时代码提交前最后五秒别去改代码。我自己就干过一件蠢事——提交前觉得某个变量名不顺眼手一快改错了结果从AC直接变成WA然后疯狂怀疑自己改出了什么隐藏Bug在考场上浪费了十几分钟。除非是明确的语法错误否则不要临时改动已经测试正常的代码。这是很多考过机试的人都会踩的坑希望你能绕过去。 
长河君 · 2026/10/14 15:52:56 · 阅读 1.2k 网安考研复试机试冲刺：Day25刷题复盘与实战经验
网安考研复试编程Day25机试冲刺期的刷题复盘与实战记录先交代一下背景。我报考的是某高校网络空间安全方向复试里有一项机试编程占的比重还不小。今天是我集中训练的第25天距离正式上机大概还有四五天。前面的24天我大概刷了80多道题从一开始照着模板写都会报错到现在能比较快地定位考点、把边界条件处理干净。这篇文章就把Day25这天的完整训练过程记录下来包括当天做的题目、完整代码、当时卡住的地方以及这20多天里总结出来的避坑经验。如果你也在准备网安复试机试或者正在刷OJ里面的题目和解法可以直接拿去用踩坑部分更是花时间换来的建议重点看看。1. 机试到底考什么先把游戏规则弄清1.1 考试环境与判分方式先说一个很多人容易忽略的事实复试机试和你平时在本地写代码完全是两回事。机试通常是在一个固定的OJ在线评测系统上进行你提交代码后系统会用一组事先准备好的测试用例来评判满足所有用例才给满分部分通过给部分分。这意味着两个很重要的点一、你的程序必须能够在别人的机器、别人的编译器环境下正确编译运行。自己电脑上能跑通不代表评测机上能跑通环境差异可能会带来意想不到的问题。二、判分只看输出结果不看代码风格。你写得再优雅输出格式错一个空格同样零分。我见过不少同学算法思路完全正确却因为多打了一个换行或者少了一个空格痛失分数这种情况太可惜了。机试的语言一般以C/C为主。我全程用C语言训练原因很简单复试机试几乎不涉及大型工程核心就是算法逻辑和编码能力C语言够用而且编译快、调试直观。如果你准备用C也完全可以但建议从头到尾只用一种语言不要今天C明天C手感会乱。1.2 25天后的定位从“会写”到“敢写”整个备考周期里我把刷题分成了三个阶段。前10天是基础热身熟悉基本输入输出、数组、字符串、结构体的处理第11天到第24天是集中刷题重点覆盖排序、二分、栈、队列、二叉树、简单图论和动态规划第25天开始就进入了考前冲刺阶段。冲刺阶段和一阶段的区别在于你不再需要大量接触新知识点而是要把已经学过的内容尽量练熟、练透。网安方向机试的题目量一般不大常见的是4到6道题难度梯度明显基础题占一半中等题占两三道压轴题一道。Day25这个节点我每天的任务就是三道题一套限时训练完全模拟考试节奏做完之后逐题复盘分析每道题的考点、最优解和我的解法之间的差距。这个阶段特别重要的是处理考试状态下会犯的错误读题漏条件、变量名写错、数组开小了、忘记初始化这些低级错误在练习时不容易暴露限时训练时会频频出现。提前踩一遍坑真正考试时才能绕开。2. 网安方向机试的算法重点与选题逻辑2.1 基础数据结构与算法要求翻了目标院校近几年的机试题目可以发现考来考去就那些东西不会特别偏。大体可以分成以下几类第一类是线性结构处理数组、链表、字符串的操作。这部分是基础中的基础熟练度要求极高因为很多中等题都是在基础题外面包了一层壳。第二类是经典算法包括快速排序、归并排序、二分查找、前缀和/差分。这些内容代码量不大但边界条件特别容易出错比如二分查找的左右闭区间问题写不好就是死循环。第三类是树和图。二叉树的前中后序遍历、层序遍历、最近公共祖先、图的深搜广搜都属于高频考点。网安方向尤其爱考树的遍历和链表操作因为这类题目既能考察数据结构的理解又能考察递归和迭代两种写法的掌握情况。第四类是动态规划和贪心。这部分通常作为压轴题出现但实际上对于复试来说考到的动态规划多数是比较基础的背包问题、最长递增子序列、最长公共子序列等。能把状态定义和状态转移方程推导清楚基本就能应对。2.2 网络安全特色的编程题目除了通用算法网安方向的机试还有一个特点部分题目会结合安全领域的场景来出题。常见的有异或加密与解密。这类题目表面上是一道位运算题实际上考察的是异或运算的性质。给定一个密钥和一个明文要求实现加密或解密或者反过来给你加密后的数据让你还原。解法就是利用a XOR b XOR b a这个性质代码不超过十行但需要你对异或的特性有清晰认识。哈希与编码处理。比如要求计算字符串的哈希值或者实现简单的字符映射替换。有些题目会把 Base64 编码、URL编码等作为背景知识来出题但不会要求你完整实现编码算法往往是给定格式让你按规则处理数据。数的进制转换。二进制、八进制、十六进制之间的转换有时候会结合IP地址、端口号、二进制数位运算来出题。这类题本身不难但特别容易在格式转换上出错比如负数怎么处理、大数怎么存储。简单密码学逻辑。比如凯撒密码、仿射密码、单表替换密码的加解密过程实现。这些题目本质上是字符串处理和数学计算的结合难度不大但需要你仔细读题弄清楚字母映射的具体规则。这些特色题不会专门考察某一个密码学算法更多是把安全领域的常见逻辑包装成编程题。知道这个规律之后平时练习就会有意识地做上几道这类题目上考场看到熟悉的场景就不慌。3. Day25训练实录三道题的完整复盘今天限时训练做的是三道题难度梯度大概是有易有难其中有并查集背景的数组处理题、异或编码题和字符串数组公共前缀题。下面把每道题的思路、代码和分析完整记录下来。3.1 题目一检查重复数字并查集简化版题目描述大概是给定一个长度为n的整数数组进行m次操作每次操作输入两个位置下标a和b表示把下标a对应的值累加到下标b对应的位置上然后输出每次操作后数组中非零元素的个数。第一眼看着像是模拟题但如果直接模拟每一步操作之后都要遍历一遍数组统计非零元素个数时间复杂度是O(n*m)n和m稍微大一点就直接超时。我一开始就按模拟写了样例能过提交上去超时。后来想到用并查集来维护。思路是这样一个位置上的数一旦被累加出去它自己就变成零了之后这个位置就不再参与计数了。我们用一个并查集维护非零位置的链表结构每次操作时先通过并查集找到当前需要操作的实际位置然后执行值的累加如果某个位置的值变成了零就把它的父节点指向它的下一个位置表示它已经消失了。这样一来每次操作只需要处理发生变化的两个位置并且维护一个非零元素数量的计数器。整体时间复杂度可以降到接近O(nm)的水平也就是并查集近乎常数的均摊复杂度。核心代码如下#include stdio.h #define MAXN 200005 int parent[MAXN]; int val[MAXN]; // 并查集查找路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } int main() { int n, m; scanf(%d %d, n, m); int nonzero 0; for (int i 1; i n; i) { scanf(%d, val[i]); parent[i] i; if (val[i] ! 0) nonzero; } // 哨兵位置方便边界处理 parent[n 1] n 1; while (m--) { int a, b; scanf(%d %d, a, b); if (a b) { int t a; a b; b t; } int rb find(b); if (rb ! n 1 val[a] ! 0) { if (val[rb] 0) { // b的值已经被移走了需要找到下一个非零位置 rb find(rb 1); } if (rb ! n 1) { val[rb] val[a]; if (val[a] ! 0) nonzero--; // a位置变零 val[a] 0; parent[a] find(a 1); // a位置从链表中移除 if (val[rb] ! 0 rb ! a) { // 检查rb是否变零变零则移出 if (val[rb] 0) { nonzero--; parent[rb] find(rb 1); } } } } printf(%d\n, nonzero); } return 0; }这道题我最开始写的时候犯了一个错误没有考虑值累加之后可能恰好变成0的情况。比如某个位置上本来是0但是根据操作规则它不能被当作有效目标位置我却没有处理导致计数错误。后来通过构造边界数据才发现问题加上了对累加结果是否为0的判断才通过。这个题目本质上是一个数据结构优化题看起来是模拟实际上是并查集维护动态删除场景。复试机试里面有不少这种包装过的题目表面是模拟实际需要你想到更优的数据结构所以平时训练时不要只满足于把样例过掉要养成估算复杂度的习惯。3.2 题目二异或加解密题目描述给定一个由字符组成的字符串S和一个整数密钥key对字符串中的每个字符做异或操作规则是S[i] ^ key输出结果字符串。而后给定一个加密后的结果要求你还原原始字符串。这道题其实就是一个异或运算性质的应用比较简单。核心知识点就是异或运算的三个性质交换律、结合律、以及一个数连续异或两次同一个数会回到本身。所以加密和解密是完全相同的操作给定密文和密钥再对每个字符异或一次key就能还原明文。我当时写的代码如下#include stdio.h #include string.h int main() { char s[1005]; int key; scanf(%s, s); scanf(%d, key); int len strlen(s); for (int i 0; i len; i) { char c s[i] ^ (key 0xFF); printf(%c, c); } printf(\n); return 0; }这里有一个细节容易踩坑key是int类型而字符是char类型直接s[i] ^ key在做整数提升时如果key的高位不是0最终结果中可能会产生一些超出可打印ASCII范围的值。虽然题目通常允许输出任意字节但如果后续还有字符判断操作就会出问题。稳妥的做法是把key转换到低8位也就是key 0xFF确保异或结果落在单字节范围内。这道题虽然简单但它代表了一类网安特色题。很多同学觉得这类题简单得像送分题恰恰在这种题目上容易大意比如没有考虑多组测试数据输入、没有注意字符串首位不能有空格等格式要求。我在这类题上的原则是代码再简单提交之前也要仔细读一遍题目里的输出格式要求格式错误就直接零分。从复习角度来说这类题最值得练习的是位运算与字符处理结合的组合按位与、按位或、异或、移位操作在不同题目里会组合出各种花样的要求。把常见的位运算操作练熟遇到变体就不会慌。3.3 题目三字符串数组的最长公共前缀题目描述给定n个字符串求它们的最长公共前缀。如果有多个结果取字典序最小的那个。如果不存在公共前缀输出空行。这道题其实是经典的水平扫描法但加了一个字典序最小的附加条件很多人会在这里翻车。先说基本解法可以每次取相邻两个字符串的公共前缀不断缩小结果范围。时间复杂度O(S)S是所有字符串的总长度。空间复杂度O(1)。但要注意字典序最小这个条件。一开始我的思路是求出公共前缀之后再去找所有字符串中是否有更短的公共前缀然后取字典序最小。后来发现不对因为公共前缀本身是唯一的不需要找多个这个条件真正限制的地方在于当存在多个字符串全体共享的公共前缀时结果只有一个但题目可能是要求你从所有可能的前缀候选中选字典序最小者因此必须对所有前缀候选进行字典序比较。重新分析之后其实最稳的做法是先排序然后只比较排序后第一个和最后一个字符串的公共前缀这就是所有字符串的最长公共前缀。因为字典序排序后第一个和最后一个字符串共同拥有的前缀就是所有字符串共同拥有的前缀的极端情况。如果这两个的前缀长度是L那他们之间的所有字符串也至少有长度为L的公共前缀。这里还有一个细节空行怎么输出要求是不存在公共前缀时输出空行。很多人用printf(\n)就能过但有些OJ要求输出一个空字符串也就是直接换行这两种做法是一致的。关键是不要画蛇添足加额外的空格。我之前在C语言里处理字符串比较和复制时踩过一个坑用strcpy之前要确保目标数组足够大否则会越界。复试OJ上这类错误往往不报编译错误而是运行时报错系统给出的信息可能是运行时错误或段错误排查起来特别耗时。后来我养成了一个习惯凡是用到字符串拷贝优先用strncpy并手动加\0避免越界问题。3.4 今天训练的总结三道题做下来用时大概90分钟一道题卡了比较久就是并查集那道其余都比较顺畅。复盘下来有几个值得记录的发现懂得算法原理和能在有限时间内写出无Bug的实现中间隔着很大的训练量。并查集我会写但一加上具体操作场景还是会乱关键还是在链表的删除逻辑上思考不够清楚。简单题不能大意异或题目里数据类型转换问题要是没处理好输出结果可能完全不可读。字符串题的核心难点永远是边界处理和内存安全而不是算法本身。4. 高频失分点与实战对策4.1 超时问题一开始就要算复杂度复试机试给的时间通常是1到2小时题目数量4到6道。很多同学一开始写代码不估算复杂度上去就是暴力模拟小数据能过大数据直接超时。我自己的经验是看到题先花30秒估算一下数据范围。如果数组长度是10^5O(n^2)的算法基本没戏如果长度是10^3O(n^2)勉强可以如果长度是10^5但操作次数也是10^5那必须想到O(nlogn)甚至O(n)的解法。如果你平时练习时估算复杂度的习惯还没养成就在每道题提交之前问自己三个问题我的算法在最好情况下的复杂度是多少最坏情况下是多少最坏情况的输入在评测数据中可能出现吗只要最坏情况过不了就得想优化的方法。另一个和超时紧密相关的坑是输入输出效率。使用C语言的scanf和printf通常没问题但如果数据量大循环中频繁调用就会变慢。必要的时候可以用getchar自己写快读不过复试机试一般不太需要这么极致的优化除非数据范围给得特别大。4.2 数组越界与初始化问题我在训练中遇到过不下十次本地没问题OJ上运行错误的情况绝大多数是数组越界或者未初始化导致的。常见的错误有三种。第一种是数组开小了题目说最多输入n个但是你在处理过程中会访问到第n1个位置的哨兵节点没留出位置就会越界。第二种是二维数组的维度搞反了行当列、列当行很容易造成访问越界。第三种是定义了局部数组但没有初始化里面的值是随机的在一些需要默认值为0或默认值为-1的场景中会导致错误逻辑。解决办法也很朴素在本地写代码时把数组大小开成题目上限多一点留几个哨兵位置对需要初始化的数组不管是全局数组还是局部数组用循环或者memset显式清零写完代码后重点检查所有数组下标的最大可能取值养成数组下标永远不要越界的条件反射。4.3 调试技巧和编成习惯复试机试时你没法使用IDE的图形化调试器很多时候只能靠打印和读代码来排查问题。我平时训练用的几个土办法很有效分段打印法。如果某个答案不对就先在关键计算节点打印中间结果观察哪个步骤开始跑偏。小数据手算对照。构造一个小的测试用例用手算一遍期望的输出然后和程序的实际输出对比。这样可以快速判断是算法逻辑错还是代码实现错。构造边界数据。特别关注空输入、单元素输入、最大值输入、重复值输入这些边界情况最容易暴露问题。还有一个建议是平时就规范命名变量不要用a1、b_2这种毫无意义的名称。复试机试时长有限变量名太难记容易自己把自己绕晕。我用idx、pos、nonzero_cnt、parent这类有语义的名字代码写出来自己看得懂调试的时候也省时间。4.4 限时训练的三个要点到了Day25这个阶段纯粹刷题已经不够了必须限时。我每天的安排是挑3到4道难度递增的题给自己计时90分钟期间不看题解、不翻笔记完全模拟考试状态。训练结束后再花半小时复盘。复盘的时候不要只看自己做没做对要看这三个问题第一时间分配是否合理。如果前面的简单题花了太多时间后面的中等题就会紧张下次遇到简单题就要强迫自己加速。第二卡在哪一个环节。是做不出来还是做错了还是做出来了但没时间检查不同环节对应的应对策略不同。做不出来是知识点有盲区需要回去补基础做错了可能是审题或边界问题需要专门训练细致程度没时间检查则是速度问题需要多练。第三考场上的心态变化。限时训练很真实地模拟了考场的紧张感如果每次训练都因为紧张而失误那就要刻意练习深呼吸、提醒自己按部就班地分析题目。这些听起来很玄但确实影响实际发挥。5. 冲刺阶段的每日执行清单Day25之后的这几天别再做新题了。新题做不完而且容易打击信心。我当时给自己列的每日清单是这样上午用一套限时训练保持手感题目难度和正式机试接近。下午只做三件小事第一复习自己整理过的错题本重点看易错点和格式要求第二把并查集、二分查找、二叉树遍历、最长公共子序列这些高频算法的模板代码手写一遍不看任何参考确保肌肉记忆是准确的第三回顾一遍网安特色题的常见套路就是前面提到的异或、编码、进制转换、简单密码学逻辑这几类每类找一两个最经典的题目重新过一遍。晚上不写代码了翻一翻常见OJ报错信息的含义。比如Compile Error是编译错误Runtime Error是运行错误Time Limit Exceeded是超时Wrong Answer是结果错误。这些英文提示在考场上看到不要慌对应到解决方案就能很快定位。如果时间富余可以练一练手写伪代码的能力。复试机试有时候会要求先描述思路再写代码或者面试官会问你的解题思路。能清晰地把思路表述出来和能写出正确代码一样重要。我在家训练时每做完一道题会自己在心里或者对着手机录音用一分钟讲一遍这题的考点是什么、我为什么用这个算法、复杂度是多少。坚持几天后上机的时候明显感觉思路更清晰不会边写边想。我个人在Day25这天最大的体会是要舍得放弃。如果一道题10分钟还没有任何靠谱的思路果断跳到下一道先把能拿的分拿到手。复试机试的题目通常有梯度前面基础题的分数占比很高把基础题全部做对就已经可以拿到一大半分后面的中等题和压轴题是加分项不是必选项。很多同学在压轴题上死磕最后连基础题都没时间检查这种策略非常不划算。还有就是考前一定要把编译环境相关的细节确认清楚。用哪个编译器版本支持C99还是C11是否允许使用gets有没有bits/stdc.h这种头文件这些信息虽然琐碎但直接影响你现场写代码的方式。我在某次模拟训练的时候因为使用了某个高版本编辑器特有的语法换到评测环境后直接编译报错折腾了五分钟才改回来那五分钟如果在考场上就是实打实的分数损失。最后再分享一个实战技巧在评测系统上做题时代码提交前最后五秒别去改代码。我自己就干过一件蠢事——提交前觉得某个变量名不顺眼手一快改错了结果从AC直接变成WA然后疯狂怀疑自己改出了什么隐藏Bug在考场上浪费了十几分钟。除非是明确的语法错误否则不要临时改动已经测试正常的代码。这是很多考过机试的人都会踩的坑希望你能绕过去。