刷在线机试训练题很多人走到第31题这一档就会明显感觉到吃力这不是错觉。前面三十道题绝大多数是单个知识点的“熟练活”字符串反转、数组求和、简单排序题目和代码之间几乎是直线关系想清楚输入就能写。但到了第31题到第40题这个区间题目开始把多个考点缝合在一起考你字符统计里夹着排序规则背包题里多了主件和附件的依赖关系模拟题里还藏着性能陷阱。这篇文章记录的是我用C刷完这一区间的完整心得涵盖字符串、链表、动态规划、贪心、二分、栈、位运算和模拟题。适合刚刷完前三十题、准备往中等难度进阶的人参考也适合那些本地跑得好好的、一提交判题系统就各种报错的人对照排查。1. 先说这个区间的地位为什么31~40是很多人的分水岭1.1 十道题的考点分布总览我先按自己刷题时整理出的版本把这个系列第31~40题的主干考点列一张表。不同题库的题序可能有出入但考察方向基本跑不出这些。题号考察方向核心知识点第31题字符串统计与排序哈希计数、自定义排序、字母序第32题进制转换取模与整除、查表法处理10以上数字第33题链表去重指针操作、哨兵节点、边界处理第34题字符流中第一个不重复字符计数数组、队列、惰性删除第35题主件附件购物问题背包DP、组合状态枚举第36题区间调度贪心、按结束时间排序第37题单峰数组峰值查找二分法、相邻元素比较第38题整数二进制中1的个数位运算、n (n-1)第39题后缀表达式求值栈、左右操作数顺序第40题任务轮转模拟循环队列、批量跳步优化这张表能说明三件事。第一字符串和容器占了接近一半。这非常符合机试风格字符处理代码量不大但对库函数的熟练度要求很高。第二算法思维题集中在35到37题一题背包、一题贪心、一题二分这几题是真正拉分的因为思路一旦卡住后面的时间计划会被全部打乱。第三38到40题看着更偏“实现”没有复杂的数学模型但代码稳定性要求高一个栈弹出顺序写反、一个循环边界没控制好就是一次错误的提交。1.2 从单一语法到组合考点的跨越为什么这个区间会成为分水岭我觉得原因是它完成了两个转变。第一个转变是代码量变大。前10道题的代码大多在二三十行31~40这个区间平均五十行起步像任务轮转模拟这种题甚至要写到八九十行。代码一长变量命名、函数拆分、输入输出结构的清晰度就开始直接影响调试效率再也不是“想到哪写到哪”就能行的了。第二个转变是题目开始有“前置知识”概念。第35题如果不知道“依赖背包”这个模型靠穷举就会超时第37题如果不理解二分查找里边界更新的含义很容易写出死循环。这个阶段的题目不再是“教一个知识点做一道题”而是“默认你已经懂了基础来考你组合应用”。前三十题没打牢的地基到这里就会集中暴露。2. 字符串和容器题占了大头STL用得好120分钟能省出三十分钟2.1 字符统计与排序map帮你省一半事第31题如果考的是“统计字符串中每个字母出现次数按次数降序次数相同按字母升序”直接map配合vector再sort是最顺的思路。#include iostream #include string #include map #include vector #include algorithm using namespace std; int main() { string s; while (getline(cin, s)) { mapchar, int cnt; for (char c : s) { if (isalpha(c)) cnt[c]; } vectorpairchar, int v(cnt.begin(), cnt.end()); sort(v.begin(), v.end(), [](const auto a, const auto b) { if (a.second ! b.second) return a.second b.second; return a.first b.first; }); for (auto p : v) cout p.first; cout endl; } return 0; }这里有个关键点map本身按键有序但题目要求按次数排序所以必须把pair倒进vector再用sort。sort的比较函数用lambda很合适机试环境一般支持C11不需要担心编译器太老。很多人会纠结“用map还是unordered_map”。我建议看题目要不要有序性。第31题最后反正要sort两种容器都行但如果题目要求按字母序输出直接map能省一步排序因为map底层是红黑树键天然有序。容器选型不是玄学是“先看需求再选结构”的基本功。2.2 进制转换查表法比if-else稳“十进制转任意进制”这类题本身不难但非常能看出基本功。新手常见写法是if (digit 10)转字符然后else后面挂一串switch代码又长又容易漏。更稳的做法是查表。string tenToAny(long long n, int radix) { if (n 0) return 0; string table 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ; bool neg false; if (n 0) { neg true; n -n; } string ans; while (n 0) { ans table[n % radix]; n / radix; } if (neg) ans -; reverse(ans.begin(), ans.end()); return ans; }查表法把“数字转字符”的映射统一放进一个字符串n % radix 直接作为下标取字符。这样写即使是36进制也不需要增加任何分支代码。写这一类题我吃过两个亏。一是n等于0时while循环进不去返回空字符串所以开头一定要if (n 0) return 0;。二是进制数比较大时中间结果可能超过int范围参数和取模后的余数都建议用long long。还有一个细节如果题目允许负数符号要单独记录别在取模循环里处理否则余数的正负会把你绕晕。2.3 链表去重哨兵节点救了你不少边界判断链表题在机试里偶尔冒出来最常见的是“删除有序链表中的重复元素”。它最烦的地方是头结点可能被删如果第1个节点和第2个节点值相同直接操作head指针会很容易把链表缝错。我现在的习惯是统一加一个哨兵节点dummy所有删除逻辑都从dummy开始走最后返回dummy.next。struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* deleteDuplicates(ListNode* head) { ListNode dummy(0); dummy.next head; ListNode* prev dummy; while (prev-next) { ListNode* cur prev-next; if (cur-next cur-val cur-next-val) { int v cur-val; while (cur cur-val v) { ListNode* tmp cur; cur cur-next; delete tmp; } prev-next cur; } else { prev prev-next; } } return dummy.next; }注意题目有两种问法一种是“重复节点只保留一个”另一种是“重复节点一个都不留”。两种代码不一样我刷题时把两种情况都写了一遍建议你也这样做因为机试出题人很喜欢在这种地方加一个“全部删除”的限定词。另外在线判题一般只看返回值不要求释放内存但本地练习时delete是个好习惯。链表题多画图特别是删除节点的“前驱指向后继”那一步光在脑子里转很容易转错。2.4 字符流计数数组加队列的惰性删除第34题风格更接近“数据结构设计”向一个字符流里不断插入字符随时查询整个字符流中第一个只出现一次的字符。维护一个计数数组再维护一个队列新字符直接入队排队查询时如果队头字符的计数已经大于1说明它早就不可能是答案直接弹出直到队头是合法字符或队列为空。const int MAX_CHAR 256; int cntArr[MAX_CHAR] {0}; queuechar q; void insertChar(char c) { cntArr[c]; q.push(c); } char firstUnique() { while (!q.empty() cntArr[q.front()] 1) { q.pop(); } return q.empty() ? # : q.front(); }这个写法叫“惰性删除”不要在每次插入时都费力清理队列只在查询时从队头开始清。这样总体复杂度是O(n)每个字符最多入队一次、出队一次效率很好。很多人在这一步会想“能不能用map存次数再用一个vector维护顺序”也能做但代码会变得复杂。数组已经能覆盖所有ASCII字符没必要因为习惯就上容器。真实机试里能用数组解决的问题用数组能少一层抽象就少一层抽象。2.5 这波容器题刷完我重新理解了STL选型这四道题给我的选型经验可以总结成三句话需要有序输出、频繁取最小最大用map/set只做O(1)快速查找用unordered_map普通数组能满足需求时别为了“用容器”而用容器。实际做题时选错容器不是运行速度问题而是逻辑绕进去的问题。比如第34题非要用map存次数代码本身没问题但你在查“第一个不重复字符”时map的有序性帮不上任何忙反而会让你多写不必要的遍历。选容器这件事看着是STL知识实际上是在考你对题目数据结构的抽象能力。3. 动态规划、贪心与二分这个区间真正拉开差距的三道题3.1 依赖背包把“主件附件”打包枚举第35题是经典的“主件附件购物问题”。输入格式通常是这样总钱数N物品数M每个物品有价格v、重要度p、主件编号q。q等于0表示它是主件q大于0表示它是某个主件的附件。每件商品的价值一般定义成价格乘以重要度要在预算内让总价值最大。做法要点很清楚输入时把附件挂到对应主件下dp时把每个主件当成“组合套餐”来枚举。struct Goods { int price 0; int value 0; vectorpairint, int annex; // price, value }; vectorGoods goods(n 1); // 输入时if (q 0) 直接给 goods[i]else goods[q].annex.push_back({v, v * p}); for (int i 1; i n; i) { if (goods[i].price 0) continue; // 跳过附件 for (int j N; j goods[i].price; j--) { // 只买主件 dp[j] max(dp[j], dp[j - goods[i].price] goods[i].value); // 主件 第一个附件 if (goods[i].annex.size() 1) { int p1 goods[i].annex[0].first; int v1 goods[i].annex[0].second; if (j goods[i].price p1) { dp[j] max(dp[j], dp[j - goods[i].price - p1] goods[i].value v1); } } // 主件 第二个附件以及主件 两个附件同理枚举 } }有人会问为什么不把附件当成独立物品放进dp循环因为附件依赖主件独立放进去会出现“附件已买而主件没买”的非法状态。把主件和附件组合成固定套餐本质上是把依赖关系“拍平”让每个状态都是合法购买组合。做这题还要注意一个细节dp初始化到底该用0还是负无穷。如果题目说的是“不超过预算N”dp数组全0就可以因为不买任何东西本身就是合法状态如果题目说“必须刚好用完预算”那就得初始化为负无穷只让dp[0]0。两种语义对应两种做法做之前一定要看清楚题目有没有“恰好”两个字。3.2 区间贪心按结束时间排序这个顺序为什么稳第36题是典型的区间调度给出一堆活动的开始时间和结束时间选出尽可能多的互不冲突的活动。解法从代码上看极其简单按结束时间升序排序扫描一遍当前区间开始时间不早于上次选的结束时间就选它。struct Node { int start; int end; }; sort(acts.begin(), acts.end(), [](const Node a, const Node b) { return a.end b.end; }); int curEnd INT_MIN; int ans 0; for (auto act : acts) { if (act.start curEnd) { ans; curEnd act.end; } }但很多人只记住了排序规则没理解为什么必须按结束时间排。用一个生活场景来想你有一整天时间可以安排会议每个会议有开始和结束时间。如果优先选开始最早的可能选到一个从早上八点一直开到晚上八点的马拉松会议一天直接报废但如果优先选结束最早的那么后面永远留下尽可能多的空闲时间。这就是“局部最优能推向全局最优”的直观来源。机试不需要写严格证明但这个直觉一定要有。因为贪心题的变体很多有些改成了“最少会议室”“最大重叠数”等背后的思考方式都基于“当前选择对后续影响最小”这一条。3.3 二分查找死循环和越界其实是同一件事第37题这类“找单峰数组峰值”的题目本质是二分查找的变体给定一个先递增后递减的数组找最大元素位置。核心判断是mid和mid1的大小关系。int findPeak(vectorint nums) { int l 0, r (int)nums.size() - 1; while (l r) { int mid l (r - l) / 2; if (nums[mid] nums[mid 1]) { l mid 1; } else { r mid; } } return l; }这个写法有几个边界细节值得背下来。循环条件是l r保证了当r是最后一个合法下标时mid一定小于r所以nums[mid 1]不会越界。mid的求法建议写成l (r - l) / 2避免l和r都很大时相加溢出。最容易踩的坑是死循环。二分写死循环几乎都出在“更新lmid时mid向下取整”这种情况下当区间只剩两个元素mid等于左边界如果判断结果让lmidl一直不变循环永远出不来。口诀是更新lmid时mid要向上取整也就是写成mid l (r - l 1) / 2更新rmid时mid向下取整。这个规则记牢二分就能少掉一半的bug。4. 栈、位运算与模拟这三类题考验的是代码稳定性4.1 后缀表达式求值减法的顺序错一次就全错第39题是后缀表达式逆波兰表达式求值。规则只有一句话遇到数字压栈遇到运算符弹出两个数算完再压回去。但减法和除法的操作数顺序特别容易写反。int evalRPN(vectorstring tokens) { stackint st; for (string token : tokens) { if (token.size() 1 string(-*/).find(token) ! string::npos) { int b st.top(); st.pop(); int a st.top(); st.pop(); if (token ) st.push(a b); else if (token -) st.push(a - b); else if (token *) st.push(a * b); else st.push(a / b); } else { st.push(stoi(token)); } } return st.top(); }这里的关键是后弹出的a是左操作数先弹出的b是右操作数。后缀表达式“4 2 -”的正确结果是2如果写成b - a就会得到-2。用一个小样例去验证代码是最快的哪怕自己构造一个“3 4 2 *”也花不了十秒。为什么栈能解决这个问题因为后缀表达式的定义就是“操作数在前运算符在后”栈天然保存了最近看到的操作数运算符出现时栈顶两个元素就是应该参与运算的那两个。这和括号匹配、函数调用栈都是同一类思想。另外中间结果可能很大建议把栈的类型设成long long或者至少在做乘法前想一下数据范围。除法还要考虑除数为0的情况机试数据一般不会给但本地测试写个防御更安心。4.2 二进制里1的个数n (n-1) 值得背进条件反射第38题“统计整数二进制中1的个数”最漂亮的解法是while (n) { count; n (n - 1); }原理一句话就够n - 1会把n最低位的1变成0并把该位右边的所有0变成1n (n-1)的结果就是把最低位的1消掉了。每循环一次消一个1循环次数就是1的个数不用傻傻循环32次。这个技巧不只是这一道题能用。判断一个数是不是2的幂可以用n 0 (n (n - 1)) 0找两个整数的二进制表示有多少位不同可以先异或再数1的个数。位运算题里这是出现频率极高的基础操作值得练成条件反射。有个注意事项如果题目输入可能为负数建议先转成unsigned类型再操作。负数在补码表示下高位全是1转成unsigned以后逻辑会清晰很多避免符号位扩展带来的困惑。4.3 任务轮转模拟别让循环硬扛10的9次方第40题这类模拟题通常描述是若干任务排成一个队列每个单位时间取出队首任务处理一个时间片没完成就重新排到队尾问某个时刻系统状态是什么。最直观的写法是逐单位时间循环但如果时间上限给到10^9线性循环必然超时。我的经验是先别急着写循环先想能不能“成批处理”。如果队列里所有任务的剩余时间都大于0那么这一轮里队列顺序不会变每个任务的剩余时间都在同步减少。找出最小剩余时间minRemain直接让时间一次性前进minRemain乘以队列长度这段时间内不会有任何任务完成也不会发生队首队尾的顺序变化。只有当某些任务剩余时间归零时才需要真正进入逐个时间片处理的状态。这个“跳步”技巧本质是把确定的重复计算合并成一次批量操作。很多模拟题看起来像纯暴力但只要时间参数给得大考察的就是你能不能发现这种批量推进的规律。4.4 模拟题通用打法先搭骨架再填规则模拟题最容易出错的地方不是算法而是规则太多、逻辑线太长。第40题这种多规则场景我的做法是先定义数据模型比如任务结构体再写主循环骨架最后把规则一条条填进去。每填一条规则就在注释里标注清楚这个任务什么条件离开队列、什么条件回到队尾、同一时刻多个事件按什么顺序处理。宁可多写两个函数也不要全部塞进一个main。机试虽然只看结果但代码结构清晰你调试时的思路也会清晰。很多人在模拟题上反复WA不是不会写是写到后面自己都忘了哪条规则处理到哪一步了。5. 本地跑得好好的在线判题就是报错输入输出与边界自检5.1 多组输入cin和getline混用的换行残留很多本地正常的代码一上判题系统就出问题第一个要怀疑的就是输入读取方式。最常见的坑是cin n之后直接getline(cin, s)然后发现s是空的。原因是cin读数字时会在缓冲区里留下一个换行符getline读到这个换行符就直接结束了。正确写法是先cin.ignore()把残留的换行吃掉再getline。如果一组数据里既有数字又有字符串我更推荐统一用getline读完一整行再用istringstream解析这样最不容易踩换行残留的坑。int n; string line; while (getline(cin, line)) { istringstream ss(line); ss n; string s; getline(cin, s); // 已经是下一行了注意上一行结尾的换行已被getline吃掉 }多组输入最大的原则是不要写死循环次数用while配合getline或者cin读取直到EOF。判题系统会连着跑很多组数据你漏读一组后面全乱。5.2 字符串切割C没有split手写时要绕开三个坑C标准库没有现成的split函数手写时常见三个坑连续分隔符会产生空串字符串开头和结尾的分隔符会被忽略或产生空元素分隔符是空格时不能用cin直接读因为cin会跳过空格。一个比较稳的写法是逐个字符扫描只在当前字符不等于分隔符时累加碰到分隔符就把已累积的字符串压入结果。vectorstring split(const string s, char delim) { vectorstring res; string cur; for (char c : s) { if (c delim) { if (!cur.empty()) res.push_back(cur); cur.clear(); } else { cur c; } } if (!cur.empty()) res.push_back(cur); return res; }这里连续分隔符不会产生空串因为压入前判断了cur是否为空。有些题目希望你保留空字段那就把条件去掉但绝大多数机试题都是跳过空串的根据题意选一种即可。5.3 提交之前对着这张边界清单过一遍我刷31~40这段时间把常见的翻车点整理成了一张自检清单每次提交前快速过一遍能挡掉大部分无谓的WA。检查点常见翻车原因应对习惯空输入、只有换行getline读到空串后直接访问下标先判空再处理n1的最小规模dp数组长度不够或循环次数少一次写代码前把n1代入验证最大规模int溢出发生在中间结果涉及乘法优先用long long重复元素排序后相邻元素比较逻辑写错用一组全相同的数据测试负数、0进制转换、位运算方向搞乱单独考虑或者统一转unsigned行尾空白字符串比较失败确认判题环境后决定是否去除\r自检不是碰运气是把出题人最爱的几个陷阱主动想一遍。尤其是第31题字符串统计和第38题位运算边界条件往往就是出题人设置区分度的位置。6. 从31刷到40我对C机试备考的几点复盘6.1 刷题顺序按类型打歼灭战不按题号打游击我不建议硬按1到100的顺序一路刷下去。31~40这个区间里31到34全是字符串和容器题连续做能快速形成手感35到37是算法思维题更适合分开做不要一个下午连着刷三道否则脑子里全是模板没有消化时间38到40偏实现可以作为一天的收尾题让大脑从“想算法”切换到“写代码”的状态。一个可行的安排是第一天集中做31到34第二天只做35和37第三天做36加上38到40。这样既照顾了知识点的连贯性又给了算法题足够的间隔消化时间。6.2 复盘只看一件事第一次没想通的地方在哪每道题做完我会在本地注释里记一句话第一次卡住的原因是什么——是看不懂题目、是没想到用栈、还是边界条件写错。隔一周重新做一遍重点看这句话是否还成立。大多数情况下第二遍能顺畅写出来说明这个知识点真正长在自己身上了如果第二遍还在同一个地方卡住那就不是“没记住”的问题是对这个模型的直觉还没建立需要再找同类题补几道。复盘不是重抄一遍代码是追问“我到底在哪个环节缺了一块知识拼图”。6.3 三个跟算法无关的小习惯最后分享三个不影响算法思想、但直接影响通过率的习惯。第一每题先花两分钟把输入输出骨架写完再想核心逻辑避免最后赶时间漏了输出格式。第二自己构造三组测试数据最小规模、普通规模、包含边界条件的数据不要只靠题目的输入样例。第三卡题超过30分钟就果断看题解但看完之后关掉题解自己重新写一遍而不是复制粘贴。这一点适用于所有刷题场景不只这个区间。如果让我把这十道题再刷一遍35题和39题我会各写三遍。不是因为它们最难而是这两道题最容易被“看懂”骗过去——你觉得逻辑都明白了一旦动手操作数顺序、状态枚举、数组初始化任何一个细节都能让结果面目全非。这种失误不能靠运气规避只能靠实打实的手感。