每年一到三四月份就是各大单位集中组织计算机能力测试的高峰期C机试又是其中最常出现的科目。我最近刚带完一轮针对机试的突击训练自己也完整模拟了一遍整套真题流程。这次要写的是 26.3.12 场次的 t88 到 t92总共五道题。这五题很有意思覆盖了指针、字符串处理、排序、质数判断、二分查找这几个机试高频考点难度梯度也拉得比较开有送分题也有需要静下心推演的题目。对于准备 C 机试的朋友来说这一套题如果吃透了应付大多数单位的机试基本问题不大。我写这篇文章不是简单把代码贴一遍了事。我会把每一题的核心考点、设计思路、我当时踩过的坑、最后落地可用的代码全部拆开讲清楚也会把一些机试实战中的时间分配、编译环境选择、边界测试心得一并分享出来。内容偏向实战复盘适合正在备战机试的在校学生也适合工作后需要参加晋升或职称机考的开发者。1. 机试全貌与题目布局1.1 这套题到底在考什么t88 到 t92 这五道题从编号上就能看出是同一场次中连续的一套题。机试的出题逻辑通常不是漫无边际地乱考而是会按照“基础语法、数据结构、经典算法、数学思维、综合应用”这条主线来设计。这套题也遵循了这个规律t88 考指针与字符串考察 C 最底层的内存操作能力t89 考字符串转换与数组处理偏向于输入解析和边界处理t90 考排序算法从手写冒泡到 sort 库函数的选型t91 考质数判断与快速幂属于典型数论入门t92 考二分查找是算法题里最常出现的查找范式。五道题从易到难我实际做下来的体感是t88 和 t89 属于热身题需要求稳拿满分t90 和 t91 是分水岭能筛选出有基本功的人t92 是拉开差距的题目虽然代码量不大但边界条件稍不注意就会扣分。1.2 机试环境的确定性不能忽视机试和平时开发不一样环境是固定的。我这次模拟用的是 Windows Visual Studio 2022 社区版编译标准选的 C17。虽然 g 在 Linux 环境下也能编译通过这套题的代码但机试阅卷系统往往以 Windows 平台为准。有几个环境细节特别重要#include bits/stdc.h这种万能头文件在 VS 里默认是不存在的必须老老实实包含具体头文件scanf/printf 和 cin/cout 混用的时候要注意如果关闭了同步ios::sync_with_stdio(false)混用很可能导致输入顺序错乱机试系统通常要求从标准输入读取数据向标准输出写入结果不需要做文件读写。还有一个容易被忽略的点VS 默认使用的是 UTF-8 编码但如果系统区域设置为中文控制台窗口的代码页可能是 GBK。如果题目要求输出中文字符串最好用英文输出或者提前设置setlocale(LC_ALL, chs)否则会出现乱码导致误判。环境项推荐配置说明IDEVisual Studio 2022 / Code::BlocksVS 调试功能强Code::Blocks 轻量标准C17兼容机试阅卷系统的同时支持现代特性输入输出标准输入输出不要写文件读写除非题目明确要求编码UTF-8 / 英文输出避免中文字符编码不一致导致的误判1.3 做题顺序与时间分配策略机试时间一般给得比较紧2 小时做 5 题平均每题 24 分钟。我的建议是不要死磕顺序拿到题先花两分钟把所有题都扫一遍按难度排序再动手。我这次的做题顺序是t88 → t89 → t90 → t91 → t92。理由很简单t88 和 t89 是基础题先把该拿的分稳稳装进口袋心态会稳很多。t90 的排序是中等难度写完后可以缓一口气。t91 的质数判断如果优化思路清晰十分钟就能写完。最后集中精力做 t92 的二分查找。核心原则是永远不要在某一题上卡超过 30 分钟。如果一道题思路进了死胡同先跳过等做完其他题再回头用暴力解法兜底。2. t88指针与字符串处理2.1 题目还原与题意拆解t88 的题目是一道经典指针应用题要求实现一个函数接收一个 C 风格字符串char*或const char*统计其中不同字符的个数并且将只出现一次的字符按原顺序输出。题目会给定一段测试代码使用指针遍历字符串不能借助std::string的算法库。这种题非常典型机试中的同学容易出现两个问题一是对 C 风格字符串的结尾符\0不够敏感。写循环条件的时候经常写成for(int i 0; i strlen(str); i)这在每轮循环都要调用一次strlen时间复杂度会从 O(n) 变成 O(n²)数据量一大就会超时。正确的姿势是直接判断*p ! \0或者先算出长度存到变量里。二是指针自增和取值运算符的优先级搞混。*p和(*p)是两个完全不同的操作前者是先取p指向的值、再移动指针后者是把p指向的值加一。新手在这里非常容易出错。2.2 指针遍历的两种正确写法第一种是下标方式虽然题目要求用指针但很多同学习惯性用下标其实效果等价只是不够“指针”int countUnique(const char* str) { if (str nullptr) return 0; int cnt[256] {0}; int len 0; while (str[len] ! \0) { cnt[(unsigned char)str[len]]; len; } int unique 0; for (int i 0; i len; i) { if (cnt[(unsigned char)str[i]] 1) { unique; } } return unique; }这里有个细节char类型在部分平台可能带符号位直接用char做数组下标会越界。用(unsigned char)强制转换后再作为下标是必须的这算是一个隐藏的坑。第二种是纯指针方式更贴合题目要求int countUnique(const char* str) { if (str nullptr) return 0; int cnt[256] {0}; const char* p str; while (*p ! \0) { cnt[(unsigned char)*p]; p; } int unique 0; for (p str; *p ! \0; p) { if (cnt[(unsigned char)*p] 1) { unique; } } return unique; }2.3 指针参数设计的两个原则这道题如果要求写函数而不是完整程序函数的参数设计也需要讲究。接收字符串时用const char*比char*更安全因为函数只读数据不修改内容。如果阅卷系统中有代码审查环节const的加分效应会很明显。还有一个原则是指针参数永远要先判空。很多同学写指针题时忽略了nullptr的判断一旦测试数据传入空指针程序直接崩溃这一题基本就白卷了。2.4 我踩过的坑数组越界的隐蔽来源我第一版代码用了全局数组int cnt[26]题目测试用例也全是小写字母所以当时跑得很顺畅。但在 debug 模式下偶然输入了一个大写字母cnt[A]的下标是 65直接越界。虽然数组开在全局区越界不一定崩溃但结果肯定是错的。后来我把数组改成int cnt[256]把所有单字节字符都覆盖了。最好再写一个assert(str ! nullptr)方便在 debug 阶段就发现问题。3. t89字符串数组转换与算术解析3.1 题目要求与多个易错点t89 是一个字符串处理题题目要求输入一串由数字字符和逗号组成的字符串例如123,456,789把每个由逗号分隔的子串转换成整数存入数组然后求和输出。这题看着简单实际上隐藏了大量字符串转数字的细节空字符串处理如果输入是空串应该输出 0 还是报错机试阅卷时通常约定为空串输出 0连续逗号1,,2这种情况中间的空段应该按 0 处理还是跳过不同题目的要求可能不同必须仔细读题干数字溢出子串转 int 后如果超过INT_MAX需要改用long long负数支持如果数字包含负号解析逻辑需要额外处理。用一个表格来说明常见边界输入与合理输出输入期望输出说明1,2,36常规情况0空串约定输出 01,,23连续逗号空段按 0 处理123456789012溢出需用 long long 或提示错误-1,21负号解析3.2 解析实现手动解析还是直接用 strtok网上很多代码会推荐strtok分割字符串但在 C 机试场景中我不太建议这么做。strtok会修改原字符串把分隔符替换成\0如果原字符串是const char*类型的字面量直接调用strtok会导致只读内存修改程序崩溃。C 更稳的写法是用istringstream加getline或者直接手写解析循环。我用的方案是手写解析核心逻辑很简单#include iostream #include string #include vector using namespace std; vectorlong long parseNumbers(const string s) { vectorlong long res; long long cur 0; bool inNum false; bool negative false; for (char c : s) { if (c ,) { if (inNum) res.push_back(negative ? -cur : cur); else res.push_back(0); cur 0; inNum false; negative false; } else if (c -) { negative true; inNum true; } else if (c 0 c 9) { cur cur * 10 (c - 0); inNum true; } // 非法字符直接忽略或者根据题目要求报错 } if (inNum) res.push_back(negative ? -cur : cur); else if (s.size() 0 s.back() ,) res.push_back(0); return res; } int main() { string input; while (getline(cin, input)) { vectorlong long nums parseNumbers(input); long long sum 0; for (long long v : nums) sum v; cout sum endl; } return 0; }这里有个技巧用bool inNum来记录当前是否处于一个数字段中避免连续逗号导致多压入一个 0。很多同学在处理1,,2时遇到第一个逗号 push 了 1遇到第二个逗号看到inNum false就不 push但此时1,和,的语义是有区别的用inNum状态就能统一正确判断。3.3 getline 循环读入的注意事项机试的输入经常有多行每行一组测试数据。用while (getline(cin, input))是最稳的写法。但有一个容易翻车的点如果前面用了cin n读整数后面再用getline第一行getline会读到一个空串因为缓冲区里残留着换行符。解决方案是在cin n后加一句cin.ignore()或者统一用getline读整行再解析。3.4 long long 的选择与溢出边界这道题我用long long存储中间结果主要是考虑解析过程中cur cur * 10 digit可能临时溢出。如果题目的子串最长是 10 位数字int 刚好够但如果出现 11 位int 就装不下了。机试阅卷数据经常会刻意放一个极长的数字测边界所以预先使用long long是性价比最高的防御。不过long long也不是无限大如果子串超过 19 位还是会溢出。在实际代码中我加了一个判断如果cur (LLONG_MAX - digit) / 10就标记为溢出。这是从工程化角度考虑的虽然机试中几乎不会遇到这种极值。4. t90排序算法与库函数选型4.1 题目描述与两种解题路线t90 是一道排序题输入 n 个整数要求从小到大输出排序结果。限制条件是n 的最大值可达 10 万且相同值的元素需要保持输入时的相对顺序。这个“保持相对顺序”的要求非常关键它直接决定了你能否用库函数sort解决。std::sort是不稳定排序相同元素的相对顺序不保证。而std::stable_sort是稳定排序时间复杂度同样是 O(n log n)可以完美满足要求。不过很多同学在机试时记忆混淆搞不清sort和stable_sort的区别直接用了sort导致在重复元素很多的时候输出顺序不符被扣掉不少分。排序算法时间复杂度稳定性适用场景冒泡排序O(n²)稳定n ≤ 1000 时能用快速排序sortO(n log n)不稳定追求速度且无稳定性要求归并排序stable_sortO(n log n)稳定需要保持相同元素顺序计数排序桶排序特例O(n k)稳定数据范围小且集中4.2 手写冒泡排序的完整实现与优化既然题目考察排序有些阅卷系统会强制要求手写排序算法。手写冒泡是最直观的方案但如果不加优化10 万个元素绝对会超时。冒泡排序的常规写法是两层循环外层控制轮数内层做相邻比较和交换。优化点主要有两个如果某一轮没有发生任何交换说明数组已经有序提前终止外层循环记录最后一次交换的位置下一轮只需要比较到这个位置为止因为该位置之后的元素已经有序。当然n 达到 10 万时即便是优化后的冒泡也扛不住所以这道题的最优解是手写快速排序或者直接用stable_sort。我给出的完整手写冒泡用于平时练习理解机上实战还是用库函数更稳#include iostream #include vector using namespace std; void bubbleSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - i - 1; j) { if (arr[j] arr[j 1]) { swap(arr[j], arr[j 1]); swapped true; } } if (!swapped) break; } }面试官或阅卷系统如果要求手写写快排的得分会明显高于冒泡。我现场写的快排是基于 Lomuto 分区方案的递归版本代码量不大关键是注意基准值的选取——如果基准每次都取第一个元素遇到已有序数组会退化到 O(n²)。稳妥起见三数取中法最保险。4.3 库函数 sort 与 stable_sort 的底层逻辑机试是允许使用标准库的只要题目不明确禁止。std::sort通常在数据量小时使用插入排序数据量大时使用快速排序还有堆排序兜底所以整体性能非常稳定。但它不稳定这是硬伤。std::stable_sort的底层是归并排序时间复杂度稳定在 O(n log n)且是稳定排序。它额外需要 O(n) 的辅助空间不过对于 10 万级别的数据来说内存占用非常小完全不是问题。实战建议如果题目没有明确要求手写排序直接用std::stable_sort既满足稳定性要求效率也达标。如果 n 特别大且数据范围很小比如 0 到 100 之间用计数排序能做到 O(n)效率更高。#include iostream #include vector #include algorithm using namespace std; int main() { int n; cin n; vectorint arr(n); for (int i 0; i n; i) { cin arr[i]; } stable_sort(arr.begin(), arr.end()); for (int i 0; i n; i) { if (i 0) cout ; cout arr[i]; } cout endl; return 0; }4.4 与快速幂算法的联动思考这道题排序本身难度不大但在机试的后续题目特别是 t91 的质数判断中排序数组往往能配合数学性质降低复杂度。比如判断一个数组中有多少对质数可以先排序再用双指针扫描或者对每个元素判断质数时利用递增特性提前退出。所以 t90 真正的价值不只是排序本身而是为后续题目提供一个有序、稳定的数据预处理基础。这也是为什么机关机试总喜欢把排序题放在中间位置——它承上启下。5. t91质数判断的数学精妙与快速幂实现5.1 题目要求判断质数的基础版与升级版t91 是一道关于质数的题目。基础版要求判断输入的正整数 n 是否为质数升级版则要求输出 [m, n] 区间内所有质数并计算它们的和。这类题目在机试中出现频率极高几乎可以说是必考题型。最朴素的试除法是从 2 遍历到 n-1看是否存在因子。对于单次查询来说没问题但如果 n 达到 10⁷ 级别且需要判断区间内所有数这种做法的复杂度不可接受。这里就需要引入质数判断的经典优化只需要遍历到 √n因为如果 n 存在大于 √n 的因子必然存在小于 √n 的配对因子排除偶数和 2 的倍数步长从 1 改为 2循环次数减半6k ± 1 规则大于 3 的质数必然分布在 6 的倍数两侧进一步压缩循环次数。5.2 试除法优化后的完整代码#include iostream #include cmath using namespace std; bool isPrime(int n) { if (n 1) return false; if (n 2 || n 3) return true; if (n % 2 0 || n % 3 0) return false; for (int i 5; i * i n; i 6) { if (n % i 0 || n % (i 2) 0) return false; } return true; } int main() { int m, n; cin m n; long long sum 0; for (int i m; i n; i) { if (isPrime(i)) sum i; } cout sum endl; return 0; }这个版本对单个数的判断时间是 O(√n / 6)已经非常快了。但区间 [1, 10⁷] 内每个数都判断一次总体时间复杂度依然高。真正的大规模区间质数统计必须用筛法。5.3 埃氏筛区间质数统计的主流方案埃拉托斯特尼筛法的核心思想是从 2 开始每遇到一个质数就把它的倍数全部标记为合数。标记完成后所有未被标记的数就是质数。#include iostream #include vector using namespace std; vectorint sieve(int n) { vectorint ans; vectorbool isComposite(n 1, false); for (int i 2; i n; i) { if (!isComposite[i]) { ans.push_back(i); if ((long long)i * i n) { for (int j i * i; j n; j i) { isComposite[j] true; } } } } return ans; }一个容易被人忽略的优化是内层循环从i * i开始而不是从i * 2开始。因为 i 的较小倍数已经被更小的质数标记过了不需要重复标记。这一点在数据量大时能节省大量时间。5.4 快速幂为什么质数题会牵扯幂运算很多质数相关的题目会同时考察快速幂。比如有一种题判断a^n mod p是否为质数或者用费马小定理做素性探测。快速幂的核心思想是把指数二进制拆分通过迭代平方来减少乘法次数把 O(n) 的时间降为 O(log n)。long long quickPow(long long a, long long b, long long mod) { long long result 1; a % mod; while (b 0) { if (b 1) { result result * a % mod; } a a * a % mod; b 1; } return result; }这段代码的骨架非常重要在机试中几乎是“标准模板”级别。它的关键点有三个一是每步取模防止溢出二是用位运算判断最低位是否为 1三是平方操作和右移操作的顺序不能被调换。5.5 实测中遇到的质数范围与溢出问题我在实际测试时把区间设到了 [1, 10⁷]埃氏筛的 vector 大小开到 10000001内存占用约 10 MB运行速度在 0.1 秒左右完全满足机试要求。但如果用bool数组直接开在栈上可能会因为栈空间不足导致崩溃。建议要么用全局数组要么用vectorbool后者还有空间优化的机制。还有一点埃氏筛里isComposite最好用vectorbool而不是vectorchar或vectorint因为vectorbool做了位压缩内存能减少到原来的 1/8。当然位压缩会带来一定的访问开销但机试数据量下完全可接受。6. t92二分查找的边界哲学6.1 题目描述与前置条件t92 是一道二分查找题。输入一个有序数组和一个目标值要求返回目标值在数组中的起始位置和结束位置。如果不存在返回 “-1 -1”。这是二分查找的经典变种——查找左右边界。二分查找本身逻辑简单但边界条件极易出错。机试中这题的通过率通常不高主要原因就是很多人死记模板没有理解循环不变量的含义。一旦题目稍微变化比如找左边界、找右边界、或者查找插入位置就不知道怎么改了。6.2 左边界与右边界的统一写法找左边界的核心思想是当arr[mid] target时左边界不可能在 mid 右边所以让right mid否则让left mid 1。注意这里用的是左闭右闭区间还是左闭右开区间必须全程一致。推荐写法是左闭右闭然后单独封装两个函数#include iostream #include vector using namespace std; int findLeft(vectorint arr, int target) { int left 0, right arr.size(); // 左闭右开 while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; } else { right mid; } } return left; } int findRight(vectorint arr, int target) { int left 0, right arr.size(); // 左闭右开 while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; } else { right mid; } } return left - 1; }调用时先算l findLeft(arr, target)再算r findRight(arr, target)。如果l arr.size()或arr[l] ! target说明不存在输出 “-1 -1”。否则输出l和r。6.3 二分查找的三个经典坑位第一个坑是死循环。用左闭右闭区间时如果mid (left right) / 2且left right是奇数mid会偏向左侧。当right mid时可能出现left和right始终无法收敛的情况。解决方法是统一用左闭右开区间并在循环条件里写left right这样能天然规避大部分死循环问题。第二个坑是整数溢出。mid (left right) / 2在 left 和 right 都接近INT_MAX时left right可能溢出变成负数。正确写法是mid left (right - left) / 2。这是很多机试代码即使看起来逻辑正确也会超时的隐藏原因。第三个坑是二分的适用前提数组必须是有序的。题目明确说“有序数组”但如果输入是降序直接套升序逻辑就会全错。答题前先确认数组的排序方向或者先做一次升序排序。6.4 扩展思考二分答案更值得掌握t92 考的是基础二分查找但机试想拿高分建议进一步掌握“二分答案”的思路。比如给定一个最大值阈值判断能否在某个限制条件下完成任务这类题往往是二分套贪心或二分套动态规划。举个例子有一段长度为 n 的绳子数组要切成至少 k 段长度相同的小段问每段最长能多长。这个问题看似复杂实际用二分枚举最终长度即可。每次枚举一个长度 mid统计能切出多少段如果段数大于等于 k就提高 mid否则降低 mid。二分答案的核心是“可行性判断函数”这个函数闭着眼睛写也能保证二分一定能收敛。掌握这个思路之后二分能解的题就从一个具体查找问题扩展成了一整个算法类别。7. 调试排错与机试实战心得7.1 我遇到过的编译错误与运行时错误这套题模拟训练下来除了算法本身编译和运行阶段也踩了不少坑。这里整理一个速查表给备战机试的同学做一个参考错误类型典型信息原因与对策编译错误nullptr was not declared编译标准未设为 C11 以上检查项目设置编译错误cannot open include file: stdio.hVS 未安装 C 桌面开发组件运行时错误stack overflow递归过深或数组开在栈区改用堆区或全局区运行时错误segmentation fault指针未判空、数组越界检查下标范围超时Time Limit Exceeded用 O(n²) 算法处理了 10⁵ 级数据改用 O(n log n) 或更低答案错误结果差 1二分边界或者质数判断漏了 n2、n3 的情况7.2 时间分配与心理建设机试中很多人不是不会做而是时间前松后紧。我在前面也提过先把送分题拿下再解决中等题最后死磕难题。这里再补充一个细节每做完一道题花 10 秒钟造一个边界用例自测。比如 t89 的连续逗号t91 的负数输入t92 的目标值在数组两端都能快速暴露隐藏 bug。如果某道题卡了超过 20 分钟果断跳过。机试的计分规则一般不按题目难度加权而是按通过数据组打分。一道题你只过了一半数据得一半分但如果你把全部时间耗在这题上后面三道容易题可能直接得零分。怎么算都不划算。7.3 这套题在真实场景中的延伸价值t88 到 t92 这五道题表面是考试题实际是 C 工程中最常用技能的浓缩。指针操作是掌握现代 C 的基础字符串处理是日常开发的常态排序是数据预处理的基石质数判断和二分查找则代表了两类重要的算法思维——数学建模与空间收缩。我把这套题刷下来的最大感触是死记代码模板没有意义必须理解每个循环变量的边界意义、每个优化步骤背后的复杂度变化。机试能拿多少分基本就是你平时写代码时想得有多深的一个侧写。如果你正在准备近期的机试拿这套 t88-t92 做模拟练习是个不错的选择。做题时给自己掐表、把所有自测样例跑一遍、再对照我这篇文章里的优化点查漏补缺坚持一段时间上了考场心里会踏实很多。
C++机试真题解析：从指针到二分查找的五大高频考点实战复盘
每年一到三四月份就是各大单位集中组织计算机能力测试的高峰期C机试又是其中最常出现的科目。我最近刚带完一轮针对机试的突击训练自己也完整模拟了一遍整套真题流程。这次要写的是 26.3.12 场次的 t88 到 t92总共五道题。这五题很有意思覆盖了指针、字符串处理、排序、质数判断、二分查找这几个机试高频考点难度梯度也拉得比较开有送分题也有需要静下心推演的题目。对于准备 C 机试的朋友来说这一套题如果吃透了应付大多数单位的机试基本问题不大。我写这篇文章不是简单把代码贴一遍了事。我会把每一题的核心考点、设计思路、我当时踩过的坑、最后落地可用的代码全部拆开讲清楚也会把一些机试实战中的时间分配、编译环境选择、边界测试心得一并分享出来。内容偏向实战复盘适合正在备战机试的在校学生也适合工作后需要参加晋升或职称机考的开发者。1. 机试全貌与题目布局1.1 这套题到底在考什么t88 到 t92 这五道题从编号上就能看出是同一场次中连续的一套题。机试的出题逻辑通常不是漫无边际地乱考而是会按照“基础语法、数据结构、经典算法、数学思维、综合应用”这条主线来设计。这套题也遵循了这个规律t88 考指针与字符串考察 C 最底层的内存操作能力t89 考字符串转换与数组处理偏向于输入解析和边界处理t90 考排序算法从手写冒泡到 sort 库函数的选型t91 考质数判断与快速幂属于典型数论入门t92 考二分查找是算法题里最常出现的查找范式。五道题从易到难我实际做下来的体感是t88 和 t89 属于热身题需要求稳拿满分t90 和 t91 是分水岭能筛选出有基本功的人t92 是拉开差距的题目虽然代码量不大但边界条件稍不注意就会扣分。1.2 机试环境的确定性不能忽视机试和平时开发不一样环境是固定的。我这次模拟用的是 Windows Visual Studio 2022 社区版编译标准选的 C17。虽然 g 在 Linux 环境下也能编译通过这套题的代码但机试阅卷系统往往以 Windows 平台为准。有几个环境细节特别重要#include bits/stdc.h这种万能头文件在 VS 里默认是不存在的必须老老实实包含具体头文件scanf/printf 和 cin/cout 混用的时候要注意如果关闭了同步ios::sync_with_stdio(false)混用很可能导致输入顺序错乱机试系统通常要求从标准输入读取数据向标准输出写入结果不需要做文件读写。还有一个容易被忽略的点VS 默认使用的是 UTF-8 编码但如果系统区域设置为中文控制台窗口的代码页可能是 GBK。如果题目要求输出中文字符串最好用英文输出或者提前设置setlocale(LC_ALL, chs)否则会出现乱码导致误判。环境项推荐配置说明IDEVisual Studio 2022 / Code::BlocksVS 调试功能强Code::Blocks 轻量标准C17兼容机试阅卷系统的同时支持现代特性输入输出标准输入输出不要写文件读写除非题目明确要求编码UTF-8 / 英文输出避免中文字符编码不一致导致的误判1.3 做题顺序与时间分配策略机试时间一般给得比较紧2 小时做 5 题平均每题 24 分钟。我的建议是不要死磕顺序拿到题先花两分钟把所有题都扫一遍按难度排序再动手。我这次的做题顺序是t88 → t89 → t90 → t91 → t92。理由很简单t88 和 t89 是基础题先把该拿的分稳稳装进口袋心态会稳很多。t90 的排序是中等难度写完后可以缓一口气。t91 的质数判断如果优化思路清晰十分钟就能写完。最后集中精力做 t92 的二分查找。核心原则是永远不要在某一题上卡超过 30 分钟。如果一道题思路进了死胡同先跳过等做完其他题再回头用暴力解法兜底。2. t88指针与字符串处理2.1 题目还原与题意拆解t88 的题目是一道经典指针应用题要求实现一个函数接收一个 C 风格字符串char*或const char*统计其中不同字符的个数并且将只出现一次的字符按原顺序输出。题目会给定一段测试代码使用指针遍历字符串不能借助std::string的算法库。这种题非常典型机试中的同学容易出现两个问题一是对 C 风格字符串的结尾符\0不够敏感。写循环条件的时候经常写成for(int i 0; i strlen(str); i)这在每轮循环都要调用一次strlen时间复杂度会从 O(n) 变成 O(n²)数据量一大就会超时。正确的姿势是直接判断*p ! \0或者先算出长度存到变量里。二是指针自增和取值运算符的优先级搞混。*p和(*p)是两个完全不同的操作前者是先取p指向的值、再移动指针后者是把p指向的值加一。新手在这里非常容易出错。2.2 指针遍历的两种正确写法第一种是下标方式虽然题目要求用指针但很多同学习惯性用下标其实效果等价只是不够“指针”int countUnique(const char* str) { if (str nullptr) return 0; int cnt[256] {0}; int len 0; while (str[len] ! \0) { cnt[(unsigned char)str[len]]; len; } int unique 0; for (int i 0; i len; i) { if (cnt[(unsigned char)str[i]] 1) { unique; } } return unique; }这里有个细节char类型在部分平台可能带符号位直接用char做数组下标会越界。用(unsigned char)强制转换后再作为下标是必须的这算是一个隐藏的坑。第二种是纯指针方式更贴合题目要求int countUnique(const char* str) { if (str nullptr) return 0; int cnt[256] {0}; const char* p str; while (*p ! \0) { cnt[(unsigned char)*p]; p; } int unique 0; for (p str; *p ! \0; p) { if (cnt[(unsigned char)*p] 1) { unique; } } return unique; }2.3 指针参数设计的两个原则这道题如果要求写函数而不是完整程序函数的参数设计也需要讲究。接收字符串时用const char*比char*更安全因为函数只读数据不修改内容。如果阅卷系统中有代码审查环节const的加分效应会很明显。还有一个原则是指针参数永远要先判空。很多同学写指针题时忽略了nullptr的判断一旦测试数据传入空指针程序直接崩溃这一题基本就白卷了。2.4 我踩过的坑数组越界的隐蔽来源我第一版代码用了全局数组int cnt[26]题目测试用例也全是小写字母所以当时跑得很顺畅。但在 debug 模式下偶然输入了一个大写字母cnt[A]的下标是 65直接越界。虽然数组开在全局区越界不一定崩溃但结果肯定是错的。后来我把数组改成int cnt[256]把所有单字节字符都覆盖了。最好再写一个assert(str ! nullptr)方便在 debug 阶段就发现问题。3. t89字符串数组转换与算术解析3.1 题目要求与多个易错点t89 是一个字符串处理题题目要求输入一串由数字字符和逗号组成的字符串例如123,456,789把每个由逗号分隔的子串转换成整数存入数组然后求和输出。这题看着简单实际上隐藏了大量字符串转数字的细节空字符串处理如果输入是空串应该输出 0 还是报错机试阅卷时通常约定为空串输出 0连续逗号1,,2这种情况中间的空段应该按 0 处理还是跳过不同题目的要求可能不同必须仔细读题干数字溢出子串转 int 后如果超过INT_MAX需要改用long long负数支持如果数字包含负号解析逻辑需要额外处理。用一个表格来说明常见边界输入与合理输出输入期望输出说明1,2,36常规情况0空串约定输出 01,,23连续逗号空段按 0 处理123456789012溢出需用 long long 或提示错误-1,21负号解析3.2 解析实现手动解析还是直接用 strtok网上很多代码会推荐strtok分割字符串但在 C 机试场景中我不太建议这么做。strtok会修改原字符串把分隔符替换成\0如果原字符串是const char*类型的字面量直接调用strtok会导致只读内存修改程序崩溃。C 更稳的写法是用istringstream加getline或者直接手写解析循环。我用的方案是手写解析核心逻辑很简单#include iostream #include string #include vector using namespace std; vectorlong long parseNumbers(const string s) { vectorlong long res; long long cur 0; bool inNum false; bool negative false; for (char c : s) { if (c ,) { if (inNum) res.push_back(negative ? -cur : cur); else res.push_back(0); cur 0; inNum false; negative false; } else if (c -) { negative true; inNum true; } else if (c 0 c 9) { cur cur * 10 (c - 0); inNum true; } // 非法字符直接忽略或者根据题目要求报错 } if (inNum) res.push_back(negative ? -cur : cur); else if (s.size() 0 s.back() ,) res.push_back(0); return res; } int main() { string input; while (getline(cin, input)) { vectorlong long nums parseNumbers(input); long long sum 0; for (long long v : nums) sum v; cout sum endl; } return 0; }这里有个技巧用bool inNum来记录当前是否处于一个数字段中避免连续逗号导致多压入一个 0。很多同学在处理1,,2时遇到第一个逗号 push 了 1遇到第二个逗号看到inNum false就不 push但此时1,和,的语义是有区别的用inNum状态就能统一正确判断。3.3 getline 循环读入的注意事项机试的输入经常有多行每行一组测试数据。用while (getline(cin, input))是最稳的写法。但有一个容易翻车的点如果前面用了cin n读整数后面再用getline第一行getline会读到一个空串因为缓冲区里残留着换行符。解决方案是在cin n后加一句cin.ignore()或者统一用getline读整行再解析。3.4 long long 的选择与溢出边界这道题我用long long存储中间结果主要是考虑解析过程中cur cur * 10 digit可能临时溢出。如果题目的子串最长是 10 位数字int 刚好够但如果出现 11 位int 就装不下了。机试阅卷数据经常会刻意放一个极长的数字测边界所以预先使用long long是性价比最高的防御。不过long long也不是无限大如果子串超过 19 位还是会溢出。在实际代码中我加了一个判断如果cur (LLONG_MAX - digit) / 10就标记为溢出。这是从工程化角度考虑的虽然机试中几乎不会遇到这种极值。4. t90排序算法与库函数选型4.1 题目描述与两种解题路线t90 是一道排序题输入 n 个整数要求从小到大输出排序结果。限制条件是n 的最大值可达 10 万且相同值的元素需要保持输入时的相对顺序。这个“保持相对顺序”的要求非常关键它直接决定了你能否用库函数sort解决。std::sort是不稳定排序相同元素的相对顺序不保证。而std::stable_sort是稳定排序时间复杂度同样是 O(n log n)可以完美满足要求。不过很多同学在机试时记忆混淆搞不清sort和stable_sort的区别直接用了sort导致在重复元素很多的时候输出顺序不符被扣掉不少分。排序算法时间复杂度稳定性适用场景冒泡排序O(n²)稳定n ≤ 1000 时能用快速排序sortO(n log n)不稳定追求速度且无稳定性要求归并排序stable_sortO(n log n)稳定需要保持相同元素顺序计数排序桶排序特例O(n k)稳定数据范围小且集中4.2 手写冒泡排序的完整实现与优化既然题目考察排序有些阅卷系统会强制要求手写排序算法。手写冒泡是最直观的方案但如果不加优化10 万个元素绝对会超时。冒泡排序的常规写法是两层循环外层控制轮数内层做相邻比较和交换。优化点主要有两个如果某一轮没有发生任何交换说明数组已经有序提前终止外层循环记录最后一次交换的位置下一轮只需要比较到这个位置为止因为该位置之后的元素已经有序。当然n 达到 10 万时即便是优化后的冒泡也扛不住所以这道题的最优解是手写快速排序或者直接用stable_sort。我给出的完整手写冒泡用于平时练习理解机上实战还是用库函数更稳#include iostream #include vector using namespace std; void bubbleSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - i - 1; j) { if (arr[j] arr[j 1]) { swap(arr[j], arr[j 1]); swapped true; } } if (!swapped) break; } }面试官或阅卷系统如果要求手写写快排的得分会明显高于冒泡。我现场写的快排是基于 Lomuto 分区方案的递归版本代码量不大关键是注意基准值的选取——如果基准每次都取第一个元素遇到已有序数组会退化到 O(n²)。稳妥起见三数取中法最保险。4.3 库函数 sort 与 stable_sort 的底层逻辑机试是允许使用标准库的只要题目不明确禁止。std::sort通常在数据量小时使用插入排序数据量大时使用快速排序还有堆排序兜底所以整体性能非常稳定。但它不稳定这是硬伤。std::stable_sort的底层是归并排序时间复杂度稳定在 O(n log n)且是稳定排序。它额外需要 O(n) 的辅助空间不过对于 10 万级别的数据来说内存占用非常小完全不是问题。实战建议如果题目没有明确要求手写排序直接用std::stable_sort既满足稳定性要求效率也达标。如果 n 特别大且数据范围很小比如 0 到 100 之间用计数排序能做到 O(n)效率更高。#include iostream #include vector #include algorithm using namespace std; int main() { int n; cin n; vectorint arr(n); for (int i 0; i n; i) { cin arr[i]; } stable_sort(arr.begin(), arr.end()); for (int i 0; i n; i) { if (i 0) cout ; cout arr[i]; } cout endl; return 0; }4.4 与快速幂算法的联动思考这道题排序本身难度不大但在机试的后续题目特别是 t91 的质数判断中排序数组往往能配合数学性质降低复杂度。比如判断一个数组中有多少对质数可以先排序再用双指针扫描或者对每个元素判断质数时利用递增特性提前退出。所以 t90 真正的价值不只是排序本身而是为后续题目提供一个有序、稳定的数据预处理基础。这也是为什么机关机试总喜欢把排序题放在中间位置——它承上启下。5. t91质数判断的数学精妙与快速幂实现5.1 题目要求判断质数的基础版与升级版t91 是一道关于质数的题目。基础版要求判断输入的正整数 n 是否为质数升级版则要求输出 [m, n] 区间内所有质数并计算它们的和。这类题目在机试中出现频率极高几乎可以说是必考题型。最朴素的试除法是从 2 遍历到 n-1看是否存在因子。对于单次查询来说没问题但如果 n 达到 10⁷ 级别且需要判断区间内所有数这种做法的复杂度不可接受。这里就需要引入质数判断的经典优化只需要遍历到 √n因为如果 n 存在大于 √n 的因子必然存在小于 √n 的配对因子排除偶数和 2 的倍数步长从 1 改为 2循环次数减半6k ± 1 规则大于 3 的质数必然分布在 6 的倍数两侧进一步压缩循环次数。5.2 试除法优化后的完整代码#include iostream #include cmath using namespace std; bool isPrime(int n) { if (n 1) return false; if (n 2 || n 3) return true; if (n % 2 0 || n % 3 0) return false; for (int i 5; i * i n; i 6) { if (n % i 0 || n % (i 2) 0) return false; } return true; } int main() { int m, n; cin m n; long long sum 0; for (int i m; i n; i) { if (isPrime(i)) sum i; } cout sum endl; return 0; }这个版本对单个数的判断时间是 O(√n / 6)已经非常快了。但区间 [1, 10⁷] 内每个数都判断一次总体时间复杂度依然高。真正的大规模区间质数统计必须用筛法。5.3 埃氏筛区间质数统计的主流方案埃拉托斯特尼筛法的核心思想是从 2 开始每遇到一个质数就把它的倍数全部标记为合数。标记完成后所有未被标记的数就是质数。#include iostream #include vector using namespace std; vectorint sieve(int n) { vectorint ans; vectorbool isComposite(n 1, false); for (int i 2; i n; i) { if (!isComposite[i]) { ans.push_back(i); if ((long long)i * i n) { for (int j i * i; j n; j i) { isComposite[j] true; } } } } return ans; }一个容易被人忽略的优化是内层循环从i * i开始而不是从i * 2开始。因为 i 的较小倍数已经被更小的质数标记过了不需要重复标记。这一点在数据量大时能节省大量时间。5.4 快速幂为什么质数题会牵扯幂运算很多质数相关的题目会同时考察快速幂。比如有一种题判断a^n mod p是否为质数或者用费马小定理做素性探测。快速幂的核心思想是把指数二进制拆分通过迭代平方来减少乘法次数把 O(n) 的时间降为 O(log n)。long long quickPow(long long a, long long b, long long mod) { long long result 1; a % mod; while (b 0) { if (b 1) { result result * a % mod; } a a * a % mod; b 1; } return result; }这段代码的骨架非常重要在机试中几乎是“标准模板”级别。它的关键点有三个一是每步取模防止溢出二是用位运算判断最低位是否为 1三是平方操作和右移操作的顺序不能被调换。5.5 实测中遇到的质数范围与溢出问题我在实际测试时把区间设到了 [1, 10⁷]埃氏筛的 vector 大小开到 10000001内存占用约 10 MB运行速度在 0.1 秒左右完全满足机试要求。但如果用bool数组直接开在栈上可能会因为栈空间不足导致崩溃。建议要么用全局数组要么用vectorbool后者还有空间优化的机制。还有一点埃氏筛里isComposite最好用vectorbool而不是vectorchar或vectorint因为vectorbool做了位压缩内存能减少到原来的 1/8。当然位压缩会带来一定的访问开销但机试数据量下完全可接受。6. t92二分查找的边界哲学6.1 题目描述与前置条件t92 是一道二分查找题。输入一个有序数组和一个目标值要求返回目标值在数组中的起始位置和结束位置。如果不存在返回 “-1 -1”。这是二分查找的经典变种——查找左右边界。二分查找本身逻辑简单但边界条件极易出错。机试中这题的通过率通常不高主要原因就是很多人死记模板没有理解循环不变量的含义。一旦题目稍微变化比如找左边界、找右边界、或者查找插入位置就不知道怎么改了。6.2 左边界与右边界的统一写法找左边界的核心思想是当arr[mid] target时左边界不可能在 mid 右边所以让right mid否则让left mid 1。注意这里用的是左闭右闭区间还是左闭右开区间必须全程一致。推荐写法是左闭右闭然后单独封装两个函数#include iostream #include vector using namespace std; int findLeft(vectorint arr, int target) { int left 0, right arr.size(); // 左闭右开 while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; } else { right mid; } } return left; } int findRight(vectorint arr, int target) { int left 0, right arr.size(); // 左闭右开 while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; } else { right mid; } } return left - 1; }调用时先算l findLeft(arr, target)再算r findRight(arr, target)。如果l arr.size()或arr[l] ! target说明不存在输出 “-1 -1”。否则输出l和r。6.3 二分查找的三个经典坑位第一个坑是死循环。用左闭右闭区间时如果mid (left right) / 2且left right是奇数mid会偏向左侧。当right mid时可能出现left和right始终无法收敛的情况。解决方法是统一用左闭右开区间并在循环条件里写left right这样能天然规避大部分死循环问题。第二个坑是整数溢出。mid (left right) / 2在 left 和 right 都接近INT_MAX时left right可能溢出变成负数。正确写法是mid left (right - left) / 2。这是很多机试代码即使看起来逻辑正确也会超时的隐藏原因。第三个坑是二分的适用前提数组必须是有序的。题目明确说“有序数组”但如果输入是降序直接套升序逻辑就会全错。答题前先确认数组的排序方向或者先做一次升序排序。6.4 扩展思考二分答案更值得掌握t92 考的是基础二分查找但机试想拿高分建议进一步掌握“二分答案”的思路。比如给定一个最大值阈值判断能否在某个限制条件下完成任务这类题往往是二分套贪心或二分套动态规划。举个例子有一段长度为 n 的绳子数组要切成至少 k 段长度相同的小段问每段最长能多长。这个问题看似复杂实际用二分枚举最终长度即可。每次枚举一个长度 mid统计能切出多少段如果段数大于等于 k就提高 mid否则降低 mid。二分答案的核心是“可行性判断函数”这个函数闭着眼睛写也能保证二分一定能收敛。掌握这个思路之后二分能解的题就从一个具体查找问题扩展成了一整个算法类别。7. 调试排错与机试实战心得7.1 我遇到过的编译错误与运行时错误这套题模拟训练下来除了算法本身编译和运行阶段也踩了不少坑。这里整理一个速查表给备战机试的同学做一个参考错误类型典型信息原因与对策编译错误nullptr was not declared编译标准未设为 C11 以上检查项目设置编译错误cannot open include file: stdio.hVS 未安装 C 桌面开发组件运行时错误stack overflow递归过深或数组开在栈区改用堆区或全局区运行时错误segmentation fault指针未判空、数组越界检查下标范围超时Time Limit Exceeded用 O(n²) 算法处理了 10⁵ 级数据改用 O(n log n) 或更低答案错误结果差 1二分边界或者质数判断漏了 n2、n3 的情况7.2 时间分配与心理建设机试中很多人不是不会做而是时间前松后紧。我在前面也提过先把送分题拿下再解决中等题最后死磕难题。这里再补充一个细节每做完一道题花 10 秒钟造一个边界用例自测。比如 t89 的连续逗号t91 的负数输入t92 的目标值在数组两端都能快速暴露隐藏 bug。如果某道题卡了超过 20 分钟果断跳过。机试的计分规则一般不按题目难度加权而是按通过数据组打分。一道题你只过了一半数据得一半分但如果你把全部时间耗在这题上后面三道容易题可能直接得零分。怎么算都不划算。7.3 这套题在真实场景中的延伸价值t88 到 t92 这五道题表面是考试题实际是 C 工程中最常用技能的浓缩。指针操作是掌握现代 C 的基础字符串处理是日常开发的常态排序是数据预处理的基石质数判断和二分查找则代表了两类重要的算法思维——数学建模与空间收缩。我把这套题刷下来的最大感触是死记代码模板没有意义必须理解每个循环变量的边界意义、每个优化步骤背后的复杂度变化。机试能拿多少分基本就是你平时写代码时想得有多深的一个侧写。如果你正在准备近期的机试拿这套 t88-t92 做模拟练习是个不错的选择。做题时给自己掐表、把所有自测样例跑一遍、再对照我这篇文章里的优化点查漏补缺坚持一段时间上了考场心里会踏实很多。